《Mathematics for Computer》Problem Set 8 Solutions

6.042/18.] Mathematics for Computer Science April 5, 2005 Srini devadas and Eric Lehman Problem set 8 Solutions Due: Monday, April ll at 9 PM Problem 1. An electronic toy displays a 4 x 4 grid of colored squares. At all times, four are red, four are green, four are blue, and four are yellow. For example, here is one possible configuration: RIBIYIR BGG BRIRG BGYY ①②③ (a)How many such configurations are possible? Solution. This is equal to the number of sequences containing 4R's, 4Gs, 4 B's and 4Y's, which is 16 (4!)4 (b)Below the display, there are five buttons numbered 1, 2, 3, 4, and 5. The player may press a sequence of buttons; however, the same button can not be pressed twice in a row. How many different sequences of n button- presses are possible? Solution. There are 5 choices for the first button press and 4 for each subsequence press. Therefore, the number of different sequences of n button presses is 5. 4 (c) Each button press scrambles the colored squares in a complicated, but nonran dom way. Prove that there exist two different sequences of 32 button presses that both produce the same configuration, if the puzzle is initially in the state shown above Solution. We use the Pigeonhole Principle. Let A be the set of all sequences of 32 button presses, let b be the set of all configurations, and let f: A-B map each sequence of button presses to the configuration that results. Now: 4|>42>16!>|B

6.042/18.062J Mathematics for Computer Science April 5, 2005 Srini Devadas and Eric Lehman Problem Set 8 Solutions Due: Monday, April 11 at 9 PM Problem 1. An electronic toy displays a 4×4 grid of colored squares. At all times, four are red, four are green, four are blue, and four are yellow. For example, here is one possible configuration: ' $ R B Y R Y B G G B R R G B G Y Y  & 1  2  3  4  5 % (a) How many such configurations are possible? Solution. This is equal to the number of sequences containing 4 R’s, 4 G’s, 4 B’s, and 4 Y’s, which is: 16! (4!)4 (b) Below the display, there are five buttons numbered 1, 2, 3, 4, and 5. The player may press a sequence of buttons; however, the same button can not be pressed twice in a row. How many different sequences of n button­presses are possible? Solution. There are 5 choices for the first button press and 4 for each subsequence press. Therefore, the number of different sequences of n button presses is 5 4n−1 · . (c) Each button press scrambles the colored squares in a complicated, but nonran￾dom way. Prove that there exist two different sequences of 32 button presses that both produce the same configuration, if the puzzle is initially in the state shown above. Solution. We use the Pigeonhole Principle. Let A be the set of all sequences of 32 button presses, let B be the set of all configurations, and let f : A B map each sequence of button presses to the configuration that results. Now: → |A| > 4 > 16! > |B 32 |

