《Mathematics for Computer》Problem set 3 Solutions

6.042/18.] Mathematics for Computer Science February 15, 2005 Srini devadas and Eric Lehman Problem set 3 Solutions Due: Tuesday, February 22 at 9 PM Problem 1. An urn contains 75 white balls and 150 black balls. while there are at least 2 balls remaining in the urn, you repeat the following operation. You remove 2 balls elected arbitrarily and then: If at least one of the two balls is black, then you discard one black ball and put the other ball back in the urn If both of the balls are white then you discard them both and put a new black ball into the urn Prove that the urn never reaches the state where it is empty except for one black ball Solution. We use induction. Let P(n)be the proposition that the urn always contains an odd number of white balls Base case. Initially, the urn contains 75 white balls, which is an odd number, so P(O)is true Inductive step. Suppose that the urn contains an odd number of white balls after n steps If there are fewer than 2 balls remaining, then the process ends. Otherwise, there are then two cases 1. You draw at least one black ball. Then the number of black balls decreases by one and the number of white balls is unchanged. Therefore, the number of white balls remains odd 2. You draw two white balls. Then the number of black balls increases by one, and the number of white balls decreases by two. Again, the number of white balls remains Thus, the urn still contains an odd number of white balls after n+ l steps. By induction, the urn always contains an odd number of white balls. Therefore, the urn can never hold just one black ball and zero white balls, since zero is even. Problem 2. A puzzle toy contains the numbers l,..., 35 written on small circular disks. The disks are arranged on an oval track with no gaps so that the whole sequence of disks can slide clockwise or counterclockwise around the track

6.042/18.062J Mathematics for Computer Science February 15, 2005 Srini Devadas and Eric Lehman Problem Set 3 Solutions Due: Tuesday, February 22 at 9 PM Problem 1. An urn contains 75 white balls and 150 black balls. While there are at least 2 balls remaining in the urn, you repeat the following operation. You remove 2 balls selected arbitrarily and then: • If at least one of the two balls is black, then you discard one black ball and put the other ball back in the urn. • If both of the balls are white, then you discard them both and put a new black ball into the urn. Prove that the urn never reaches the state where it is empty except for one black ball. Solution. We use induction. Let P(n) be the proposition that the urn always contains an odd number of white balls. Base case. Initially, the urn contains 75 white balls, which is an odd number, so P(0) is true. Inductive step. Suppose that the urn contains an odd number of white balls after n steps. If there are fewer than 2 balls remaining, then the process ends. Otherwise, there are then two cases: 1. You draw at least one black ball. Then the number of black balls decreases by one and the number of white balls is unchanged. Therefore, the number of white balls remains odd. 2. You draw two white balls. Then the number of black balls increases by one, and the number of white balls decreases by two. Again, the number of white balls remains odd. Thus, the urn still contains an odd number of white balls after n + 1 steps. By induction, the urn always contains an odd number of white balls. Therefore, the urn can never hold just one black ball and zero white balls, since zero is even. Problem 2. A puzzle toy contains the numbers 1, . . . , 35 written on small circular disks. The disks are arranged on an oval track with no gaps so that the whole sequence of disks can slide clockwise or counterclockwise around the track

Problem Set 3 X Disks slide around track 34人35人1人 Turning dial reverses the order of four disks In addition the track runs through a circular dial that is four disks wide. This dial can be rotated 180 degrees, reversing the order of the four disks on that portion of the track. For example, if the dial were turned in the configuration above, then the the order of 34, 35, 1, 2 would become 2, 1, 35, 34 Suppose that the puzzle is initially in the state shown above with numbers increasing counterclockwise around the track. Prove that no sequence of operations has the effect of swapping disks only 1 and 2 while leaving all the other disks in the same order Solution. Associate each configuration of the puzzle with a permutation of the num- bers l,..., 35 by taking the numbers in counterclockwise order starting in the middle of he dial. Thus, the example configuration corresponds to the permutation ex Now we use induction on the number of operations. Let P(n) be the proposition that fter n operations, there are an even number of inversions Base case. Initially, there are zero inversions. Since zero is even, P(O)is true Inductive step. Suppose that after n steps there are an even number of inversions. There are now three cases to consider. Suppose the dial is turned 180 degrees. This transforms the permutation S1S253S4.S32S33534535 nto the permutation S35S34S3S4·S325335251

