《Mathematics for Computer》Final exam

6.042/18.062] Mathematics for Computer Science May16,2005 Srini devadas and Eric Lehman Final exam YOUR NAME This is an open-notes exam However, calculators are not allowed You may assume all results from lecture the notes, problem sets and recitation Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them · GOOD LUCK! Problem Points Grade Grader 10 10 10 15 10 8 10 10 Total 100

6.042/18.062J Mathematics for Computer Science May 16, 2005 Srini Devadas and Eric Lehman Final Exam YOUR NAME: • This is an open­notes exam. However, calculators are not allowed. • You may assume all results from lecture, the notes, problem sets, and recitation. • Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. • Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them. • GOOD LUCK! Problem Points Grade Grader 1 15 2 10 3 10 4 10 5 10 6 15 7 10 8 10 9 10 Total 100

Problem 1. [15 points] Consider the following sequence of predicates Q1(x1)=x1 Q2(x1,x2)=x1→m2 Q Q4(x1,x2,x3,x4)=(x1→x2)→x3)→4 Q5(x1,x2,x3,x4,x5)=(x1→x2)→x3)→x4)→5 Let Tn be the number of different true/false settings of the variables T1, 2,.. In for which Qn(a1, T2,..., n)is true. For example, T2= 3 since Q2(1, T2) is true for 3 different settings of the variables f1 and 2: TT TFF FTF TFTT FF T (a) Express Tn+1 in terms of Tn, assuming n> 1 Solution We have n+1(T1,x 1)=Qn( If an+1 is true, then Qn+1 is true for all 2n settings of the variables 1, 2, .. In. If n+i is false, then Qn+i is true for all settings of c1, 12, .. n except for the Tn settings that make Qn true. Thus, altogether we have 21+21-Tn=2 n (b)Use induction to prove that Tn=3(2n++(1)m) for n> 1. You may assume your answer to the previous part without proof Solution. The proof is by induction. Let P(n) be the proposition that Tn=(2n++ Base case: There is a single setting of 1 that makes Q1(a1)=1 true, and Ti 1))/3=1. Therefore, P(O)is true Inductive step: For n>0, we assume P(n)and reason as follows Tn+1=2+1-Tn 2n+2+(-1)x+1 3 The first step uses the result from the previous problem part, the second uses the induction hypothesis P(n), and the third is simplification. This implies that P(n+1 is true. By the principle of induction, P(n) is true for alln> 1

� � Final Exam 2 Problem 1. [15 points] Consider the following sequence of predicates: Q1(x1) = x1 Q2(x1, x2) = x1 ⇒ x2 Q3(x1, x2, x3) = (x1 ⇒ x2) ⇒ x3 Q4(x1, x2, x3, x4) = ((x1 ⇒ x2) ⇒ x3) ⇒ x4 Q5(x1, x2, x3, x4, x5) = (((x1 ⇒ x2) ⇒ x3) ⇒ x4) ⇒ x5 . . . . . . Let Tn be the number of different true/false settings of the variables x1, x2, . . . , xn for which Qn(x1, x2, . . . , xn) is true. For example, T2 = 3 since Q2(x1, x2) is true for 3 different settings of the variables x1 and x2: Q2(x1, x2) T T T F F T F F x1 x2 T F T T (a) Express Tn+1 in terms of Tn, assuming n ≥ 1. Solution. We have: Qn+1(x1, x2, . . . , xn+1) = Qn(x1, x2, . . . , xn) ⇒ xn+1 If xn+1 is true, then Qn+1 is true for all 2n settings of the variables x1, x2, . . . , xn. If xn+1 is false, then Qn+1 is true for all settings of x1, x2, . . . , xn except for the Tn settings that make Qn true. Thus, altogether we have: n Tn+1 = 2n + 2 − Tn = 2n+1 − Tn 1 (b) Use induction to prove that Tn = 3 (2n+1 + (−1)n) for n ≥ 1. You may assume your answer to the previous part without proof. Solution. The proof is by induction. Let P(n) be the proposition that Tn = (2n+1 + (−1)n)/3. Base case: There is a single setting of x1 that makes Q1(x1) = x1 true, and T1 = (21+1 + (−1)1)/3 = 1. Therefore, P(0) is true. Inductive step: For n ≥ 0, we assume P(n) and reason as follows: Tn+1 = 2n+1 − Tn n 2n+1 + (−1) = 2n+1 − 3 n+1 2n+2 + (−1) = 3 The first step uses the result from the previous problem part, the second uses the induction hypothesis P(n), and the third is simplification. This implies that P(n+1) is true. By the principle of induction, P(n) is true for all n ≥ 1

Final exan Problem 2. [10 points] There is no clock in my kitchen. However The faucet drips every 54 seconds after i shut off the water The toaster pops out toast every 87 seconds after I plug it in I'd like to fry an egg for exactly 141 seconds. My plan is to plug in the toaster and shut off the faucet at the same instant I'll start kxP-tn tme. What values of D and Pmake and stop frying when the toaster pops for theng when the faucet drips for the D-th time this plan work? D P Reminder: Calculators are not allowed Solution. The Pulverizer gives 5-87-854=3. Multiplying by 47 gives 235·87-376·54=141 →235.87=141+376·54 Thus, I'll start frying after at drip D=376 and stop 141 seconds later at pop P=87

Final Exam 3 Problem 2. [10 points] There is no clock in my kitchen. However: • The faucet drips every 54 seconds after I shut off the water. • The toaster pops out toast every 87 seconds after I plug it in. I’d like to fry an egg for exactly 141 seconds. My plan is to plug in the toaster and shut off the faucet at the same instant. I’ll start frying when the faucet drips for the D­th time and stop frying when the toaster pops for the P­th time. What values of D and P make this plan work? D = P = Reminder: Calculators are not allowed. Solution. The Pulverizer gives 5 · 87 − 8 · 54 = 3. Multiplying by 47 gives: 235 · 87 − 376 · 54 = 141 ⇒ 235 · 87 = 141 + 376 · 54 Thus, I’ll start frying after at drip D = 376 and stop 141 seconds later at pop P = 87

Final exan Problem 3. [10 points] Circle either true or false next to each statement below. Assume graphs are undirected without self-loops or multi-edges 1. For all n > 3, the complete graph on n vertices has an Euler false 2. If a graph contains no odd-length cycle, then it is bipartite true 3. Every non-bipartite graph contains a 3-cycle as a subgraph false 4. Every graph with a Hamiltonian cycle also has an Euler tour 5. There exists a graph with 20 vertices, 10 edges, and 5 con- false nected component 6. Every connected graph has a tree as a subgraph true 7. In every planar embedding of a connected planar graph, the true number of vertices plus the number of faces is greater than the number of edges 8. If every girl likes at least 2 boys, then every girl can be false matched with a boy she likes 9. If every vertex in a graph has degree 3, then the graph is 4-true colorable 10. There exists a six-vertex graph with vertex degrees 0, 1, 2, 3, false 4, and 5

Final Exam 4 Problem 3. [10 points] Circle either true or false next to each statement below. Assume graphs are undirected without self­loops or multi­edges. 1. For all n ≥ 3, the complete graph on n vertices has an Euler false tour. 2. If a graph contains no odd­length cycle, then it is bipartite. true 3. Every non­bipartite graph contains a 3­cycle as a subgraph. false 4. Every graph with a Hamiltonian cycle also has an Euler tour. false 5. There exists a graph with 20 vertices, 10 edges, and 5 con­ false nected components. 6. Every connected graph has a tree as a subgraph. true 7. In every planar embedding of a connected planar graph, the true number of vertices plus the number of faces is greater than the number of edges. 8. If every girl likes at least 2 boys, then every girl can be false matched with a boy she likes. 9. If every vertex in a graph has degree 3, then the graph is 4­ true colorable. 10. There exists a six­vertex graph with vertex degrees 0, 1, 2, 3, false 4, and 5

Final exan Problem 4.[10 points] In the final round of the World Cup, 16 teams play a single elimination tournament The teams are called A,B,C,.. P The tournament consists of a sequence of rounds In each round, the teams are paired up and play matches The losers are eliminated, and the winners advance to the next round The tournament ends when there is only one team left For example, three possible single-elimination tournaments are depicted below ABCDEFGH A BAC A D ACGE0 KCJDLBPIEF B E B E E B F P E P E E A L A H MNOP F Two tournaments are the same if the same matches are played and won by the same teams For example, the first and second tournaments shown above are the same, but the third is different. How many different tournaments are possible? Solution. Suppose that we draw the tournament so that the winning team in each game is listed above the losing team. Then the ordering of teams on the left completely determines all matches and winners. Therefore, there are 16! single-elimination tourn ments Another approach is to use a result from earlier in the course: the number of ways to pair up 2n people is(2n)! /n! 2. In a single-elimination tournament, we must pair up 16 teams, determine who wins the 8 matches between them, then pair up the 8 winning teams, detrmine who wins the 4 matches, and so forth. The number of ways in which this can be done is 4!24 2!22

@@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� @@ �� 5 C I L Final Exam Problem 4. [10 points] In the final round of the World Cup, 16 teams play a single￾elimination tournament. • The teams are called A, B, C, . . . , P. • The tournament consists of a sequence of rounds. – In each round, the teams are paired up and play matches. – The losers are eliminated, and the winners advance to the next round. – The tournament ends when there is only one team left. For example, three possible single­elimination tournaments are depicted below: B A E E D B E H C D B P E A H M K C J D L B P I E F O A H G M N A I A E M I A C G E O M K I B A C D G H F E P O N M L K J I A A I A E M I A C E G I K M O A B D E M F G H K J Two tournaments are the same if the same matches are played and won by the same teams. For example, the first and second tournaments shown above are the same, but the third is different. How many different tournaments are possible? Solution. Suppose that we draw the tournament so that the winning team in each game is listed above the losing team. Then the ordering of teams on the left completely determines all matches and winners. Therefore, there are 16! single­elimination tourna￾ments. Another approach is to use a result from earlier in the course: the number of ways to pair up 2n people is (2n)!/n! 2n. In a single­elimination tournament, we must pair up 16 teams, determine who wins the 8 matches between them, then pair up the 8 winning teams, detrmine who wins the 4 matches, and so forth. The number of ways in which this can be done is: 16! 8! 4! 2! 28 24 22 21 = 16! 8! 28 · · 4! 24 · · 2! 22 · · 1! 21 · N O P C C C C C C
C

C C
AA H  H A H  H A
A
AA A A A A

H  H C H  H HH  H  H HH 
H  H C C
C

C C
A A
AA H  H HH A  AA

H  H C C
C
C

C H  H H  H H  H HH 
H  H C A A
AA H  H HH  AA H  H H  H

H  H H  H H  H HH 

Final exan A final alternative is to use the general Product rule. The champions can be chosen in 16 ways, the other finalists in 15 ways, the semi-finalist that played the champions in 14 ways,the other semi-finalist in 13 ways, and so forth. In all, this gives 16! tournaments

Final Exam 6 A final alternative is to use the General Product Rule. The champions can be chosen in 16 ways, the other finalists in 15 ways, the semi­finalist that played the champions in 14 ways, the other semi­finalist in 13 ways, and so forth. In all, this gives 16! tournaments again

Final exan Problem 5. [10 points] There are 3 children of different ages. What is the probability that at least two are boys, given that at least one of the two youngest children is a boy? Assume that each child is equally likely to be a boy or a girl and that their genders are mutually independent. A correct answer alone is sufficient. However, to be eligible for partial credit, you must include a clearly-labeled tree diagram Solution. Let M be the event that there are at least two boys and let y be the event that at least one of the two youngest children is a boy. In the tree diagram below, all edge probabilities are 1 /2 B B B<GB 11111 22222222 youngest oldest M Y Prob Pr(My Pr(M∩Y)

Final Exam 7 Problem 5. [10 points] There are 3 children of different ages. What is the probability that at least two are boys, given that at least one of the two youngest children is a boy? Assume that each child is equally likely to be a boy or a girl and that their genders are mutually independent. A correct answer alone is sufficient. However, to be eligible for partial credit, you must include a clearly­labeled tree diagram. Solution. Let M be the event that there are at least two boys, and let Y be the event that at least one of the two youngest children is a boy. In the tree diagram below, all edge probabilities are 1/2. �� � HH B H B G × × × × 1/2 1/2





@@ @ HHH B G B G × × × 1/2 1/2 A A A A A A�� � HHH G B B G × × × 1/2 1/2 @ @ @ HHH G B G 1/2 1/2 youngest oldest M Y Prob Pr (M | Y ) = Pr (M ∩ Y ) Pr (Y ) 1/2 = 3/4 = 2/3

Problem 6.[15 points] On the morning of day 1, i put a gray document on my desk. This creates a stack of height 1 Dn each subsequent morning, I insert a white document into the stack at a position se- lected uniformly at random. For example, the stack might look like this on the evening of day 5 Then, on the following morning I would insert a white document at one of the six posi tions indicated above with equal probability Let the random variable bn be the number of white documents below the gray docu ment on day n. (a) Express Pr(Bn+1=0)in terms of Pr(Bn=0) (Bn+1=0) Solution Pr(Bn+1=0) Pr(Bn=0) (b) Express Pr(Bn+1=n)in terms of Pr(Bn =n-1) Pr(Bn+1= n Solution Pr(B

Final Exam 8 Problem 6. [15 points] On the morning of day 1, I put a gray document on my desk. This creates a stack of height 1: On each subsequent morning, I insert a white document into the stack at a position se￾lected uniformly at random. For example, the stack might look like this on the evening of       day 5: Then, on the following morning, I would insert a white document at one of the six posi￾tions indicated above with equal probability. Let the random variable Bn be the number of white documents below the gray docu￾ment on day n. (a) Express Pr(Bn+1 = 0) in terms of Pr(Bn = 0). Pr(Bn+1 = 0) = Solution. n Pr(Bn+1 = 0) = Pr(Bn = 0) n + 1 (b) Express Pr(Bn+1 = n) in terms of Pr(Bn = n − 1). Pr(Bn+1 = n) = Solution. n Pr(Bn+1 = n) = Pr(Bn = n − 1) n + 1

(c) Express Pr(Bn+1=k)in terms of Pr(Bn= k)and Pr(Bn=k-1)assuming that 0<k< Pr(Bn+1=k) Solution Pr(Bn,=b⊥n-k Pr(B2+1=k) n+ k-1)

Final Exam 9 (c) Express Pr (Bn+1 = k) in terms of Pr (Bn = k) and Pr (Bn = k − 1) assuming that 0 < k < n. Pr (Bn+1 = k) = Solution. k Pr (Bn+1 = k) = n − k Pr (Bn+1 = k) + Pr (Bn+1 = k − 1) n + 1 n + 1

Final exan (d) Use induction to prove that Bn is uniformly distributed on (0, 1, 2,.,n-1 You may assume your answers to the preceding problem parts without justification Solution. We use induction. Let P(n)be the proposition that Bn is uniformly dis- ibuted on the set (0, 1, 2 Base case. The random variable Bi is always equal to O, so it is uniformly distributed Inductive step. Assume that the random variable Bn is uniformly distributed on the set 0, 1, 2,..., n-1 and consider the random variable B,+1. There are three cases n Pr(Br 0) n+1 Pr(Bn=0 n+in 1 n+1 n Pr(B +1 Pr(Bn=n-1) n+ln Pr(Bn+1= k n-k1 k 1 1n+n+1 +1 n each case, the first equation comes from the preceding problem parts. We use the induction hypotheses on the starred lines. The remaining steps are simplfica tions. This shows that Bn+i is uniformly distributed and the claim follows from the principle of induction

Final Exam 10 (d) Use induction to prove that Bn is uniformly distributed on {0, 1, 2, . . . , n − 1}. You may assume your answers to the preceding problem parts without justification. Solution. We use induction. Let P(n) be the proposition that Bn is uniformly dis￾tributed on the set {0, 1, 2, . . . , n − 1}. Base case. The random variable B1 is always equal to 0, so it is uniformly distributed on {0}. Inductive step. Assume that the random variable Bn is uniformly distributed on the set {0, 1, 2, . . . , n − 1} and consider the random variable Bn+1. There are three cases: n Pr (Bn+1 = 0) = Pr (Bn = 0) n + 1 n 1 = (*) n + 1 n 1 = n + 1 n Pr (Bn+1 = n) = Pr (Bn = n − 1) n + 1 n 1 = (*) n + 1 n 1 = n + 1 k Pr (Bn+1 = k) = n − k Pr (Bn+1 = k) + Pr (Bn+1 = k − 1) n + 1 n + 1 1 k 1 = n − k + (*) n + 1 n n + 1 n 1 = n + 1 In each case, the first equation comes from the preceding problem parts. We use the induction hypotheses on the starred lines. The remaining steps are simplfica￾tions. This shows that Bn+1 is uniformly distributed, and the claim follows from the principle of induction