Reference no: EM132740048

Discrete Mathematics Assignment

You are required to write down your answers with steps on papers (and write your name and student ID on the first page), take photos on them, convert them to a PDF file, and then submit to OLE. You may use the mobile app CamScanner. Note that computer-typed answers are not accepted.

Question 1: Rewrite each of the following propositions such that negation appear only within predicates. For example, ¬ ∃y ∃x P (x, y) should be rewritten as ∀y ∀x ¬P (x, y).
(a) ¬ ∃x ∀y P (x, y)
(b) ¬ ∃y (∀x ∃z P (x, y, z) ∨ ∃x ∀z Q(x, y, z))

Question 2: Let N be a set of sets defined as follows:
ˆ N contains the empty set ∅;
ˆ if N contains the set x, then N contains the set x ∪ {x}.
(a) Give any five distinct elements of N .

(b) Determine the truth value of the statement "Each element of N is a set containing a distinct number of elements".
(c) Use proof by contradiction to show that N is an infinite set.
(d) Prove or disprove that N ∈ N .

Question 3 Let S be any infinite set, and let T = {f | f : S → S} be the set of functions from S to S. Prove that S and T do not have the same cardinality.

Question 4 Twelve basketball players, whose uniforms are numbered 1 through 12, stand around the center ring on the court in an arbitrary arrangement. Show that some three consecutive players have the sum of their numbers at least 20.

Question 5 Give a combinatorial argument to prove that
n· 4^n-1 = ∑ⁿ_k=0C(n, k)·3^k·(n - k).
You may consider the scenario that n people go to a wine tour by car. One person is the driver who must not drink. The other people can choose one of the 3 alcoholic menus or a non-alcoholic menu.

Note that a non-combinatorial proof will receive 0 marks.

Question 6 Use mathematical induction to show that for all events E1, E2, . . . , En,

p(E₁ ∪ E₂ ∪ · · · ∪ E_n) ≤ ∑ⁿ_i=1p(E_i) .

Question 7 Suppose you are given two envelopes, each containing an integer from the set {0, 1, 2, · · · , 10}. The two envelopes are guaranteed to have two distinct numbers. You are allowed to peek at the number in one envelope, and you win by choosing the envelope with the larger number.

(a) Consider the following strategy:
1. Peek into a random envelope. We see a value r.

2. If r > 5, then guess that r is the larger number; otherwise, guess that the larger number is in the other envelope.
Give two examples of the envelope numbers in which this strategy has exactly 50% chance of winning and more than 50% chance of winning.
(b) Consider the following strategy:
1. Pick a number x from the set {0.5, 1.5, · · · , 9.5} randomly.
2. Peek into a random envelope. We see a value r.

3. If r > x, then guess that r is the larger number; otherwise, guess that the larger number is in the other envelope.
(i) If x is between the two envelope numbers, what is the chance of winning?

(ii) Let p be the probability that we choose the number x such that a < x < b, where a and b are the two envelope numbers. Show that p > 0.
(iii) Show that this strategy has a better than 50% chance of winning.

Question 8: Suppose a fair die is tossed.
(a) Let X be the random variable that equals twice the number that occurs. Compute E(X).
(b) Let Y be the random variable that equals 1 when an odd number occurs, and equals 3 otherwise. Compute
E(Y ).

(c) Let Z = X + Y , where X and Y are the random variables defined in (a) and (b), respectively. Find Z(y) for each outcome y ∈ {1, 2, · · · , 6}, and hence compute E(Z).