2 Problem Set 3 1 2 3 4 5 6 7 Disks slide around track. of four disks. Turning dial reverses the order 34 35 33 In addition, the track runs through a circular dial that is four disks wide. This dial can be rotated 180 degrees, reversing the order of the four disks on that portion of the track. For example, if the dial were turned in the configuration above, then the the order of 34, 35, 1, 2 would become 2, 1, 35, 34. Suppose that the puzzle is initially in the state shown above with numbers increasing counterclockwise around the track. Prove that no sequence of operations has the effect of swapping disks only 1 and 2 while leaving all the other disks in the same order. Solution. Associate each configuration of the puzzle with a permutation of the num￾bers 1, . . . , 35 by taking the numbers in counterclockwise order starting in the middle of the dial. Thus, the example configuration corresponds to the permutation: 1 2 3 . . . 35 Now we use induction on the number of operations. Let P(n) be the proposition that after n operations, there are an even number of inversions. Base case. Initially, there are zero inversions. Since zero is even, P(0) is true. Inductive step. Suppose that after n steps there are an even number of inversions. There are now three cases to consider: • Suppose the dial is turned 180 degrees. This transforms the permutation s1s2s3s4 . . . s32s33s34s35 into the permutation: s35s34s3s4 . . . s32s33s2s1

Problem set 3 This amounts to swapping s1 with S35 and s2 with s34. Each swap changes the parity of the number of inversions so after two swaps there are still an even number of Inversions. suppose that the numbers are rotated one position clockwise around the track. This transforms the permutation S1S2S3S4.S32S33534S3 into the permutation: This reverses the order of exactly 34 pairs of disks, S1 and every other disk. This changes the parity of the number of inversions 34 times, which leaves an even num- ber of inversions Similarly, rotating one position counterclockwise reverses the order of 34 pair again leaving an even number of inversions By induction, the number of inversions is always even. Therefore, the configuration in which 1 and 2 are swapped (which has 1 inversion) is unreachable Problem 3. A regular 52-card deck is arranged as follows A2.A.24..K。A·2·.KA◇2◇..K◇ In a perfect shuffle, the deck is first divided into two piles, one containing the top 26 cards and the other the bottom 26. These two piles are then recombined into a single deck by perfectly interlacing them This interlacing process can be done in two different ways since the new top card could come from the top of either 26-card pile. So over a sequence of perfect shuffles,many different arrangements of the deck can be obtained. Prove that no sequence of perfect shuffles puts the deck in the following order KA◇2◇..◇A◆2。..K Solution. We use induction. Define the cards in the i-th and (52- i)-th positions in the deck to be opposites. Thus, for example, the top card is opposite the bottom card, the second card is opposite the next to last card, and the two cards in the middle of the deck

Problem Set 3 3 This amounts to swapping s1 with s35 and s2 with s34. Each swap changes the parity of the number of inversions, so after two swaps there are still an even number of inversions. • Suppose that the numbers are rotated one position clockwise around the track. This transforms the permutation s1s2s3s4 . . . s32s33s34s35 into the permutation: s2s3s4 . . . s32s33s34s35s1 This reverses the order of exactly 34 pairs of disks, s1 and every other disk. This changes the parity of the number of inversions 34 times, which leaves an even num￾ber of inversions. • Similarly, rotating one position counterclockwise reverses the order of 34 pairs, again leaving an even number of inversions. By induction, the number of inversions is always even. Therefore, the configuration in which 1 and 2 are swapped (which has 1 inversion) is unreachable. Problem 3. A regular 52­card deck is arranged as follows: A♥ 2 . . . K♥ A♣ 2♣ . . . K♣ A♠ 2♠ . . . K♠ A♦ 2♦ . . . K♦ In a perfect shuffle, the deck is first divided into two piles, one containing the top 26 cards and the other the bottom 26. These two piles are then recombined into a single deck by perfectly interlacing them: This interlacing process can be done in two different ways since the new top card could come from the top of either 26­card pile. So over a sequence of perfect shuffles, many different arrangements of the deck can be obtained. Prove that no sequence of perfect shuffles puts the deck in the following order: A♥ 2♥ . . . K♥ A♣ 2♣ . . . K♣ A♦ 2♦ . . . K♦ A♠ 2♠ . . . K♠ Solution. We use induction. Define the cards in the i­th and (52 − i)­th positions in the deck to be opposites. Thus, for example, the top card is opposite the bottom card, the second card is opposite the next to last card, and the two cards in the middle of the deck

