《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