Massachusetts Institute of Technology Handout 63 6.042J/18.062J: Mathematics for Computer Science December 8, 1998 Professors Nancy Lynch and Srinivas Devadas

Practice Final Solutions

Problem 1. [8 points]

Recall the definition of the Fibonacci numbers:

F_{n} = \begin{cases}0 & if n = 0 \\ 1 & if n = 1 \\ F_{n−1} + F_{n−2} & if n > 1 \end{cases}

(a) [2 points] Which Fibonacci numbers are even? (I.e., find a necessary and sufficient condition on n that characterizes when F_{n} is even). State a theorem of the form: F_{n} is even if and only if… Answer: F_{n} is even if and only if 3|n.

(b) [6 points] Prove that your answer to part (a) is correct. Answer: There are many ways to proceed. We will use strong induction on the hypothesis P (n) = “2|F_{n} ⇔ 3|n′′. Base case: P (0) is true since 3|0 and F_{0} = 0 is even. Inductive step: We will show that ∀n ≥ 0, (P (0) ∧ … ∧ P (n)) ⇒ P (n + 1) In other words, we will assume that P (k) is true for 0 ≤ k ≤ n in order to prove that P (n + 1) is true. There are three cases to consider:

\underline{Case 1} n ≡ 0 mod 3.

In this case, 3 does not divide n + 1 and so it suffices to show that F_{n+1} is odd. If n = 0, then P (n + 1) is true since F_{n+1} = F_{1} = 1 is odd. If n > 0, then n ≥ 3 and F_{n+1} = F_{n} + F_{n−1}. Since 3|n, we know that 3 doesn’t divide (n − 1). By the inductive assumption, this means that F_{n} is even and F_{n−1} is odd. Hence, F_{n+1} is odd, as desired.

\underline{Case 2} n ≡ 1 mod 3.

In this case 3 does not divide (n + 1) and so it suffices to show that F_{n+1} is odd. Since 3 does not divide n and 3|(n − 1), we know by the inductive assumption that F_{n} is odd and F_{n−1} is even. Hence, F_{n+1} = F_{n} + F_{n−1} is odd, as desired.

\underline{Case 3} n ≡ 2 mod 3.

In this case, 3|(n + 1) and so it suffices to show that F_{n+1} is even.

Since 3 does not divide n or (n − 1), we know from the inductive assumption that F_{n} and F_{n−1} are odd. This means that F_{n+1} = F_{n} + F_{n−1} is even, as desired.

This concludes the inductive step of the proof. Hence, P (n) is true for all n ≥ 0.

Problem 2. [10 points]

Consider an n-player tournament for n ≥ 2 in which there is a match between each pair of players. In each match, there is one winner and one loser (no ties allowed). Let P denote the set of players and let W ⊆ P denote the subset of players who won the most games (I.e., x ∈ W if x wins k games and no other player wins more than k games). Let B(x, y) be a predicate which is true if and only if x beats y. (Note: B(x, x) is always false).

(a) [2 points] Express the following statement using quantifiers and logical notation. “For any player x ∈ W and any other player z, either x beats z or there exists a player y such that x beats y and y beats z (or both)”. Answer:

∀x ∈ W ∀z ∈ P ((x ≠ z) ⇒ (B(x, z) ∨ ∃y ∈ P (B(x, y) ∧ B(y, z))))

(b) [2 points] Write the negation of the preceding statement in logical notation without using the negation or complement symbol. Also, do not use the ≠ symbol for this part. (Note: B(z, x) implies z ≠ x). You do not need to prove your answer is correct. Answer:

∃x ∈ W ∃z ∈ P (B(z, x) ∧ (∀y ∈ P (B(y, x) ∨ B(z, y))))

(c) [6 points] Prove the statement in part (a). Answer: The proof is by contradiction. Assume for the purposes of contradiction that the statement in part (a) is not true. This means that the statement in part (b) is true. Hence, there exists a player x ∈ W and a different player z ∈ P such that z beats x and ∀y ∈ P, z beats y or y beats x. Let P_{x} denote set of players beaten by x, and P_{z} denote set of players beaten by z. Note that x ∉ P_{x}. Since ∀y ∈ P, z beats y or y beats x, we know that z beats every player in P_{x}. In addition z beats x. Since x ∉ P_{x}, this means that |P_{z}| ≥ |P_{x}| + 1, which contradicts the assumption that x ∈ W.