Problem Set 3 are opposite each other. Let P(n)be the proposition that opposite cards are the same color Base case. In the initial configuration, hearts are opposite diamonds and clubs are opposite spades. Therefore, all opposite cards are the same color Inductive step. Suppose that all opposite cards are the same color. Consider an arbitrary configuration of the deck C1C2C3. C52 A perfect shuffle leaves the deck in one of the following orders C1C27C2C28C3C29··C25C51C26C52 C27C1C28C2C29C3 51C25C52C26 In both cases, exactly the same cards remain opposites: Ci and Cs2, C2 and csl, etc. So, in particular, opposite cards are still the same color By induction, opposite cards are always the same color. Therefore, the hearts, clubs diamonds, spades configuration is unreachable since there all opposite cards are different colors Problem 4. Prove the following basic facts about greatest common divisors (a)gcd(ka, kb)=k ged(a, b) Solution. The smallest positive value of s·(ka)+t·(kb)=k·(s·a+t·b) over alls, t e Z is k times the smallest positive value of +t·b over all s, t E Z. The first quantity is gcd(ka, kb) and the second is gcd(a, b). There- fore, gcd(ka, kb)= k gcd(a, b) (b) gcd(a, b)=gcd(a+kb, b)for allkE Z Solution. We show that every linear combination of a and b is a linear combination of a+ kb and b and vice-versa ·Ifx=s·a+t· b then a=8·(a+kb)+t"· b where s'= s and t=t-sk ·Ifx=s(a+kb)+t.b, then x=s·a+t· b where s=s'andt=t'+sk hus, in particular, the smallest positive linear combinations are equal, so gcd(a, b) cd(a+ kb, b)

4 Problem Set 3 are opposite each other. Let P(n) be the proposition that opposite cards are the same color. Base case. In the initial configuration, hearts are opposite diamonds and clubs are opposite spades. Therefore, all opposite cards are the same color. Inductive step. Suppose that all opposite cards are the same color. Consider an arbitrary configuration of the deck: c1c2c3 . . . c52 A perfect shuffle leaves the deck in one of the following orders: c1c27c2c28c3c29 . . . c25c51c26c52 c27c1c28c2c29c3 . . . c51c25c52c26 In both cases, exactly the same cards remain opposites: c1 and c52, c2 and c51, etc. So, in particular, opposite cards are still the same color. By induction, opposite cards are always the same color. Therefore, the hearts, clubs, diamonds, spades configuration is unreachable since there all opposite cards are different colors. Problem 4. Prove the following basic facts about greatest common divisors: (a) gcd(ka, kb) = k · gcd(a, b) for all k > 0. Solution. The smallest positive value of s · (ka) + t · (kb) = k a · (s · · + t b) over all s, t ∈ Z is k times the smallest positive value of s a · · + t b over all s, t ∈ Z. The first quantity is gcd(ka, kb) and the second is gcd(a, b). There￾fore, gcd(ka, kb) = k gcd(a, b). (b) gcd(a, b) = gcd(a + kb, b) for all k ∈ Z. Solution. We show that every linear combination of a and b is a linear combination of a + kb and b and vice­versa. • If x = s a + t b, then x = s� · (a + kb) + t � b where s� = s and t � = t − s� · · · k. • If x = s� · (a + kb) + t � b, then x = s a + t b where s = s� and t = t � + s� · · · k. Thus, in particular, the smallest positive linear combinations are equal, so gcd(a, b) = gcd(a + kb, b)

Problem set 3 Problem 5. Here is a long run of composite numbers 114,115,116,117,118,119,120,121,122,123,124,125,126 Prove that there exist arbitrarily long runs of composite numbers. Consider numbers a little bigger than n! where n!=m:(n-1)…3·2.1 Solution. Let k be some natural number such that 1<k< n. We know k I(n!+ k) because k n! and k k. Thus, the numbers n! +2, n! +3, n! +4,.. n!+n are all composite This is a run of n-1 consecutive composite numbers. Because we can choose n arbitrarily, we know arbitrarily long runs of composite numbers exist Problem 6. Here is a very, very fun game. Initially, there is a blackboard with the numbers 1309 and 1729 written on it. Now you and I take turns; you go first. On each player's turn, he or she must write a new positive integer on the board that is the difference of two numbers that are already there the first person who can not create a new number loses the ga ame For example, your first move must be 1729- 1309= 420. Then I could play either 1309-420=889or1729-420=1309, and so forth (a) Prove every number written on the board is a multiple of 7 less than or equal to 1729 Solution. We use induction. Let P(n) be the proposition that after n moves, every number on the board is a positive linear combination of 1729 and 1390 Base case. P(O) is true because 1729 and 1390 are trivial linear combinations of 1729 Inductive step. Assume that after n moves, every number on the board is a positive linear combination of 1729 and 1390. The next number written on the board is also a positive linear combination because: The rules require the number to be positive The new number must be a difference of two numbers already on the board, which are themselves linear combinations of 1729 and 1390 by assumption And a difference of linear combinations is another linear combination By induction, every number on the board is a positive linear combination of 1729 and 1390. And every positive linear combination of 1729 and 1390 is a multiple of gcd(1729,1390)=7 (b) Prove that every positive multiple of 7 less than or equal to 1729 is on the board at the end of the game Solution. Let a be the smallest number on the board at the end of the game. B the Division Algorithm, there exist integers q and r such that 1729=qa+r where

