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!>|B6.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 |