Problem 3. [8 points] Find a closed form expression for T (n) in each of the following sums and recurrences. In order to save time in calculations, you can express your answer using Θ notation. You do not need to prove your answer. (In each case n ∈ ℕ, but you can ignore the case when n = 0).

(a) [2 points]

T (n) = ∑_{i=1}^{n} \frac{2}{i}

Answer: Θ(ln n) by the integral method or the formulas given in class.

(b) [2 points]

T (n) = ∑_{i=1}^{n}(i + 3)

Answer: Θ(n^{2}) by the integral method or the formulas given in class.

(c) [2 points]

T (n) = \begin{cases}1 & if n ≤ 4 \\ T (⌊\frac{n}{4}⌋) + T (⌊\frac{n}{3}⌋) + n^{2} & if n > 4 \end{cases}

Answer: We will use the Akra-Bazzi formula. We observe that p < 1. Θ (n^{p} (1 + ∫_{1}^{n} \frac{x^{2}}{x^{p+1}} dx)) = Θ (n^{p}n^{2−p}) = Θ(n^{2})

(d) [2 points]

T (n) = \begin{cases}1 & if n ≤ 4 \\ 2T (⌊\frac{n}{4} + \sqrt{n}⌋) + \sqrt{n} & if n > 4 \end{cases}

Answer: We use the Akra-Bazzi formula. p is the solution to 2 (\frac{1}{4})^{p} = 1, so p = 1/2

Θ (n^{1/2} + n^{1/2} ∫_{1}^{n} \frac{\sqrt{x}}{x^{3/2}} ) = Θ (n^{1/2} + n^{1/2} ∫_{1}^{n} \frac{1}{x})
= Θ(n^{1/2} + n^{1/2} ln n)
= Θ(n^{1/2} ln n)

Problem 4. [6 points] Solve the following recurrence for T (n).

T (n + 1) = 6T (n) − 9T (n − 1) + 2^{n}

with the initial conditions T (0) = 1, T (1) = −1. Answer: A particular solution is of the form k2^{n}. Plugging in the equation we obtain k = 2. The characteristic polynomial x^{2} − 6x + 9 has a double root at 3. So the general solution has the form a3^{n} + bn3^{n} + 2^{n+1} We use the initial conditions to solve for a, b to obtain a = −1, b = −2/3 So the answer is

T (n) = −3^{n} − 2n3^{n−1} + 2^{n+1}

Problem 5. [10 points]

(a) [5 points] Calculate the number of ways the integers from 1 to 9 can be arranged so that no even integer is in its natural position. (For example 2 is not in the second position, and so on). Specify your answer as an integer or as the sum of products of integers. (You may include factorials in your answer but not binomial coefficients). Answer: Let A_{i} be the set of ways of arranging the integers such that integer i is in it’s natural position. We observe that |A_{i}| = 8!, |A_{i} ∩ A_{j}| = 7!, |A_{i} ∩ A_{j} ∩ A_{k}| = 6!, and |A_{i} ∩ A_{j} ∩ A_{k} ∩ A_{l}| = 5!, for i, j, k, and l distinct integers in {1, …, 9}. We use inclusion/exclusion to calculate the number of ways to arrange the integers such that some even integer is in it’s natural position. |A_{2} ∪ A_{4} ∪ A_{6} ∪ A_{8}| = \binom{4}{1}8! − \binom{4}{2}7! + \binom{4}{3}6! − 5! = 4 · 8! − 6 · 7! + 4 · 6! − 5! So the number of ways of arranging the integers such that none of the even integers is in it’s natural position is 9! − |A_{2} ∪ A_{4} ∪ A_{6} ∪ A_{8}| = 9! − 4 · 8! + 6 · 7! − 4 · 6! + 5!