Problem Set 3 5 Problem 5. Here is a long run of composite numbers: 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126 Prove that there exist arbitrarily long runs of composite numbers. Consider numbers a little bigger than n! where n! = n · (n − 1) 3 2 1 · · · · · . Solution. Let k be some natural number such that 1 < k ≤ n. We know k | (n! + k) because k | n! and k k| . Thus, the numbers n!+2, n!+3, n!+4, . . . , n!+n are all composite. This is a run of n−1 consecutive composite numbers. Because we can choose n arbitrarily, we know arbitrarily long runs of composite numbers exist. Problem 6. Here is a very, very fun game. Initially, there is a blackboard with the numbers 1309 and 1729 written on it. Now you and I take turns; you go first. On each player’s turn, he or she must write a new positive integer on the board that is the difference of two numbers that are already there. The first person who can not create a new number loses the game. For example, your first move must be 1729 − 1309 = 420. Then I could play either 1309 − 420 = 889 or 1729 − 420 = 1309, and so forth. (a) Prove every number written on the board is a multiple of 7 less than or equal to 1729. Solution. We use induction. Let P(n) be the proposition that after n moves, every number on the board is a positive linear combination of 1729 and 1390. Base case. P(0) is true because 1729 and 1390 are trivial linear combinations of 1729 and 1390. Inductive step. Assume that after n moves, every number on the board is a positive linear combination of 1729 and 1390. The next number written on the board is also a positive linear combination, because: • The rules require the number to be positive. • The new number must be a difference of two numbers already on the board, which are themselves linear combinations of 1729 and 1390 by assumption. And a difference of linear combinations is another linear combination. By induction, every number on the board is a positive linear combination of 1729 and 1390. And every positive linear combination of 1729 and 1390 is a multiple of gcd(1729, 1390) = 7. (b) Prove that every positive multiple of 7 less than or equal to 1729 is on the board at the end of the game. Solution. Let x be the smallest number on the board at the end of the game. By the Division Algorithm, there exist integers q and r such that 1729 = q · x + r where

Problem Set 3 0<r< a. When no more moves are possible 1729- a must already be on the board, and thus so must 1729-2. c,.. 1729-(q-1)a. However, 1729-q=rcan not be on the board, since r r and r is defined to be the smallest number there The only explanation is that r=0, which implies that c 1729. By a symmetric argument, 3| 1390. Therefore, a is a common divisor of c and y. The only common divisors of 1729 and 1390 are 1 and 7, and r can not be 1 by the preceding problem part. Therefore, 7 is on the board at the end of the game. Since no more moves are possible, 1729-7, 1729-2.7,..., 7,0 must all be on the board as well. So every positive multiple of of 7 less than or equal to 1729 is on the board at the end of the me (c) Who wins? Solution. There are 1729/7= 247 numbers on the board at the end of the game Thus, there were 247-2= 245 moves. Since you go first, you also get the last move and win the game Problem 7. Prove the following theorem Theorem. If gcd(a, b)=l, then gcd(a+b, a-b)=l or 2 Solution. Since gcd(a, b)=l, there exist integers s and t such that +t·b Now there is a linear combination of a+b and a-b equal to 2 (s+t)·(a+b)+(s-t)·(a-b)=2(sa+t·b)=2 Thus gcd(a+b, a-b) is at most 2, which implies it is equal to 1 or 2

6 Problem Set 3 0 ≤ r < x. When no more moves are possible, 1729 − x must already be on the board, and thus so must 1729 − 2x, . . . 1729 − (q − 1)x. However, 1729 − qx = r can not be on the board, since r < x and x is defined to be the smallest number there. The only explanation is that r = 0, which implies that x | 1729. By a symmmetric argument, x | 1390. Therefore, x is a common divisor of x and y. The only common divisors of 1729 and 1390 are 1 and 7, and x can not be 1 by the preceding problem part. Therefore, 7 is on the board at the end of the game. Since no more moves are possible, 1729 − 7, 1729 − 2 7· , . . . , 7, 0 must all be on the board as well. So every positive multiple of of 7 less than or equal to 1729 is on the board at the end of the game. (c) Who wins? Solution. There are 1729/7 = 247 numbers on the board at the end of the game. Thus, there were 247 − 2 = 245 moves. Since you go first, you also get the last move and win the game. Problem 7. Prove the following theorem. Theorem. If gcd(a, b) = 1, then gcd(a + b, a − b) = 1 or 2. Solution. Since gcd(a, b) = 1, there exist integers s and t such that: s · a + t · b = 1 Now there is a linear combination of a + b and a − b equal to 2: (s + t) · (a + b) + (s − t) · (a − b) = 2(s · a + t · b) = 2 Thus gcd(a + b, a − b) is at most 2, which implies it is equal to 1 or 2