BSc.-Discrete Mathematics-Mumbai-April 2019
MUMBAI UNIVERSITY
Paper / Subject Code: 82304
Discrete Mathematics.
Time : 2 1/2Hrs.
Total Marks : 75
N. B.: (1) All questions are compulsory.
(2) Make suitable assumptions wherever necessary and state the assumptions made.
(3) Answers to the same question must be written together.
(4) Numbers to the right indicate marks.
(5) Draw neat labeled diagrams wherever necessary.
(6) Use of Non-programmable calculators is allowed.
____________________________________________________________________________________________________________________________
Q. 1. Attempt any three of the following: (15M)
a) Define Universal statement, conditional statement and existential statement. Give example of each.
b) Define domain, co-domain and function. Define functions H and K from R to R by the following formulas: For all x ∈ R,
????(????) = (???? − 2)2 ???????????? ????(????) = (???? − 1)(???? − 3) + 1 Does H = K? Explain.
c) In a survey of 60 people, it was found that
25 read Newsweek magazine 26 read Time
26 read Fortune 9 read both Newsweek and Fortune
11 read both Newsweek and Time 8 read both Time and Fortune
3) read all three magazines.
i) Find the number of people who read at least one of the three magazines.
ii) Draw a Venn diagram and fill the correct numbers in each of the regions.
d) Prove the following by contradiction:
There is no computer algorithm that will accept any algorithm X and data set D as input and
then will output “halts” or “loops forever” to indicate whether or not X terminates in a finite
number of steps when X is run with data set D.
e) Let p: He is rich q: He is happy
Write each of the following statements in symbolic form using p and q.
i) He is poor
ii) If he is rich, then he is unhappy.
iii) He is neither rich nor happy.
iv) It is necessary to be poor in order to be happy.
v) To be poor is to be unhappy.
f) The logician Raymond Smullyan describes an island containing two types of people: knights who always tell the truth and knaves who always lie.∗ You visit the island and are approached by two natives who speak to you as follows:
A says: B is a knight.
B says: A and I are of opposite type.
What are A and B?
Q. 2) Attempt any three of the following: (15M)
a) Define Predicate, its domain and truth set. Let Q(x) be the predicate “x is a factor of 12. Find the truth set of Q(x) if
I) the domain of n is the set Z+ of all positive integers
ii) the domain of n is the set Z of all integers.
b) Consider a statement of the form: ∀x ∈ D, if P(x) then Q(x). Write its contrapositive, converse and inverse. Write a formal and an informal contrapositive, converse, and inverse for the following statement: If a real number is greater than 2, then its square is greater than 4.
c) State which are valid and which are invalid. Justify your answers.
i) All healthy people eat an apple a day.
Keisha eats an apple a day.
∴ Keisha is a healthy person.
ii) All freshmen must take writing.
Caroline is a freshman.
∴ Caroline must take writing.
iii) All healthy people eat an apple a day.
Herbert is not a healthy person.
∴ Herbert does not eat an apple a day.
iv) If a product of two numbers is 0, then at least one of the numbers is 0.
For a particular number x, neither (2x + 1) nor (x − 7) equals 0.
∴ The product (2x + 1)(x − 7) is not 0.
v) If a number is even, then twice that number is even.
The number 2n is even, for a particular number n.
∴ The particular number n is even.
d) i) Prove that every integer is a rational number.
ii) Consider the statement: The negative of any rational number is rational.
1) Write the statement formally using a quantifier and a variable.
2) Determine whether the statement is true or false and justify your answer.
e) Define floor and ceiling. Prove that for all real numbers x and all integers m,
⌊???? + ????⌋ = ⌊????⌋ + ????.
f) i) Prove that if a, d, q, and r are integers such that a = dq + r and 0 ≤ r < d, then
???? = ⌊????/????⌋ and ???? = ???? − ⌊????/????⌋ ∙ ????.
ii) Prove that for all positive integers a and b, gcd(a, b) = lcm(a, b) if, and only if, a = b.
Q. 3) Attempt any three of the following: (15M)
a) If x is a real number not divisible by π, then for all integers n ≥ 1, prove by using method of induction that:
???????????? ???? + ???????????? 3???? + ???????????? 5???? +· · · +???????????? (2???? − 1) x=\frac{1-cos2nx}{2sinx}
b) You begin solving a jigsaw puzzle by finding two pieces that match and fitting them together. Each subsequent step of the solution consists of fitting together two blocks made up of one or more pieces that have previously been assembled. Use strong mathematical induction to prove that the number of steps required to put together all n pieces of a jigsaw puzzle is n − 1.
c) Solve the recurrence relation ???????? = −3????????−1 − 3????????−2 − ????????−a with
d) Let J5 = {0, 1, 2, 3, 4}. Then J5 − {0}={1, 2, 3, 4}.
Student A tries to define a function R : J5 − {0}→ J5 − {0} as follows:
For each x ∈ J5 − {0}, R(x) is the number y so that (xy) mod 5 = 1.
Student B claims that R is not well defined. Who is right: student A or student B? Justify your answer.
e) Define F: Z → Z and G: Z → Z by the rules ????(????) = 7???? and ????(????) = ???? ???????????? 5 for all integers a. Find (???? ? ????)(0), (???? ? ????)(1), (???? ? ????)(2), (???? ? ????)(3), ???????????? (???? ? ????)(4).
f) i) Prove that any infinite set contains a countably infinite subset.
ii) If A is any countably infinite set, B is any set, and g: A → B is onto, then B is countable.
Q. 4. Attempt any three of the following: (15M)
a) i) Define inverse relation.
ii. Let A = {3, 4, 5} and B = {4, 5, 6} and let R be the “less than” relation. That is, for all (????, ????) ∈ ???? × ????, ???? ???? ???? ⇔ ???? < ????. State explicitly which ordered pairs are in R and R−1.
b) Prove that:
I) If R is reflexive, then R−1 is reflexive.
ii) If R and S are reflexive, is R ∩ S reflexive? Why?
c) Define an equivalence relation. Suppose A is a set, R is an equivalence relation on A, and a and b are elements of A.If a R b, then prove that [a] = [b].
d) Prove that any sum of an odd number of odd integers is odd.
e) Determine whether G and G’ are isomorphic. If they are, give a function g: V(G) → V(G’) that defines the isomorphism. If they are not, give an invariant for graph isomorphism that they do not share.
i)
ii)
f) Use Kruskal’s algorithm to find a minimum spanning tree for the following graph. Indicate the order in which edges are added to form each tree.
Q. 5) Attempt any three of the following: (15M)
a) An urn contains two blue balls (denoted B1 and B2) and one white ball (denoted W). One ball is drawn, its color is recorded, and it is replaced in the urn. Then another ball is drawn, and its color is recorded.
i) Let B1W denote the outcome that the first ball drawn is B1 and the second ball drawn is W. Because the first ball is replaced before the second ball is drawn, the outcomes of the experiment are equally likely. List all nine possible outcomes of the experiment.
ii) Consider the event that the two balls that are drawn are both blue. List all outcomes in the event. What is the probability of the event?
iii) Consider the event that the two balls that are drawn are of different colors. List all outcomes in the event. What is the probability of the event?
b) i) A person buying a personal computer system is offered a choice of three models of the basic unit, two models of keyboard, and two models of printer. How many distinct systems can be purchased?
ii) How many integers are there from 10 through 99?
iii) How many odd integers are there from 10 through 99?
iv) How many integers from 10 through 99 have distinct digits?
v) A bit string is a finite sequence of 0’s and 1’s. How many bit strings have length 8?
c) How many positive integers less than 1,000 have no common factors with 1,000? (Use De Morgan’s laws and the inclusion/exclusion rule)
d) i. If seven integers are chosen from between 1 and 12 inclusive, must at least one of them be odd? Why?
ii) If ten integers are chosen from between 1 and 20 inclusive, must at least one of them be even? Why?
iii) If n + 1 integers are chosen from the set {1, 2, 3, . . . , 2n}, where n is a positive integer,must at least one of them be odd? Why?
iv) How many cards must you pick from a standard 52-card deck to be sure of getting at least 1 red card? Why?
v) A certain college class has 40 students. All the students in the class are known to be from 17 through 34 years of age. You want to make a bet that the class contains at least x students of the same age. How large can you make x and yet be sure to win your bet?
e) An urn contains four balls numbered 2, 2, 5, and 6. If a person selects a set of two balls at random, what is the expected value of the sum of the numbers on the balls?
f) A student taking a multiple-choice exam does not know the answers to two questions. All have five choices for the answer. For one of the two questions, the student can eliminate two answer choices as incorrect but has no idea about the other answer choices. For the other question, the student has no clue about the correct answer at all. Assume that whether the student chooses the correct answer on one of the questions does not affect whether the
student chooses the correct answer on the other question.
i) What is the probability that the student will answer both questions correctly?
ii) What is the probability that the student will answer exactly one of the questions correctly?
iii) What is the probability that the student will answer neither question correctly?