(b) [5 points] How many strings are there with n 1’s, 2n 2’s, and 3n 3’s? Leave your answer in the form of a ratio of factorials. You do not need to prove your answer.

Answer: \frac{(6n)!}{n!(2n)!(3n)!}

by the formula for multinomial coefficients.

Problem 6. [8 points]

Consider an n-node undirected graph G = (V, E). A simple k-cycle (2 < k ≤ n) in G is a sequence of distinct nodes v_{1}, v_{2}, …, v_{k} for which (v_{1}, v_{2}) ∈ E, (v_{2}, v_{3}) ∈ E, …, (v_{k−1}, v_{k}) ∈ E, and (v_{k}, v_{1}) ∈ E. Note that v_{1}, v_{2}, …, v_{k} is the same cycle as v_{2}, v_{3}, …, v_{k}, v_{1}, and so forth. Also, v_{1}, v_{2}, …, v_{k} is the same cycle as v_{k}, …, v_{2}, v_{1}.

(a) [4 points] What is the maximum possible number of distinct k-cycles in G (assuming all possible edges are present in G)? (Note: for n = 3 the answer is 1). Answer: The number of ways of choosing k vertices in some particular order is \frac{n!}{(n−k)!}. Since v_{1}, v_{2}, …, v_{k} is the same cycle as v_{2}, v_{3}, …, v_{k}, v_{1} (k such cycles), and v_{1}, v_{2}, …, v_{k} is the same cycle as v_{k}, …, v_{2}, v_{1} (2 such cycles), the answer is \frac{n!}{2k(n−k)!} by the division rule.

(b) [4 points] Now suppose that G is constructed randomly as follows: For every pair of nodes {v_{i}, v_{j}}, toss a coin of bias p. Include the edge {v_{i}, v_{j}} if the coin comes up heads. Assume that the coin tosses are mutually independent. What is the expected number of k-cycles in G ? (If you were not able to solve part (a), you may let X denote the answer to part (a) and express your answer in terms of X, k, and p). Answer: Let I_{e} be the indicator random variable of the event “edge e appears on the graph”. Let C_{k} be the number of simple k-cycles in the graph. Then

C_{k} = ∑_{e_{1},... ,e_{k}} I_{e_{1}} · . . . · I_{e_{k}}

where e_{1}, …, e_{k} runs through all possible simple k-cycles. Taking expectations of the above sum and using linearity of expectation and the fact that the events of edges appearing on the graph are independent, we obtain

C_{k} = ∑_{e_{1},... ,e_{k}} Ex[I_{e_{1}}] · . . . · Ex[I_{e_{k}}]

Since Ex[I_{e}] = p for every edge, Ex[C_{k}] = Xp^{k} = \frac{n!p^{k}}{2k(n−k)!}.

Problem 7. [9 points]

The gambling game Yahtzee is played with five fair, mutually independent six-sided dice. In the following questions, you may leave factorials and binomial coefficients in your answer.

(a) [3 points] The gambling game Yahtzee is played with five fair, mutually independent sixsided dice. In the following questions, you may leave factorials and binomial coefficients in your answer. Answer: There are six choices for the number that occurs five times. There are 6^{5} possible rolls, so the answer is 6 (\frac{1}{6})^{5} = \frac{1}{6^{4}}

(b) [3 points] Find the probability of a straight. A straight is either a throw of {1, 2, 3, 4, 5} or {2, 3, 4, 5, 6}. (Note that the dice are unordered - e.g., any roll which results in one 1, one 2, one 3, one 4, and one 5 counts as a straight). Answer: There are two ways to choose the type of straight, and 5! ways of arranging the numbers on the faces of the dice. Since the total number of resulting dice throws is 6^{5}, the answer is \frac{2·5!}{6^{5}}.

(c) [3 points] A full house is a result in which there is a group of three dice with the same number, and a group of two dice with the same number (for example {2, 2, 5, 5, 5} is full-house). A Yahtzee doesn’t count as a full house. Find the probability of a full house. Answer: There are 6 ways to choose the triple and 5 ways to choose the pair (once the triple is chosen). There \binom{5}{2} ways to pick the dice that will be assigned to the pair.

