Massachusetts Institute of Technology Final Exam Solutions 6.042J/18.062J: Mathematics for Computer Science December 15, 1998 Professors Nancy Lynch and Srinivas Devadas

Final Exam Solutions

Problem 1. (10 points) Suppose that A and B are non-empty sets such that A is strictly contained in B. Mark each statement below True or False.

Set A is finite iff set B is finite. (False.) If B is finite, then there must exist a surjection mapping B to A. (True.) If B is finite, then there must exist an injection mapping A to B. (True.) If B is finite and there is a bijection mapping A to B \ A, then |B| = 2|A|. (True.) There can not exist a bijection from A to B. (False.)

Problem 2. (15 points) Consider the following procedure for computing the greatest common divisor (gcd) of a non-empty list of positive integers (x_{1}, x_{2}, …, x_{n}).

If all entries in the list are equal, then the procedure outputs the common value and terminates. Otherwise, the procedure selects two entries with different values and replaces the larger one by the difference.

We can model this procedure with a state machine as follows.

• The set of states Q consists of all lists of n positive integers.

• The set of start states Q_{0} consists of the single state (x_{1}, x_{2}, …, x_{n}).

• The set δ contains all transitions of the form

(y_{1}, y_{2}, …, y_{i}, …, y_{j}, …, y_{n}) → (y_{1}, y_{2}, …, y_{i} − y_{j}, …, y_{j}, …, y_{n})

where i and j are distinct numbers in the range 1 to n and y_{i} > y_{j}. (Note that the transition is written with y_{i} preceding y_{j}, but that the reverse order is also possible.)

(a) (5 points) Prove that the procedure terminates.

We construct a non-negative, decreasing derived variable. This implies that the machine reaches at state with no outgoing transitions. All such states are terminating states of the procedure.

Define the derived variable S to take on the value y_{1} + y_{2} + … + y_{n} in the state corresponding to the list (y_{1}, y_{2}, …, y_{n}). This derived variable is non-negative, since all y_{i} are positive. The derived variable is decreased by each transition, since the list entry y_{i} is decrease by y_{j} (a positive quantity) and all other list entries are unchanged.

(b) (10 points) Prove that the procedure computes the gcd of x_{1}, x_{2}, …, x_{n}. State explicitly any number theoretic facts that you use, but do not prove them.

The proof uses the Invariant Theorem. We will prove the invariant that in state (y_{1}, y_{2}, …, y_{n}),

gcd(y_{1}, y_{2}, …, y_{n}) = gcd(x_{1}, x_{2}, …, x_{n}).

The invariant hold trivially in the start state. Futhermore, the invariant holds after a transition if it holds prior to a transition:

gcd(y_{1}, y_{2}, …, y_{i} − y_{j}, …, y_{j}, …, y_{n}) = gcd(y_{1}, y_{2}, …, y_{i}, …, y_{j}, …, y_{n})
= gcd(x_{1}, x_{2}, …, x_{n})

The first step is justified by the following number-theoretic fact. For positive integers z_{1}, z_{2}, …, z_{n},

gcd(z_{1}, z_{2}, …, z_{i}, …, z_{j}, …, z_{n}) = gcd(z_{1}, z_{2}, …, z_{i} − z_{j}, …, z_{j}, …, z_{n})

provided z_{i} > z_{j}. The second step in the argument above is justified by the assumption that the invariant holds prior to the transition. Therefore, the invariant holds by the Invariant Theorem. This invariant implies that the output of the procedure is correct. If (y_{1}, y_{2}, …, y_{n}) is a terminating state, then

y_{1} = y_{2} = … = y_{n} = gcd(y_{1}, y_{2}, …, y_{n})
= gcd(x_{1}, x_{2}, …, n_{n}).

The second step uses the invariant.

Problem 3. (12 points) Find a closed-form expression for T (N) in each problem part. Your answer may make use of Θ notation. No proofs are required.

6.042J/18.062JFinal Exam Solutions 3 (a) (6 points)

T (n) = ∑_{i=1}^{n} \frac{i^{2} + 6\sqrt{i}}{i\sqrt{i}}
T (n) = ∑_{i=1}^{n} \frac{i^{2} + 6\sqrt{i}}{i\sqrt{i}}
= ∑_{i=1}^{n} \frac{i^{2}}{i\sqrt{i}} + ∑_{i=1}^{n} \frac{6\sqrt{i}}{i\sqrt{i}}
= ∑_{i=1}^{n} \sqrt{i} + ∑_{i=1}^{n} \frac{6}{i}
= Θ (n^{3/2} + ln n)
= Θ (n^{3/2})

