Massachusetts Institute of Technology Handout 64 6.042J/18.062J: Mathematics for Computer Science May 26, 1999 Professor Albert R. Meyer

Final Exam Solutions

Problem 1. [35 pts] Short Answers.

(a) An assembly line produced 10001 cars which passed inspection and 19 which did not. What is the largest n for which there must have been a run of n consecutive cars that passed inspection? Solution: 501

(b) What is the largest number of edges possible in a two-colorable, four vertex undirected graph (without self-loops)? Solution: 4

(c) A bridge hand consists of 13 cards. The suit-distribution of a hand is the number of cards in each suit. For example, one possible suit-distribution is 4 spades, 3 hearts, 3 diamonds, and 3 clubs. How many suit-distributions are there?

Solution: This is equivalent to placing 13 balls (corresponding to each card in a hand) to 4 bins (corresponding to each suit). Thus the number of distributions is \binom{13+4−1}{4−1} = 560.

(d) In an employment interview for an expedition to the Sahara desert, a weather forecaster honestly promises at least 95% accuracy for his daily predictions of sunshine versus rain. Is this an impressive credential for the job? Briefly explain.

Solution: Unimpressive: he could be 95% accurate by always predicting sunshine. It would be impressive if his daily prediction also was 95% accurate given that it rained.

(e) In a simple path in an undirected tree with n vertices, what is the largest number of edges possible?

Solution: n − 1

(f) What is the coefficient of x^{12} in the polynomial (7x + 3)^{50}? (Your answer may contain binomial coefficients and integer powers.)

Solution: 3^{50−12}7^{12}\binom{50}{12}

(g) Write a closed form expression for

∏_{k=1}^{∞} 2^{1/2^{k}}.

Solution: 2^{∑_{k=1}^{∞} 1/2^{k}} = 2^{1} = 2.

Handout 64: Final Exam Solutions  2  Name:

Problem 2. [10 pts] Cardinality. Let P (A) denote the powerset of a set A. Prove there is no bijection between S and P (P (S)) for any set S.

Solution: By contradiction. If there was such a bijection, then there is an surjection from S to P (P (S)). But there is an obvious surjection P (P (S)) to P (S), namely map every one-element set {T } ∈ P (P (S)) to T ∈ P (S) (and map all the other elements of P (P (S)) to an arbitrary member of P (S)—say the empty set). Since the composition of surjections is a surjection, we conclude there is an surjection from S to P (S), contradicting Cantor’s Theorem.

Problem 3. [10 pts] Stable Marriage Problem and Partial Order. We know the “morning-evening” protocol yields a man-optimal set of stable marriages when the men propose, or a woman-optimal set of stable marriage if we reverse the roles and let the women propose. In many cases there are further sets of stable marriages in addition to those produced by our protocol. We say that a stable marriage set, S_{1}, improves another such set S_{2}, in symbols S_{1} ⪰ S_{2}, if every man likes his wife in S_{1} at least as much as his wife in S_{2}.

(a) Prove that the improves relation, ⪰, is a partial order on stable marriage sets.

Solution: OMITTED

(b) What special properties do the the man-optimal and woman-optimal stable marriage sets have in this partial order?

Solution: They are the maximum and minimum elements, respectively.

(c) For stable marriage sets S_{1}, S_{2}, define the set of marriages, S_{1} ⊔ S_{2}, by having each man marry whichever of his spouses in S_{1} or S_{2} he prefers. It turns out, and you may take as given, that S_{1} ⊔ S_{2} defines a marriage set and the set is stable (neither of these facts is obvious). What special relationship does S_{1} ⊔ S_{2} have with S_{1} and S_{2} in this partial order?

Solution: It is the least upper bound of S_{1} and S_{2}.

Problem 4. [15 pts] Divide and Conquer. We wish to prove by induction on n that the recurrence

T (n) = T (⌊n/2⌋) + T (⌊n/4⌋) + n

has an asymptotic growth rate of O(n).

Circle each of the inequalities below which can serve as an induction hypothesis in a such a proof.

\begin{aligned}(i) & T (n) & ≤ & 4n^{2} \\ (ii) & T (n) & ≤ & 2n \\ (iii) & T (n) & ≤ & 10n \\ (iv) & T (n) & ≤ & 3n + 10 \\ (v) & T (n) & ≤ & 4n \end{aligned}

Solution: (iii) and (v)

Problem 5. [15 pts] Inclusion-exclusion. Consider the seven letter word almeyer.

(a) [5 pts] How many different sequences of these seven letters are there? Solution: \binom{7}{1,1,1,2,1,1} = 7!/2!

(b) [10 pts] How many such sequences are there that do not contain either of the words eye or ram? Solution:

Arrangements with eye: use {eye, a, l, m, r} = 5!
Arrangements with ram: use {ram, l, e, y, e} = 5!/2!
Arrangements with ram and eye: use {ram, eye, l} = 3!
Arrangements with neither ram nor eye = 7!/2! − 5! − 5!/2! + 3! = 2346.

Problem 6. [15 pts] Binomial Coefficients. Consider the following identity:

∑_{k=0}^{n} \binom{n}{k}2^{k} = 3^{n}.

(a) [5 pts] Prove this identity using the binomial theorem. Solution: OMITTED

(b) [10 pts] Prove this identity via a combinatorial argument. (Hint: Consider the number of ways to donate some subset of your n baseball cards to two museums. For one side, consider where each card ends up. For the other, consider where each donated card ends up.) Solution: OMITTED

Problem 7. [15 pts] Conditional Probability. We consider a hypothetical Institute with only two departments: EECS and Math, and consider the experiment where we pick a random applicant for admission to one of these departments. Define the following events:

A ::= applicant is accepted,
F ::= applicant is female,
M ::= applicant is male,
MATH ::= applicant applied to Math,
EECS ::= applicant applied to EECS.

Assume that all applicants are either male or female, and that no applicant applied to both departments.

(a) The Institute is sued for gender discrimination, with the plaintiff observing that in both EECS and Math, the probability that a woman is accepted is less than the probability that a man is accepted. This observation can be precisely expressed with two inequalities between conditional probabilities involving the events above. State these inequalities.

Solution:

Pr(A | F ∩ EECS) < Pr(A | M ∩ EECS),
Pr(A | F ∩ MAT H) < Pr(A | M ∩ MAT H).

(b) The Institute’s defense attorneys retort that overall among all applicants, a woman is more likely to be accepted than a man. Express this observation as an inequality between conditional probabilities involving the events above.

Solution:

Pr {A | F } > Pr {A | M}

(c) Although the assertions above may appear to be logically inconsistent, both the plaintiff’s and the defense’s claims about the conditional probabilities can be correct. (Never mind whose interpretation of the data we find more persuasive.) Fill in the missing table entries below with possible applicant statistics for which both the plaintiff and the University attorneys’ assertions are true.

Applied  Accepted  percent accepted
Dept Females  Females  Females

Math

EECS 100  70  70%

Total

Dept Males  Males  Males
Math  100  50  50%

EECS Total Solution:

CS  0 females accepted, 1 applied  0%
50 males accepted, 100 applied  50%
EECS 70 females accepted, 100 applied 70%
1 male accepted, 1 applied  100%
Overall 70 females accepted, 101 applied ≈ 70%
51 males accepted, 101 applied ≈ 51%

Problem 8. [20 pts] Probability of Graph Assertions. A digraph with vertices {1, 2, …, n} is called an n-digraph. (The edges of an n-digraph may be any pair of vertices; self-loops are allowed.) Given an n-digraph, G, let “d(x, y)” be the assertion that G has a directed edge from vertex x to vertex y.

(a) [1 pts] How many n-digraphs are there? Solution: 2^{n^{2}}

(b) [1 pts] How many n-digraphs satisfy the assertion ∀x, y : d(x, y)? Solution: 1

(c) [3 pts] How many n-digraphs satisfy the assertion ∃x, y : d(x, y)? Solution: 2^{n^{2}} − 1

Suppose we randomly select an n-digraph, with all n-digraphs equally likely to be selected.

(d) [5 pts] Explain why there is nonzero probability that the selected n-digraph satisfies both of the following assertions:

\begin{matrix}∀x_{1}∃x_{2}∃x_{3}∀x_{4}∀x_{5}∃x_{6} : d(x_{1}, x_{2}) ∨ d(x_{3}, x_{4}) ∨ d(x_{5}, x_{6}) ∨ d(x_{3}, x_{1}) \\ ∃x_{1}∀x_{2}∀x_{3}∃x_{4}∃x_{5}∃x_{6} : d(x_{1}, x_{2}) ∧ d(x_{3}, x_{4}) ∧ d(x_{5}, x_{6}) ∧ d(x_{3}, x_{1}) \end{matrix}

Solution: We need only show that some n-digraph satisfies both assertions. The complete n-digraph is one.

(e) [6 pts] A directed Hamiltonian cycle in a digraph is a directed cycle going through each vertex exactly once. What is the expected number of directed Hamiltonian cycles in the selected graph?

Solution:

E [number of cycles through a particular Hamiltonian cycle of vertices]

= Pr {all edges present in a particular cycle of the vertices}
= 1/2^{n}.

The number of Hamiltonian cycles is n!/n so the expected number of cycles is n!/n2^{n}.

(f) [4 pts] Circle all that apply: the expected number of Hamiltonian cycles is

= Ω(e − 0.001)^{n ln n},  = Θ(e^{n ln n}),  = O(e + 0.001)^{n ln n},  ∼ e^{n ln n}/(2e)^{n}.

Solution: The first and third. Using Stirling’s formula

n!/n2^{n} ∼ \sqrt{2π/n}(n/e)^{n}/2^{n} = \sqrt{2π/n}e^{n ln n}/(2e)^{n}.

The dominant term is e^{n ln n}, but the answer is not Θ(e^{n ln n}) because of the other nonconstant factors. However, slightly increasing or decreasing the base e of the domininant term will compensate for the factors. Here’s a careful argument for the Ω(e − 0.001)^{n ln n} answer: But e^{n ln n} = [(e − 0.001)α]^{n ln n} where α = e/(e − 0.001) > 1, so