Pr(fullhouse) = \frac{6·5\binom{5}{2}}{6^{5}} = \frac{50}{6^{4}}.

Problem 8. [12 points]

Bobo decides to bet one dollar at a casino. However, he’s not sure what game he wants to play.

• The probability that Bobo plays poker is 20%, in which case he has a 30% chance of winning $2 and a 70% chance of losing $1.

• The probability that Bobo plays blackjack is 20%, in which case he has a 40% chance of winning $1 and a 60% chance of losing $1.

• The probability that Bobo plays the slot machines is 60%, in which case he has a 30% chance of winning $1 and an 70% chance of losing $1.

Let X denote Bobo’s winnings when he makes one bet according to the above probabilities.

(a) [2 points] What is Ex[X]? Answer: If Bobo plays poker his expected winings are 0.3(2) − 0.7(1) = −0.1 If Bobo plays blackjack his expected winnings are 0.4(1) − 0.6(1) = −0.2 If Bobo plays the solt machines his expected winnings are 0.3(1) − 0.7(1) = −0.4 Therefore, Ex[X] = 0.2(−0.1) + 0.2(−0.2) + .6(−0.4) = −0.3

(b) [2 points] What is Ex[X^{2}]? Answer: If Bobo plays poker Ex[X^{2}|poker] = 0.3(4) + 0.7(1) = 1.9 If Bobo plays blackjack Ex[X^{2}|blackjack] = 0.4(1) + 0.6(1) = 1 If Bobo plays the solt machines Ex[X^{2}|machines] = 0.3(1) + 0.7(1) = 1 Therefore, Ex[X^{2}] = 0.2(1.9) + 0.2 + .6 = 1.18

(c) [4 points] What is Var[X]? Var[X] = Ex[X^{2}] − Ex[X]^{2} = 1.18 − (0.3)^{2} = 1.09

(d) [4 points] If we know that Bobo won one dollar at the casino, what is the probability that he played blackjack? Answer: Let W be the event that Bobo won $1,B be event that he played blackjack, P be the event he played poker, and M the event that he played the slot machines. From Bayes Law, we know that

Pr(B|W) = \frac{Pr(W |B)P (B)}{Pr(W)}
= \frac{Pr(W |B)P (B)}{Pr(W |B)Pr(B) + Pr(W |M)Pr(M) + Pr(W |P)Pr(P)}
= \frac{(0.4)(0.2)}{(0.4)(0.2) + (0.3)(0.6) + (0)(0.2)}
= \frac{0.08}{0.26}
= \frac{4}{13}

Note that Pr(W |P) = 0, since Bobo won precisely one dollar.

Problem 9. [14 points] The spider is expecting guests and wants to catch 500 flies for her dinner. The expected number of flies caught in the web per hour is 40.

(a) [4 points] What is an upper bound to the probability that the spider will have caught 500 flies in 10 hours? Answer: Using Markov’s inequality we obtain Pr(X = (5/4)400) ≤ Pr(X ≥ (5/4)400) ≤ 4/5

(b) [2 points] What is a lower bound to the probability that the spider will have to wait more than 10 hours to catch 50 flies? Answer: The event that the fly has to wait more than 10 hours to catch 500 flies is the same as the event that the spider will catch less than 500 flies in 10 hours. This is the complement of the event that the spider catches at least 500 flies in 10 hours, so by part (a) the answer is 1 − 4/5 = 1/5.

(c) [4 points] The spider checks her log and discovers that the standard deviation for the number of flies caught in an hour is 20. Find an upper bound on the probability that the spider will catch 500 flies within 10 hours, using this additional information. Answer: Since the standard deviation for the number of flies caught in one hour is 20, the standard deviation for the number of flies caught in 10 hours is \sqrt{(10 · 20^{2})} = 20\sqrt{10} Using Chebychev’s inequality we obtain

Pr(X = 500) ≤ Pr(X ≥ 400 + \frac{\sqrt{10}}{2} · 20\sqrt{10}) ≤ \frac{1}{1 + \frac{\sqrt{10}}{4}^{2}} = \frac{2}{7}