(b) (6 points)

T (n) = \{ \begin{matrix}1 & for n ≤ 5 \\ \frac{1}{2}T (⌊\frac{n}{2} + log n⌋) + \frac{2}{n} & for n > 5 \end{matrix}

We apply Akra-Bazzi. First, we find the parameter p by solving the equation

\frac{1}{2} · (\frac{1}{2})^{p} = 1.

The solution is p = −1. Therefore, we have

T (n) = Θ (n^{−1} · (1 + ∫_{1}^{n} \frac{(\frac{2}{u})}{u^{−1+1}} du))
= Θ (n^{−1} · (1 + 2 ln n))
= Θ (\frac{ln n}{n})

Problem 4. (10 points) Suppose that five points are placed inside a square with sides of length 1. Prove that the distance between some pair of points is at most \sqrt{2}/2.

Divide the square into four subsquares with edge-length \frac{1}{2}. By the pigeonhole principle, some two of the five points must be placed inside the same subsquare. The distance between these two points can be at most \sqrt{2}/2.

Problem 5. (20 points) Solve the following counting problems. Simplified answers are not required.

(a) (4 points) In how many ways can the letters in BOOKKEEPER be arranged?

\frac{10!}{2! 2! 3!}

(b) (4 points) In how many ways can 160 distinguishable students be assigned to 8 indistinguishable recitations so that every recitation has 20 students?

If the recitations were distinguishable, then the answer would be \frac{160!}{20!^{8}} by the multinomial formula. Since the recitations are identical, the answer is \frac{160!}{20!^{8} 8!} by the quotient rule.

(c) (4 points) In how many ways can 6.042 TA John Dunagan assign the following objects to three desk drawers,

• 7 tasty treats,

• 27 thumb tacks, and

• 1 can of theoretically-enriched Spam,

so that the Spam shares a drawer with no tasty treats and at least 19 thumb tacks? (Desk drawers are distinguishable, but tasty treats and thumbtacks are not.)

Theory Pig (R. I. P.) and the tacks can be assigned to a drawer in 3 ways. The treats can be divided between the other two drawers in \binom{7+1}{1} = 8 ways. The 8 remaining tacks can be divided among the three drawers in \binom{8+2}{2} = 45 ways. Overall, there are 3 · 8 · 45 assignments.

(d) (4 points) How many ways can 100 identical balls be placed in 10 distinguishable bins so that every bin contains an odd number of balls?

First, we put 1 ball into each bin. Then we pair up the 90 remaining balls into 45 pairs. Then we assign the 45 pairs to bins. This can be done in \binom{45+9}{9} ways.

(e) (4 points) How many paths are there from (0, 0) to (4, 4) consisting of 10 steps, each of which is either north, south, east, or west?

Either there are 5 north steps, 1 south step, and 4 east steps, or else there are 5 east steps, 1 west step, and 4 north steps. Thus, there are

2 · \frac{10!}{5! 1! 4!}

paths in total.

Problem 6. (8 points) Some MIT students go for dinner at the Border Cafe in Harvard Square. They want to order enough appetizers to feed everyone. Chili con queso will feed one person, Tejas chicken will feed two people, and quesadillas will feed three people. Write the generating function for the number of different appetizer orders that will feed exactly n people.

\frac{1}{1 − x} · \frac{1}{1 − x^{2}} · \frac{1}{1 − x^{3}}

Problem 7. (10 points) The following identity holds for non-negative integers n, j, and k such that n ≥ j + k.

\binom{n}{j}\binom{n − j}{k} = \binom{n}{j + k}\binom{j + k}{k}

(a) (5 points) Prove the identity algebraically.

\binom{n}{j}\binom{n − j}{k} = \frac{n!}{j! (n − j)!} · \frac{(n − j)!}{k! (n − j − k)!}
= \frac{n!}{j! k! (n − j − k!)}
= \frac{n!}{(j + k)! (n − j − k)!} · \frac{(j + k)!}{k! j!}
= \binom{n}{j + k}\binom{j + k}{k}

(b) (5 points) Prove the identity combinatorially.

Both sides of the equation count the number of ways to choose distinguishable, disjoint subsets of sizes j and k from a set of n elements. On the left side, we first choose the j-element subset from the whole n-element set, and then choose the k-element subset from the remaining n − j elements. On the right side, we first choose j + k elements from the whole set. From these j + k elements, we then choose the k-element set; the remainders form the j-element set.

Problem 8. (5 points) Suppose that I roll a die, but conceal the result from you. You then repeatedly guess at the number that I rolled, and I will tell you whether each guess is right or wrong. No proofs are required for this problem.

(a) (2 points) Suppose that you guess 1, 2, 3, 4, 5, and then 6 in that order. What is the expected number of guesses that you need to get the right number?

From the definition of expected value, the answer is

\frac{1}{6} · (1 + 2 + 3 + 4 + 5 + 6) = \frac{7}{2}.

(b) (3 points) Suppose that you repeatedly guess numbers in the range 1 to 6 uniformly and mutually independently at random. What is the expected number of guesses that you need to get the right number?

Let the expected number of guesses be X. After a wrong guess, the expected number of guesses is the same as before. The rules of the game imply the following equation.

X = \frac{1}{6} · 1 + \frac{5}{6} · (1 + X)

By solving the equation, we find that the expected number of guesses is X = 6.

Problem 9. (5 points) A spider eats three flies a day. Each fly attempting to pass through his web has an even chance of becoming entangled. The spider eats the flies that become entangled in his web until he fills his quota. After his quota is filled, the spider allows flies that become entangled to work themselves free and escape.

Wilbur the Fly is about to attempt a flight through the spider’s web. If five flies have already made the attempt today, then what is the probability that Wilbur survives?

(Assume that the flies become entangled mutually independently.)

Among the first five flies, the number that become entangled is either less than half (≤ 2) or more than half (≥ 3). These two events are equally likely, since each fly has an even chance of becoming entangled. Therefore, the spider has an even chance of filling his quota with the first five flies.

The probability that Wilbur survives is computed below.

Pr(fly lives) = 1 − Pr(Wilbur dies)
= 1 − Pr(quota unfilled ∩ Wilbur entangled)
= 1 − Pr(quota unfilled) · Pr(Wilbur entangled)
= 1 − \frac{1}{2} · \frac{1}{2}
= \frac{3}{4}

In the first step, we switch to computing the probability of the complementary event. The second step uses the fact that Wilbur the Fly dies only if the spider’s quota is unfilled and the fly becomes entangled. The third step follows from the fact that flies become entangled mutually independently. The fourth step is substitution, and the last step is simplification.

Problem 10. (10 points) Smith and Wesson are shooting at a target. Smith’s chance of hitting the target is double that of his friend Wesson. If they each take a shot, then the probability that at least one of them hits the target is \frac{1}{2}. What is the probability that Wesson hits the target with a single shot?

(The event that one hits the target is independent of the event that the other hits the target.)

Let S be the event that Smith hits, and let W be the even that Wesson hits. We are given two facts:

Pr(S) = 2 Pr(W)
Pr(S ∪ W) = \frac{1}{2}

Expanding the second equation using inclusion-exclusion gives:

Pr(S) + Pr(W) − Pr(S ∩ W) = \frac{1}{2}
Pr(S) + Pr(W) − Pr(S) · Pr(W) = \frac{1}{2}
2 Pr(W) + Pr(W) − 2 Pr(W) · Pr(W) = \frac{1}{2}

The second equation follows from independence, and the third equation follows by substituting in the first fact listed above. The root of this quadratic that makes sense as a probabilty is \frac{3}{4} − \frac{1}{4} \sqrt{5} = 0.19 . . ..

Problem 11. (10 points) A box initially contains n black balls. The following procedure is repeated. A ball is drawn from the box at random. If the ball is white, then it is returned to the box. If the ball is black, then with probability p a white ball is returned to the box and with probability 1 − p a black ball is returned to the box. What is the expected number draws needed to fill the box with white balls?

Suppose that the box contains k white balls. The probability that a black ball is drawn and replaced by a white ball is \frac{n−k}{n} · p. Therefore, the expected number of draws to introduce one more white ball is \frac{n}{p(n−k)}. By linearity of expectation, the expected number of draws required to fill the box with white balls is:

∑_{k=0}^{n−1} \frac{n}{p(n − k)} = \frac{n}{p} · ∑_{k=0}^{n−1} \frac{1}{n − k}

= \frac{n}{p} · ∑_{j=1}^{n} \frac{1}{j}

= \frac{nH_{n}}{p}

The second step uses the substituion j = n − k.

Problem 12. (5 points) The number of people that enter Filene’s Basement in the last hour before closing on Christmas Eve is a random variable taking on an integer value in the range 0 to 100 uniformly.

Each shopper picks at least one present to buy. After selecting each present, a shopper is equally likely to continue shopping and to go pay at the checkout register. Shoppers’ decisions to continue buying are mutually independent.

The checkout clerk throws two fair, independent dice for each item and then charges a number of dollars equal to the sum.

What is the expected total amount of money spent by these last-minute shoppers at Filene’s Basement?

Applying Wald’s Theorem twice, the expected amount of money spent is the product of the expectations of the three random variables described in the problem.

Ex(money spent) = Ex(num people) · Ex(num gifts) · Ex(price)
= 50 · 2 · 7
= 700

Problem 13. (10 points) Solve the following problems concerning grades at MIT.

(a) (5 points) Suppose that the average GPA at MIT is 4.0. Give a tight upper bound on the probability that a random student’s GPA is 4.5 or higher.

From Markov’s Inequality,

Pr(GPA ≥ 4.5) ≤ \frac{4.0}{4.5}
= \frac{8}{9}.

(b) (5 points) Suppose in addition that the standard deviation of GPA’s at MIT is 0.2. Give a tight upper bound on the probability that a random student’s GPA is 4.5 or higher, taking this new information into account.

From the one-sided Chebyshev inequality,

Pr(GPA − 4.0 ≥ 0.5) ≤ \frac{0.2^{2}}{0.2^{2} + 0.5^{2}}
= \frac{4}{29}

Problem 14. (10 points) A primality testing algorithm takes as input an integer n ≥ 2 and outputs either PRIME or COMPOSITE. The algorithm uses random numbers in a clever way to give a much better run-time. An unfortunate consequence is that the algorithm only ouputs a correct answer with probability \frac{2}{3}. The answers produced by multiple runs of the algorithm are mutually independent.

(a) (7 points) Suppose that we run the algorithm Q times. Use the Chernoff inequality to lower bound the probability that the most common answer is correct. You may treat the approximation ln (\frac{3}{2}) ≈ \frac{2}{5} as an equality.

The expected number of wrong answers is \frac{1}{3}Q. Now we apply the Chernoff bound to upper bound the probability that the wrong answer is actually the most common answer.

Pr (num wrong ≥ \frac{1}{2} · Q) = Pr (num wrong ≥ \frac{3}{2} · Ex(num wrong))
≤ e^{−(\frac{3}{2})·(ln \frac{3}{2} −1+ \frac{2}{3})·Ex(num wrong)}
≈ e^{− \frac{1}{10} ·Ex(num wrong)}
= e^{− \frac{1}{30} Q}

Consequently, the most common answer is correct with probabiliy at least

1 − e^{− \frac{1}{30} Q}.

(b) (3 points) How many times must the algorithm be run to ensure that the most common answer is correct with probability at least 1 − \frac{1}{n}? Give the smallest answer that you can justify.

Suppose that we run the algorithm at least 30 ln n times. Then the probability that the most common answer is incorrect is at most:

e^{− \frac{1}{30} ·30 ln n} = e^{− ln n}
= \frac{1}{n}

Therefore, the most common answer is correct with probability at least 1 − \frac{1}{n}.

Problem 15. (10 points) The superhero Bozonmann is in hot pursuit of the archfiend Doctor Phermion. During each minute one of three events occurs.

• With probability p, Bozonmann pauses to recharge his powerpack, allowing the Doctor to get one step farther ahead.

• With probability q, the evil Doctor Phermion zaps his pursuer with a gluon gun, forcing him to fall two steps back.

• With probability 1 − p − q our resolute hero, Bozonmann, advances a step closer to the notorious villain.

If Bozonman comes within two steps of Phermion, then our hero can reach out and capture his foe immediately.

(a) (5 points) Write a recurrence and base cases describing P_{n}, the probability that Bozonmann catches Doctor Phermion, given that they start n steps apart. Do not solve the recurrence.

P_{0} = 1
P_{1} = 1
P_{2} = 1
P_{n} = pP_{n+1} + qP_{n+2} + (1 − p − q)P_{n−1} (n > 2)

(b) (5 points) Write a recurrence and base cases describing E_{n}, the expected number of minutes until Bozonmann catches up to the evil Doctor, given that they start n steps apart. Do not solve the recurrence.

E_{0} = 0
E_{1} = 0
E_{2} = 0
E_{n} = 1 + pE_{n+1} + qE_{n+2} + (1 − p − q)E_{n−1} (n > 2)