Problem Set 8 hus, by the Pigeonhole Principle, f is not injective; that is, there exist distinct el- ements a1, a2 E A such taht f(ai=f(a2). In other words, there are two different sequences of button presses that produce the same configuration Problem 2. Suppose you have five 6-sided dice, which are colored red, blue, green, white, and black. a roll is a sequence specifying a value for each die. For example, one roll is red green blue white black For the problems below, you do not need to simpify your answers, but briefly explain your reasoning (a) For how many rolls is the value on every die different? Example: (1, 2, 3, 4, 5)is a roll of this type, but(1,1, 2, 3, 4)is not Solution. The number of such rolls is6·5·4·3.2 (b) For how many rolls do two dice have the same value and the remaining three dice all have different values? Example:(6, 1,6, 2, 3)is a roll of this type, but(, 1, 2, 2, 3)and(4, 4, 4, 5, 6)are not Solution. There are possible pairs of rolls that might have the same value and 6 possibilities for what this value is. There 5. 4.3 possible distinct values for the remaining three rolls. So the number of rolls of this type is 6·5·4·3 (c) For how many rolls do two dice have one value two different dice have a second value, and the remaining die a third value? Example:(6, 1, 2, 1, 2)is a roll of this type, but (4, 4, 4, 4, 5)and(5, 5, 5, 6, 6)are not Solution. There are (2)sets of two values that might be duplicated. There are( 2) rolls where larger duplicated value may come up and ) remaining rolls where the smaller duplicated value may come up. There is only 1 remaining roll where the nonduplicated value may then come up, and 4 remaining values it could take. So, the number of rolls of this ty (( m problem concerns seven card hands dealt from a regular 52-card deck

� � � � � � � � � � � � � � � � 2 Problem Set 8 Thus, by the Pigeonhole Principle, f is not injective; that is, there exist distinct el￾ements a1, a2 ∈ A such taht f(a1) = f(a2). In other words, there are two different sequences of button presses that produce the same configuration. Problem 2. Suppose you have five 6­sided dice, which are colored red, blue, green, white, and black. A roll is a sequence specifying a value for each die. For example, one roll is: ( 3 , 1 , 4 , 1 , 5 ���� ���� ���� ���� ����) red green blue white black For the problems below, you do not need to simpify your answers, but briefly explain your reasoning. (a) For how many rolls is the value on every die different? Example: (1, 2, 3, 4, 5) is a roll of this type, but (1, 1, 2, 3, 4) is not. Solution. The number of such rolls is 6 5 4 3 2 · · · · (b) For how many rolls do two dice have the same value and the remaining three dice all have different values? Example: (6, 1, 6, 2, 3) is a roll of this type, but (1, 1, 2, 2, 3) and (4, 4, 4, 5, 6) are not. Solution. There are 5 2 possible pairs of rolls that might have the same value and 6 possibilities for what this value is. There 5 4 3 · · possible distinct values for the remaining three rolls. So the number of rolls of this type is 5 6 5 4 3 2 · · · · (c) For how many rolls do two dice have one value, two different dice have a second value, and the remaining die a third value? Example: (6, 1, 2, 1, 2) is a roll of this type, but (4, 4, 4, 4, 5) and (5, 5, 5, 6, 6) are not. Solution. There are 6 2 sets of two values that might be duplicated. There are 5 2 rolls where larger duplicated value may come up and 3 2 remaining rolls where the smaller duplicated value may come up. There is only 1 remaining roll where the nonduplicated value may then come up, and 4 remaining values it could take. So, the number of rolls of this type is: 6 5 3 4 2 · 2 · 2 · Problem 3. This problem concerns seven card hands dealt from a regular 52­card deck

Problem set 8 (a) How many different hands are possible? Solution. There is one hand for each way of choosing 7 cards from a 52-card deck Therefore, the number of possible hands is by the subset rule (b)How many hands contain three pairs and no three-of-a-kind or four-of-a-kind? Solution. There is a bijection with sequences specifying The values of the pairs, which can be chosen in(3)ways The suits of the lowest-value pair, which can be chosen in(2)ways The suits of the middle-value pair, which can be chosen in(2)ways The suits of the highest-value pair, which can be chosen in ()ways The value of the remaining card, which can be chosen in 10 ways The suit of the remaining card, which can be chosen in 4 ways Thus, the number of seven-card poker hands containing three pairs and no three or four-of-a-kind is 13 By the Generalized Product rule (c) How many hands have all cards of the same suit? Solution. There is a bijection with sequences specifying: The suit of all the cards, which can be chosen in 4 ways The values of the cards, which can be chosen in(3)ways So the seven cards can be chosen in 4()ways (d) How many hands have 5 or more face cards?(The jacks, queens, and kings are the face cards) Solution. There is a bijection between hands with exactly k face cards and pairs consisting of: A set of k face cards, which can be chosen in(k)ways A set of 7-h numbered cards, which can be chosen in(-_k)ways

� � � � � � � � � � � � � � � � � � Problem Set 8 3 (a) How many different hands are possible? Solution. There is one hand for each way of choosing 7 cards from a 52­card deck. Therefore, the number of possible hands is: 52 7 by the Subset Rule. (b) How many hands contain three pairs and no three­of­a­kind or four­of­a­kind? Solution. There is a bijection with sequences specifying: 13 • The values of the pairs, which can be chosen in ways. 3 • The suits of the lowest­value pair, which can be chosen in 4 2 ways. • The suits of the middle­value pair, which can be chosen in 4 2 ways. • The suits of the highest­value pair, which can be chosen in 4 2 ways. • The value of the remaining card, which can be chosen in 10 ways. • The suit of the remaining card, which can be chosen in 4 ways. Thus, the number of seven­card poker hands containing three pairs and no three or four­of­a­kind is: � � � �3 13 4 10 · 4 3 · 2 · By the Generalized Product Rule. (c) How many hands have all cards of the same suit? Solution. There is a bijection with sequences specifying: • The suit of all the cards, which can be chosen in 4 ways. 13 • The values of the cards, which can be chosen in ways. 7 13 So the seven cards can be chosen in 4 · ways. 7 (d) How many hands have 5 or more face cards? (The jacks, queens, and kings are the face cards.) Solution. There is a bijection between hands with exactly k face cards and pairs consisting of: • A set of k face cards, which can be chosen in 12 ways. k • A set of 7 − k numbered cards, which can be chosen in 40 ways. 7−k

Problem Set 8 Thus, there are(k)(-) hands with exactly k face cards. By the Sum Rule, there are 12\/40 12)/40 7八(0 hands with 5, 6, or 7 face cards Problem 4. The lecture notes describe a magic trick in which the audience selects 5 card from a deck, the Assistant reveals 4 of these cards in some order, and the Magician deter- mines the last card Now suppose there are two decks of cards, one with blue backs and one with green backs. As before, the audience selects 5 cards. The assistant reveals 4 of these cards in ome order. The Magician is allowed to look at both sides of these cards. The Magician must determine the suit, value, and back-color of the remaining card (a) Prove that this is possible Solution. Construct a bipartite graph with a vertex on the left for every possible set of 5 cards and a vertex on the right for every possible sequence of 4 cards. Put an edge between a set of 5 cards and a sequence of 4 if every card in the sequence is also in the set. In other words there is an edge between a set of 5 cards and a sequence of 4 if the Assistant can reveal that sequence of 4 provided the audience selects that set of 5 Now the magic trick is possible if there is a matching for the vertices on the left. Specifically, thethe audience picks a set of 5 cards. Then the assistant reveals the matching sequence of 4 cards. Finally, the Magician names the remaining card in the matched se We can prove the existence of the required matching using Hall,s Theorem directly (as in the notes)or with a corollary(as in lecture) Corollary. If every vertex on the left side of a bipartite graph has degree c and every vertex on the right has degree d, then there is a matching for the left vertices ifc>d>0 Here well use the corollary. In this case, each vertex on the left has degree c=5.4 2=120, since the Assistant can reveal any one of 5 cards first, 4 cards second, 3 cards third, and 2 cards last. Each vertex on the right has degree d=104-4=100, since the fifth card can be any card in the two decks other than the four in the sequence atching for the vertices on the left exists by the corollary, and the trick car (b) Extra credit: Describe a practical way to perform this trick. (We have no solution to this problem! Problem 5. Miss McGillicuddy never goes outside without a collection of pets. In partic

� �� � � �� � � �� � � �� � 4 Problem Set 8 40 Thus, there are 12 hands with exactly k face cards. By the Sum Rule, there are k 7−k 12 40 12 40 12 40 + + 5 2 6 1 7 0 hands with 5, 6, or 7 face cards. Problem 4. The lecture notes describe a magic trick in which the audience selects 5 cards from a deck, the Assistant reveals 4 of these cards in some order, and the Magician deter￾mines the last card. Now suppose there are two decks of cards, one with blue backs and one with green backs. As before, the audience selects 5 cards. The Assistant reveals 4 of these cards in some order. (The Magician is allowed to look at both sides of these cards.) The Magician must determine the suit, value, and back­color of the remaining card. (a) Prove that this is possible. Solution. Construct a bipartite graph with a vertex on the left for every possible set of 5 cards and a vertex on the right for every possible sequence of 4 cards. Put an edge between a set of 5 cards and a sequence of 4 if every card in the sequence is also in the set. In other words, there is an edge between a set of 5 cards and a sequence of 4 if the Assistant can reveal that sequence of 4 provided the audience selects that set of 5. Now the magic trick is possible if there is a matching for the vertices on the left. Specifically, the the audience picks a set of 5 cards. Then the Assistant reveals the matching sequence of 4 cards. Finally, the Magician names the remaining card in the matched set. We can prove the existence of the required matching using Hall’s Theorem directly (as in the notes) or with a corollary (as in lecture): Corollary. If every vertex on the left side of a bipartite graph has degree c and every vertex on the right has degree d, then there is a matching for the left vertices if c ≥ d > 0. Here we’ll use the corollary. In this case, each vertex on the left has degree c = 5·4·3· 2 = 120, since the Assistant can reveal any one of 5 cards first, 4 cards second, 3 cards third, and 2 cards last. Each vertex on the right has degree d = 104 − 4 = 100, since the fifth card can be any card in the two decks other than the four in the sequence. So a matching for the vertices on the left exists by the corollary, and the trick can be done. (b) Extra credit: Describe a practical way to perform this trick. (We have no solution to this problem!) Problem 5. Miss McGillicuddy never goes outside without a collection of pets. In partic￾ular:

Problem set 8 She brings 3, 4, or 5 dogs She brings a positive number of songbirds, which always come in pair She may or may not bring her alligator, Freddy. Let Tn denote the number of different collections of n pets that can accompany her. For example, T6=2 since there are 2 possible collections of 6 pets 3 dogs, 2 songbirds, 1 alligato 4 dogs, 2 songbirds, o alligators (a) give a closed-form generating function for the sequence (To, T1, T2, T3,...) Solution T(x)=(x32+x2+x3)·(x2+x4+x°+x3+…)·(1+ collections of songbirds collections of gators +I The second equation follows from the formula for the sum of a geometric series The last step is a simplification (b)From this generating function, find a closed-form expression for Tn.(Your an- swer may involve several cases. Solution x5+x6+x7 1 7)(1+x+x3+x3+.) x+2x0+3x+3x°+3x3+ Therefore, we have 007 Problem 6. In this problem, we'll use generating functions to solve the recurrence to=0

� �� � � �� � �� � Problem Set 8 5 • She brings 3, 4, or 5 dogs. • She brings a positive number of songbirds, which always come in pairs. • She may or may not bring her alligator, Freddy. Let Tn denote the number of different collections of n pets that can accompany her. For example, T6 = 2 since there are 2 possible collections of 6 pets: • 3 dogs, 2 songbirds, 1 alligato � • 4 dogs, 2 songbirds, 0 alligators (a) Give a closed­form generating function for the sequence (T0, T1, T2, T3, . . .). Solution. 4 5 ·( 2 4 6 8 x) = ( 3 T( x + x + x ) x + x + x + x + . . .) (1 + · x) collections of dogs collections of songbirds collections of gators = (x 3 + x 4 + x 5 ) · x5 + x6 + x7 x2 1 − x2 · (1 + x) = 1 − x The second equation follows from the formula for the sum of a geometric series. The last step is a simplification. (b) From this generating function, find a closed­form expression for Tn. (Your an￾swer may involve several cases.) Solution. 7 x5 + x6 + x 6 7 3 = (x 5 + x + x )(1 + x + x 3 + x + . . .) 1 − x 9 = x 5 + 2x 6 + 3x 7 + 3x 8 + 3x + . . . Therefore, we have: Tn = ⎧ ⎪⎪⎪⎨ ⎪⎪⎪⎩ 0 0 ≤ n ≤ 4 1 n = 5 2 n = 6 3 n ≥ 7 Problem 6. In this problem, we’ll use generating functions to solve the recurrence: t0 = 0 t1 = 1 tn = 5tn−1 − 6tn−2 (for n ≥ 2)

Problem Set 8 (a) Find a closed-form generating function F(a) for the sequence Solution. From the recurrence equation, this is precisely the sequence (0,1,51-6to,5t2-6t1,5t3-6 We can express this sequence in terms of the generating function F(a) 5t F() 6. -F(a) =(0,5+1,5t1-6to,5t2-6t1,5t3-6t2,)←F(x) The second term is correct; 5to +1=l, since to=0. So we have the equation F(a)=5. F()-6. F(a)+I Solving this equation for F(a) gives: F(a) (b) Rewrite this generating function as a sum of fractions of the form wnere c and r are constant Solution. Factoring the denominator gives 1-5. +6 z2=(1-2x)(1-3c o we can rewrite the fraction in the form 1-5x+6x21-2x1-3 Substituting =0 gives the equation c +d =0. Substituting l gives 1/2 C-d/2 or, equivalently, 2c+d=-1. Solving this system of linear equations gives c=-l and d=1. Therefore, we have 2x1-3 (c) Expand each fraction using the fact 1+rx+r2x2+r3x3+ T Combine these expansions to obtain a closed-form expression for t

6 Problem Set 8 (a) Find a closed­form generating function F(x) for the sequence (t0, t1, t2, . . .) Solution. From the recurrence equation, this is precisely the sequence: (0, 1, 5t1 − 6t0, 5t2 − 6t1, 5t3 − 6t2, . . .) We can express this sequence in terms of the generating function F(x): ( 0, 5t0, 5t1, 5t2, 5t3, . . . ) ←→ 5xF(x) ( 0, 0, −6t0, −6t1, −6t2, . . . ) −6x2 ←→ F(x) + ( 0, 1, 0, 0, 0, . . . ) ←→ x = ( 0, 5t0 + 1, 5t1 − 6t0, 5t2 − 6t1, 5t3 − 6t2, . . .) ←→ F(x) The second term is correct; 5t0 + 1 = 1, since t0 = 0. So we have the equation: F(x) = 5xF(x) − 6x 2 F(x) + x Solving this equation for F(x) gives: x F(x) = 1 − 5x + 6x2 (b) Rewrite this generating function as a sum of fractions of the form: c 1 − rx where c and r are constants. Solution. Factoring the denominator gives 1 − 5x + 6x2 = (1 − 2x)(1 − 3x). So we can rewrite the fraction in the form: x c d = + 1 − 5x + 6x2 1 − 2x 1 − 3x Substituting x = 0 gives the equation c + d = 0. Substituting x = 1 gives 1/2 = −c − d/2 or, equivalently, 2c + d = −1. Solving this system of linear equations gives c = −1 and d = 1. Therefore, we have: 1 F(x) = −1 + 1 − 2x 1 − 3x (c) Expand each fraction using the fact: 1 = 1 + rx + r 2 x 2 + r 3 x 3 + . . . 1 − rx Combine these expansions to obtain a closed­form expression for tn

Problem set 8 Solution F(x)=-2-22x-22x2-23x3 +30+31x+32x2+33x3+ 39-2)+(32-21)x+(32-2) Thus, tn= 3n-2 Problem 7. Below is a combinatorial proof of an equation. What is the equation Proof. Stinky Peterson owns n newts, t toads, and s slugs. Conveniently, he lives in a dorm with n+t+s other students. The students are distinguishable, but creatures of the same variety are not distinguishable )Stinky wants to put one creature in each neighbor's bed. Let w be the set of all ways in which this can be done On one hand, he could first determine who gets the slugs. Then, he could decide who among his remaining neighbors has earned a toad. Therefore, W is equal to the expression on the left On the other hand, Stinky could first decide which people deserve newts and slugs and then, from among those, determine who truly merits a newt. This shows that WI is equal to the expression on the right Since both expressions are equal to w they must be equal to each other Combinatorial proofs are real proofs. They are not only rigorous, but also convey an intuitive understanding that a purely algebraic argument might not reveal. However, combinatorial proofs are usually less colorful than this one. Solution n+t+s/n+ n+t+s/n+s n+s Problem 8. Consider the following equation (a) Describe a set S of binary sequences whose size is given by the expression on the Solution. Let s be all 2n-bit sequences with exactly n+1 ones (b) Describe a way of partitioning S into disjoint subsets To,..., In-1 such that: k八k+1

� �� � Problem Set 8 7 Solution. 1 2 2 − 23 3 F(x) = −20 − 2 x − 2 x x − . . . 1 2 3 3 + 30 + 3 x + 3 x 2 + 3 x + . . . 0 1 − 21 2 2 − (33 − 23 = (30 − 2 ) + (3 )x + (32 − 2 )x )x 3 − . . . n n Thus, tn = 3 − 2 . Problem 7. Below is a combinatorial proof of an equation. What is the equation? Proof. Stinky Peterson owns n newts, t toads, and s slugs. Conveniently, he lives in a dorm with n+t+s other students. (The students are distinguishable, but creatures of the same variety are not distinguishable.) Stinky wants to put one creature in each neighbor’s bed. Let W be the set of all ways in which this can be done. On one hand, he could first determine who gets the slugs. Then, he could decide who among his remaining neighbors has earned a toad. Therefore, |W| is equal to the expression on the left. On the other hand, Stinky could first decide which people deserve newts and slugs and then, from among those, determine who truly merits a newt. This shows that |W| is equal to the expression on the right. Since both expressions are equal to |W|, they must be equal to each other. (Combinatorial proofs are real proofs. They are not only rigorous, but also convey an intuitive understanding that a purely algebraic argument might not reveal. However, combinatorial proofs are usually less colorful than this one.) Solution. � � � � � � � � n + t + s n + t n + t + s n + s = s · t n + s · n Problem 8. Consider the following equation: � � n−1 � �� � 2n � n n = (*) n + 1 k k + 1 k=0 (a) Describe a set S of binary sequences whose size is given by the expression on the left. Solution. Let S be all 2n­bit sequences with exactly n + 1 ones. (b) Describe a way of partitioning S into disjoint subsets T0, . . . , Tn−1 such that: n n |Tk| = k k + 1

Problem set 8 In particular, state clearly which elements of S are in set Tk and explain why ITkI satisfies this equation Solution. Let Tk consist of 2n-bit sequences with exactly k zeros in the first n pos tions. Each such sequence has n-k ones in the first n positions, and thus k+1 ones in the last n positions. There are(k)ways to select the first n bits and (km) ways to select the last n bits, and so there are(n)(1) elements of Tk in all (c) Explain why equation(logically follows Solution. Since S is equal to the disjoint union ToU..UTn-I, the sum rule implies TolU..UITn-I Substituting the results from the two preceding parts gives equation()

� � � � 8 Problem Set 8 In particular, state clearly which elements of S are in set Tk and explain why |Tk| satisfies this equation. Solution. Let Tk consist of 2n­bit sequences with exactly k zeros in the first n posi￾tions. Each such sequence has n − k ones in the first n positions, and thus k + 1 ones n n in the last n positions. There are ways to select the first n bits and ways to k � �� � k+1 n n select the last n bits, and so there are k k+1 elements of Tk in all. (c) Explain why equation (*) logically follows. Solution. Since S is equal to the disjoint union T0 ∪ . . . ∪ Tn−1, the sum rule implies: | | | | S = T0 ∪ . . . ∪ | | Tn−1 Substituting the results from the two preceding parts gives equation (*)