(d) [4 points] The spider discovers additional interesting information. The standard deviation is not 20 after all, but 100 flies pass by her web every hour. 60 of these flies are quite small and are caught with probability 1/6 each. 40 of the flies are big and are caught with probability 3/4 each. Assume all fly interceptions are mutually independent. Using this information, find an upper bound on the probability that the spider will catch 500 flies within 10 hours. (Since you don’t have a calculator, you may leave ln and e in your answer). Answer: We use the Chernov bound. The expected number of flies caught every hour is (1/6)60 + (3/4)40 = 40, so the expected number of flies in 10 hours is 400. Pr(X = 500) ≤ Pr(X ≥ \frac{5}{4}400) ≤ e^{−(ln \frac{5}{4} + \frac{4}{5} −1)500} = e^{−(ln \frac{5}{4} − \frac{1}{5} )500} = 9.45 · 10^{−6}

Problem 10. [8 points] Six computers c_{1}, …, c_{6} are connected in a circle so that c_{1} is connected to c_{2} and c_{6}, c_{2} is connected to c_{1} and c_{3} and so forth. There is also a seventh computer c_{0} with direct connections to the other six computers. When two computers want to communicate the signal is transmitted through the shortest path on the network. Ties are resolved in favor of the path that does not pass through c_{0}. During each second of time, each computer sends one signal. Each signal is sent to a randomly selected computer (the source and destination of any signal are always different). All random selections are drawn from the uniform distribution, but there may be dependencies.

(a) [2 points] Draw the graph of the network.

(b) [6 points] For each edge, calculate the expected traffic per second through the edge. Edges are bidirectional so a signal passing through the edge in either direction counts as traffic through the edge. Answer: Consider an internal edge, say {c_{0}, c_{1}}. This edge is used if computer c_{0} wants to communicate with c_{1}, which happens with probability 1/6, or if c_{1} wants to communicate with c_{0} or c_{4} which happen with probability 2/6, or if c_{4} wants to communicate with c_{1} which happens with probability 1/6. So the expected total traffic through {c_{0}, c_{1}} is 2/3. By symmetry, the expected total traffic through any inner edge is 2/3.

Now consider an external edge, say {c_{1}, c_{2}}. This edge is used if computer c_{1} wants to communicate with c_{2} or c_{3} (prob. 2/6), if c_{2} wants to communicate with c_{1} or c_{6} (prob. 2/6), if c_{3} wants to communicate with c_{1} (prob. 1/6), and if c_{6} wants to communicate with c_{2} (prob. 1/6). So the expected total traffic through {c_{1}, c_{2}} is 1. By symmetry, the expected total traffic through any external edge is 1. Note that since we are using linearity of expectation, the dependencies in signals do not affect the analysis.

Problem 11. [7 points]

A job queue is operating under the following assumptions.

1. At the start of each minute (beginning at time zero), a job is removed from the queue for processing ( if the queue is nonempty) This job is processed during the ensuing 60 seconds.

2. During the course of each minute (in between the times when jobs are removed from the queue), new jobs can arrive in the queue. The probability that one new job arrives is 1/2. The probability that two new jobs arrive is 1/4. The probability that no new jobs arrive is 1/4. The number of job arrivals at each step are mutually independent.

3. The queue overflows if it ever has 10 or more jobs.

Let R be the minute during which the queue first overflows. (If there are 10 or more jobs in the queue before we start, then R = 0).

Let J_{n} = Ex[R|n jobs in the spooler before we start]. Set up a recurrence for J_{n}. State special cases and initial conditions. Do NOT solve the recurrence

Answer:

J_{10} = 0, since the queue overflows with 10 jobs.

J_{0} = 1 + \frac{1}{4}J_{0} + \frac{1}{2}J_{1} + \frac{1}{4}J_{2}

for 1 ≤ n < 10,

J_{n} = 1 + \frac{1}{4}J_{n−1} + \frac{1}{2}J_{n} + \frac{1}{4}J_{n+1}