《Mathematics for Computer》Quiz 2

6.042/18.062] Mathematics for Computer Science April 13, 2005 Srini devadas and Eric Lehman Quiz 2 YOUR NAME Calculators are not allowed on this exam You may use one 8.5 x 11"sheet with notes in your own handwriting on both side but no other sources of information 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 · The exam ends at930PM · GOOD LUCK! Problem Points Grade Grader 10 10 15 4 15 6 15 15 匚 Total_100

6.042/18.062J Mathematics for Computer Science April 13, 2005 Srini Devadas and Eric Lehman Quiz 2 YOUR NAME: • Calculators are not allowed on this exam. • You may use one 8.5 × 11” sheet with notes in your own handwriting on both sides, but no other sources of information. • 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. • The exam ends at 9:30 PM. • GOOD LUCK! Problem Points Grade Grader 1 10 2 10 3 15 4 15 5 20 6 15 7 15 Total 100

Quiz 2 NOTE: For this exam a" closed form"is a mathematical ex pression without summation notation, product notation, or the symbol Factorials and binomial coefficients may appear in a closed form. Some examples are shown below Closed forms NOT Closed Forms 42 k=0 (Vx+1 I(+)

� � � Quiz 2 2 NOTE: For this exam, a “closed form” is a mathematical ex￾pression without summation notation, product notation, or the . . . symbol. Factorials and binomial coefficients may appear in a closed form. Some examples are shown below. Closed Forms NOT Closed Forms n 42 k2 k=0 n � � n ( √x + 1) � 1 + 1 i i=1 n 1 1 1 n! + + + . . . + 3 1 2 n

Quiz 2 Problem 1. [10 points] Let S consist of all positive integers with no prime factor larger than 3, and define X Thus, the first few terms of the sum are X 1-6 12 (a)Write a closed-form expression in the box that makes the equation below true. X j=0k=0 Solution. Every positive integer with no prime factor larger than 3 has the form 3 for some nonnegative integers j and k. Thus, the expression 23k makes the equation true (b) Write a closed-form expression in the box that makes this equation true X Solution. Well apply the formula for an infinite geometric sum twice 27 j=0k=0 1-1/3 1-1 3

�� Quiz 2 3 Problem 1. [10 points] Let S consist of all positive integers with no prime factor larger than 3, and define: � 1 X = k k∈S Thus, the first few terms of the sum are: 1 1 1 1 1 1 1 1 X = + + + + + + + + . . . 1 2 3 4 6 8 9 12 (a) Write a closed­form expression in the box that makes the equation below true. ∞ ∞ X = j=0 k=0 Solution. Every positive integer with no prime factor larger than 3 has the form 2j3k for some nonnegative integers j and k. Thus, the expression 1 2j3k makes the equation true. (b) Write a closed­form expression in the box that makes this equation true: X = Solution. We’ll apply the formula for an infinite geometric sum twice. � � �∞ �∞ 1 �∞ 1 �∞ 1 = 2j3k 2j 3k j=0 k=0 j=0 �∞ 1 k=0 � 1 � = j=0 � 2j 1 1 − 1/3 ��∞ 1 = 1 − 1/3 j=0 � � � 2j � 1 1 = 1 − 1/3 1 − 1/2 = 3

Quiz 2 Problem 2. [10 points] Derive integrals that are closely-matching lower and upper bounds on the sum 1 In k k=n where n >3. Justify your answers with a diagram. Do not integrate. Your answers should be unevaluated integrals (a) Draw your diagram in the space below. To receive full credit, the diagram must clearly communicate why your integral bounds are correct Solution y In(n+1) n(2n) (b)Write your lower bound integral here ri- in( da (c)Write your upper-bound integral here 1

Quiz 2 4 Problem 2. [10 points] Derive integrals that are closely­matching lower and upper bounds on the sum � 2n 1 ln k k=n where n ≥ 3. Justify your answers with a diagram. Do not integrate. Your answers should be unevaluated integrals. (a) Draw your diagram in the space below. (To receive full credit, the diagram must clearly communicate why your integral bounds are correct.) Solution. - 6 y = 1 ln x y = 1 ln(x 1 ln n 1 ln(n 1 n) +1) +1) ln(2 n − 1 n 2n � 2n 1 (b) Write your lower bound integral here → dx n−1 ln(x+1) � 2n 1 (c) Write your upper­bound integral here → dx n−1 ln x

Quiz 2 Problem 3. [15 points] Solve the following problems involving asymptotic notation. Here Hn is the n-th harmonic number; thus, Hn=1/1+1/2+..+1/n (a) Circle all symbols on the right that could properly appear in the box on the same line. (There may be more than one!) ogn 6O90 7+1 2H In n 6OΩ 0.01 100 n 6OΩ Solution.(1)9(2)O,o(3),O,9(4)2(5)g (b) Suppose that f(n)n g(n). Beside each statement below that must be true, circle true. Beside the remaining statements, circle false f(n)2~g(m)2 true false (n)=o(g(n)) true false false f(n)=6(29(m true false Solution.(a) True.(b)True. (c) False for all f, g.(d) False. Let f(n)=n, g(n) + logn

� � � � � � Quiz 2 5 Problem 3. [15 points] Solve the following problems involving asymptotic notation. Here Hn is the n­th harmonic number; thus, Hn = 1/1 + 1/2 + . . . + 1/n. (a) Circle all symbols on the right that could properly appear in the box on the same line. (There may be more than one!) n2 log n 2 n = √ Θ O Ω o n + 1 3n − n 3 2n = Θ O Ω o 2Hn = (ln n) Θ O Ω o 0.01 n = (ln n) 100 Θ O Ω o Solution. (1) Ω (2) O, o (3) Θ, O, Ω (4) Ω (5) Ω. (b) Suppose that f(n) ∼ g(n). Beside each statement below that must be true, circle true. Beside the remaining statements, circle false. f(n) 2 ∼ g(n) 2 true false f(n) = O(g(n)) true false f(n) = o(g(n)) true false 2f(n) = Θ(2g(n) ) true false Solution. (a) True. (b) True. (c) False for all f, g. (d) False. Let f(n) = n, g(n) = n + log n

Quiz 2 Problem 4.[15 points] A misguided MIT student designs a self-replicating 6.270 robot The student builds one such robot every day, starting on day 0. The day after a robot is built, it constructs two copies of itself. (On all subsequent days, the robot busily searches for ping-pong balls--these are 6.270 robots, after all. )Here is what happens over the first few days Day 0. The student builds robot R1 Day 1. The student builds robot R2 Robot Ri builds robots Rs and R Day 2. The student builds Rs. Robot R2 builds Rs and Rr, robot R3 builds Rg and Rg, and robot R builds Rio and Rll Robot Ri searches for ping-pong balls ay 3. The student builds R12. Robots Rs,..., Rul build robots R13,., R26. Robots Ri R2, R3, and R4 search for ping-pong balls Let Tn be the number of robots in existence at the end of day n. Thus, To =l, Ti=4, T2=11,andT3=26 (a)How many new robots are built on day n-1? Express your answer in terms of the variables T-1, Tn-2,. and assume n>2. Solution. This is the difference between the number that existed on day n-1 and the number that existed on day n-2, which is Tn-1-Tn-2 (b) Express Tn with a recurrence equation and sufficient base cases. Do not solve the recurrence Solution. The number of robots on day n is equal to the number of robots on day n-1, plus twice the number of robots built yesterday (Tn-1-Tn-2), plus the 1 robot built by the student Therefore we have: T1=4 Tn=3Tn-1-2Tn-2+1(for n> 2)

Quiz 2 6 Problem 4. [15 points] A misguided MIT student designs a self­replicating 6.270 robot. The student builds one such robot every day, starting on day 0. The day after a robot is built, it constructs two copies of itself. (On all subsequent days, the robot busily searches for ping­pong balls— these are 6.270 robots, after all.) Here is what happens over the first few days: Day 0. The student builds robot R1. Day 1. The student builds robot R2. Robot R1 builds robots R3 and R4. Day 2. The student builds R5. Robot R2 builds R6 and R7, robot R3 builds R8 and R9, and robot R4 builds R10 and R11. Robot R1 searches for ping­pong balls. Day 3. The student builds R12. Robots R5, . . . , R11 build robots R13, . . . , R26. Robots R1, R2, R3, and R4 search for ping­pong balls. Let Tn be the number of robots in existence at the end of day n. Thus, T0 = 1, T1 = 4, T2 = 11, and T3 = 26. (a) How many new robots are built on day n − 1? Express your answer in terms of the variables Tn−1, Tn−2, . . . and assume n ≥ 2. Solution. This is the difference between the number that existed on day n − 1 and the number that existed on day n − 2, which is Tn−1 − Tn−2. (b) Express Tn with a recurrence equation and sufficient base cases. Do not solve the recurrence. Solution. The number of robots on day n is equal to the number of robots on day n − 1, plus twice the number of robots built yesterday (Tn−1 − Tn−2), plus the 1 robot built by the student. Therefore, we have: T0 = 1 T1 = 4 Tn = 3Tn−1 − 2Tn−2 + 1 (for n ≥ 2)

Quiz 2 (c) An even more misguided 6. 270 student designs another self-replicating robot to hunt down and destroy robots of the first kind. The number of these robots at the d of day n is Pn, where P0=0 P1=1 Pn=5Pn-1-6Pn-2+1(for n> 2) Find a closed-form expression for Pn. Show your work clearly to be eligible for rtial credit Solution. The characteristic equation is a-5r+6=0. The right side factors into (a-2)(a-3), so the roots are 2 and 3. For a particular solution, let's first guess Pn =c Substituting this into the recurrence equation gives c 5c-6c+ l, which implies that C=1/ 2. Therefore, the general form of the solution is Pn=A.2+B·3+1/2 Substituting Po=0 and Pi= l gives the equations 0=A+B+1/2 1=2A+3B+1/2 Solving this system gives A=-2 and B=3/2. Therefore, the solution is Pn +1/2

Quiz 2 7 (c) An even more misguided 6.270 student designs another self­replicating robot to hunt down and destroy robots of the first kind. The number of these robots at the end of day n is Pn, where: P0 = 0 P1 = 1 Pn = 5Pn−1 − 6Pn−2 + 1 (for n ≥ 2) Find a closed­form expression for Pn. Show your work clearly to be eligible for partial credit. 2 Solution. The characteristic equation is x − 5x + 6 = 0. The right side factors into (x − 2)(x − 3), so the roots are 2 and 3. For a particular solution, let’s first guess Pn = c. Substituting this into the recurrence equation gives c = 5c − 6c + 1, which implies that c = 1/2. Therefore, the general form of the solution is: Pn = A 2n + B 3n · · + 1/2 Substituting P0 = 0 and P1 = 1 gives the equations: 0 = A + B + 1/2 1 = 2A + 3B + 1/2 Solving this system gives A = −2 and B = 3/2. Therefore, the solution is: 3 Pn = −2 · 2n + 3n + 1/2 2 ·

Quiz 2 Problem 5.[20 points] Solve the following counting problems. Your answers must be closed forms, but need not be simplified. In particular, you may leave factorials and binomial coefficients in your answers. To be eligible for partial credit, you must explain how you arrived at your answer (a) Four card players(Alice, Bob, Carol, and Dave)are each dealt a 7-card hand from a 52-card deck In how many different ways can this be done? Solution. There is a bijection with 52-symbol sequences containing 7A's, 7B'S, 7 CS, 7Ds and 24 X's(indicating cards that remain in the deck). Thus, the number of ways to deal out the cards is 51! 24! by the bookkeeper Rule (b) Stinky Peterson has decided to start a Bug Farm under his bed. He plans to raise 100 bugs selected from four basic varieties: creepy, crawly, fuzzy, and slimey Assuming he wants at least 10 speciments of each, how many different distributions are possible?(For example, one possible distribution is 20 creepy, 20 crawly, 10 fuzzy, and 50 slimey Solution. First, he places 10 specimens of each under his bed. Then he must se- lect the remaining 60 additional speciments from the four kinds of bug. There is a bijection between such selections and 63-bit sequences with exactly 3 ones, so the number of distributions is by the bookkeeper Rule (c) There are n runners in a race. Before the race, each runner is assigned a number between 1 and n. The runners can finish the race in any one of n! different orders In how many of these orders is the first finisher not #1, the second finisher not #2, and the third finisher not #3? Solution. Let Pk be the set of finishing orders in which runner #k is is the k-th finisher. In these terms, the solution n!-|B∪PUB=m!-(|f|+|P|+|B3 B∩P2-|B1∩P3-|P2∩P3 +|f∩P2∩P3|) n!-3(n-1)!+3(mn-2)!-(n-3)! (d) How many ways are there to park 4 identical SU Vs and 10 identical cars in a row of 20 parking spaces if SUVs are too wide to park next to each other? For example, here is one parking possibilit

Quiz 2 8 Problem 5. [20 points] Solve the following counting problems. Your answers must be closed forms, but need not be simplified. In particular, you may leave factorials and binomial coefficients in your answers. To be eligible for partial credit, you must explain how you arrived at your answer. (a) Four card players (Alice, Bob, Carol, and Dave) are each dealt a 7­card hand from a 52­card deck. In how many different ways can this be done? Solution. There is a bijection with 52­symbol sequences containing 7 A’s, 7 B’s, 7 C’s, 7 D’s and 24 X’s (indicating cards that remain in the deck). Thus, the number of ways to deal out the cards is 51! 7!4 24! by the Bookkeeper Rule. (b) Stinky Peterson has decided to start a Bug Farm under his bed. He plans to raise 100 bugs selected from four basic varieties: creepy, crawly, fuzzy, and slimey. Assuming he wants at least 10 speciments of each, how many different distributions are possible? (For example, one possible distribution is 20 creepy, 20 crawly, 10 fuzzy, and 50 slimey.) Solution. First, he places 10 specimens of each under his bed. Then he must se￾lect the remaining 60 additional speciments from the four kinds of bug. There is a bijection between such selections and 63­bit sequences with exactly 3 ones, so the number of distributions is � � 63! 63 = 60! 3! 60 by the Bookkeeper Rule. (c) There are n runners in a race. Before the race, each runner is assigned a number between 1 and n. The runners can finish the race in any one of n! different orders. In how many of these orders is the first finisher not #1, the second finisher not #2, and the third finisher not #3? Solution. Let Pk be the set of finishing orders in which runner #k is is the k­th finisher. In these terms, the solution is: n! − |P1 ∪ P2 ∪ P3| = n! − (| | | | | | P1 + P2 + P3 − | | − | P1 ∩ P2 P1 ∩ P3| − | | P2 ∩ P3 + |P1 ∩ P2 ∩ P3|) = n! − 3(n − 1)! + 3(n − 2)! − (n − 3)! (d) How many ways are there to park 4 identical SUVs and 10 identical cars in a row of 20 parking spaces if SUVs are too wide to park next to each other? For example, here is one parking possibility:

Quiz 2 car car vrr Solution. First, let's park the SUVs. The number of ways to do this is equal to the number of ways to select 20 books off of a shelf such that adjacent books are not selected-a problem of a type you' ve seen before. The answer is(4). Now the 10 cars can be parked in the remaining g spaces in (10)ways. So the total number of parking possibilities is (e)A mobile is a hanging structure built from seven horizontal rods (indicated with solid lines), seven vertical strings(indicated with dotted lines), and eight toys (indi cated with the letters A-h B C D E Many different toy arrangements can be obtained by twisting the strings. For ex ample, twisting the string marked with the arrow would swap toys A and B Twisting the string marked with the +arrow would reverse the order of toys e, F, G, and H On the other hand, no combination of twists swaps only toys b and C. Two mobiles are different if one can not be obtained from the other by twisting strings. How many different mobiles are possible? Solution. There are 8! different sequences of toys. Each mobile can be configured in 2 different ways, by twisting or not twisting the 7 upper strings. Thus, there is a 2-to-1 mapping from sequences to mobiles. By the Division Rule, the number of different mobiles is 8! /2=315

� � � � � � � � Quiz 2 9 S c c c S c S c c c c S c c U a a a U a U a a a a U a a V r r r V r V r r r r V r r Solution. First, let’s park the SUVs. The number of ways to do this is equal to the number of ways to select 20 books off of a shelf such that adjacent books are not selected— a problem of a type you’ve seen before. The answer is 17 . Now the 10 4 cars can be parked in the 16 remaining spaces in 16 ways. So the total number of 10 parking possibilities is: 17 16 4 · 10 (e) A mobile is a hanging structure built from seven horizontal rods (indicated with solid lines), seven vertical strings (indicated with dotted lines), and eight toys (indi￾cated with the letters A­H).   - A B C D E F G H Many different toy arrangements can be obtained by twisting the strings. For ex￾ample, twisting the string marked with the → arrow would swap toys A and B. Twisting the string marked with the ← arrow would reverse the order of toys E, F, G, and H. On the other hand, no combination of twists swaps only toys B and C. Two mobiles are different if one can not be obtained from the other by twisting strings. How many different mobiles are possible? Solution. There are 8! different sequences of toys. Each mobile can be configured in 27 different ways, by twisting or not twisting the 7 upper strings. Thus, there is a 27­to­1 mapping from sequences to mobiles. By the Division Rule, the number of different mobiles is 8!/27 = 315.  

Quiz 2 10 Problem 6. [15 points] A subsequence is obtained from a sequence by deleting one or more terms. For example, the sequence(1, 2, 3, 4, 5)contains(2, 4, 5) as a subsequence Theorem. Every sequence of n2+ 1 distinct integers contains an increasing or decreasing subse- quence of length n+1 For example, in the 3+1= 10 term sequence(5,6,1, 4, 9, 0, 2, 7, 8, 3), the underlined terms increasing sequence of length 3+1=4. Fill in the outline of a proof provided OW Proof (a)label each term in the sequence with the length of the longest increasing subse quence that ends with that term. For example, here is a sequence with the corre- ponding labels listed below. 121口□口口□□ Solution 2,1,2,2,3,1,3,2,3 (b) Now there are two cases. If some term is labeled n+l or higher, then the theorem is true because Solution. this means there is an increasing sequence of length at least n+1 that ends with that term (c)Otherwise, at least n+ 1 terms must have the same label b E 1, 2 Solution. of the Pigeonhole Principle. Regard the labels a pigeons and the numbers 1, 2,..., n as pigeonholes. Assign each label to its value. Since there are n2+1 pigeons and only n pigeonholes, some n+ I pigeons must be assigned to some hole (d ) The theorem is also true in this case because Solution. Each of the n l terms labeled b must be smaller than the one befo (Otherwise, a term labeled b could be appended to the length-b increasing sequence that ends at its predecessor to obtain a length-(6+ 1)increasing sequence. But then the term should actually be labeled b+ 1. ) Therefore, the n+ l terms labeled b form a decreasing subsequence

� Quiz 2 10 Problem 6. [15 points] A subsequence is obtained from a sequence by deleting one or more terms. For example, the sequence (1, 2, 3, 4, 5) contains (2, 4, 5) as a subsequence. Theorem. Every sequence of n2 + 1 distinct integers contains an increasing or decreasing subse￾quence of length n + 1. For example, in the 32+1 = 10 term sequence (5, 6, 1, 4, 9, 0, 2, 7, 8, 3), the underlined terms form an increasing sequence of length 3 + 1 = 4. Fill in the outline of a proof provided below. Proof. (a) Label each term in the sequence with the length of the longest increasing subse￾quence that ends with that term. For example, here is a sequence with the corre￾ponding labels listed below. ( 2, 6, 1, 5, 4, 9, 0, 8, 3, 7 ) 1 2 1 Solution. 1, 2, 1, 2, 2, 3, 1, 3, 2, 3 (b) Now there are two cases. If some term is labeled n+1 or higher, then the theorem is true because Solution. this means there is an increasing sequence of length at least n + 1 that ends with that term. (c) Otherwise, at least n + 1 terms must have the same label b ∈ {1, 2, . . . , n} because Solution. of the Pigeonhole Principle. Regard the labels a pigeons and the numbers 1, 2, . . . , n as pigeonholes. Assign each label to its value. Since there are n2 + 1 pigeons and only n pigeonholes, some n + 1 pigeons must be assigned to some hole b. (d) The theorem is also true in this case because Solution. Each of the n + 1 terms labeled b must be smaller than the one before. (Otherwise, a term labeled b could be appended to the length­b increasing sequence that ends at its predecessor to obtain a length­(b + 1) increasing sequence. But then the term should actually be labeled b + 1.) Therefore, the n + 1 terms labeled b form a decreasing subsequence