\sqrt{2π/n}(e^{n ln n})/(2e)^{n} = \sqrt{2π/n}(α^{n ln n})(e − 0.001)^{n ln n}/(2e)^{n}
= \sqrt{2π/n}(e − 0.001)^{n ln n}(α^{ln n}/2e)^{n}
≥ \sqrt{2π/n}(e − 0.001)^{n ln n}3^{n}
= [3^{n}\sqrt{2π/n}](e − 0.001)^{n ln n}

when n is large enough that α^{ln n} ≥ 6e. Since the bracketed expression in the final term grows unboundedly, the final term is Ω(e − 0.001)^{n ln n}.

Problem 9. [15 pts] Wald’s Theorem.

There was a mistake in the original version of this problem, so it was cancelled from the actual final. The corrected version is below.

Suppose successive digits from zero to nine are generated independently until the four digit sequence 9999 appears.

What is the expected number of digits generated?

Hint: Parse the sequence into consecutive “tries to get 9999”, where a “try” is either a single digit other than 9, or a 9 followed by a single digit other than 9, etc. For example, the sequence 92349982999769999 parses into eight tries:

/92/3/4/998/2/9997/6/9999/.

Solution: 11110.

By Wald’s Theorem, the expected number is the mean time to a successful try, namely 10^{4}, times the expected length of a try. Notice that a try is of length four iff it begins with three nines, so the probability of a length four try is 1/10^{3}. That means the expected length of a try is

1 · \frac{9}{10} + 2 · \frac{1}{10} \frac{9}{10} + 3 · (\frac{1}{10})^{2} \frac{9}{10} + 4 · (\frac{1}{10})^{3} = (900 + 180 + 27 + 4)/1000 = 1111/1000

Thus on average, we will have to read 11110 digits in order to see “9999”.

Problem 10. [20 pts] Law of Large Numbers. Let X_{1}, X_{2}, … be a sequence of mutually independent random variables such that Var [X_{i}] ≤ b for some b ≥ 0 and all i ≥ 1. Let

S_{n} ::= X_{1} + X_{2} + ⋯ + X_{n}.

Prove that for every ϵ > 0

lim_{n→∞} Pr \{|\frac{S_{n}}{n} − E [\frac{S_{n}}{n} ]| ≥ ϵ\} = 0.

Hint: Adapt the proof in the class handout of the Weak Law of Large Numbers. Note that in the version from the handout, the X_{i}’s came from independent samples of the same 0-1 valued experiment, which is not the case here.

Solution: Same as proof in the notes, simply replacing Var [G] by b.

Problem 11. [15 pts] Bounds from the Mean. Two hundred students take a final exam. Given only that the mean on the exam is 60 and the lowest score was 20,

(a) [10 pts] state a best possible upper bound on the number of students who scored at least 120.

Solution: Let R be the score. Apply Markov’s Bound to R − 20:

Pr {R ≥ 120} = Pr {R − 20 ≥ 100} ≤ E [R − 20] /100 = 40/100 = 2/5,

so at most (2/5)200 = 80 students score ≥ 120.

(b) [5 pts] Give an example set of scores which achieve your bound.

Solution: Of the 200 students, 80 score 120 and 120 score 20. The mean is

(80 · 120 + 120 · 20)/200 = 60,

as required.

Problem 12. [15 pts] Bounds from the Mean. An exam has 20 true/false questions and 10 multiple choice questions. Each true/false question is worth 2 points, while each multiple choice question is worth 6 points. There is a student who answers the questions randomly and independently. The student is correct with probability 1/2 on each true/false question, and with probability 1/3 on each multiple choice question.

(a) [4 pts] What is the expected score of the student?

Solution: 1/2 · 20 · 2 + 1/3 · 10 · 6 = 40

(b) [6 pts] What is the variance of the student’s score?

Solution: 100. Let T_{i} be the score on ith T/F question.

Var [T_{i}] = E [T_{i}^{2}] − E^{2} [T_{i}] = 1/2 · 2^{2} − 1 = 1.

Let M_{i} be the score on ith multiple choice question.

Var [M_{i}] = E [M_{i}^{2}] − E^{2} [M_{i}] = 1/3 · 6^{2} − 2^{2} = 8.

Let S be the final score, so

S = ∑_{i=1}^{20} T_{i} + ∑_{i=1}^{10} M_{i}.

Because of independence, the variances add:

Var [S] = ∑_{i=1}^{20} Var [T_{i}] + ∑_{i=1}^{10} Var [M_{i}] = 20 · 1 + 10 · 8 = 100.

(c) [5 pts] To give an upper bound on the probability that the student scores more than 80 points, one or more among Markov’s, Chebyshev’s, and Chernoff’s bounds, and the bounds derived for the tails of the binomial distribution are applicable. Which ones?

Solution: Markov and Chebyshev apply; Chernoff requires Bernoulli (0/1-valued) variables, so doesn’t apply in any direct way; the distribution of S would be binomial only if the probabilities and values of the two kinds of questions were the same, but they aren’t, so binomial bounds don’t apply.