《Mathematics for Computer》Lecture l4 induction 2

6.042/18.] Mathematics for Computer Science February 10, 2005 Srini devadas and Eric Lehman Lecture notes duction ii 1 Unstacking Here is another wildly fun 6.042 game that' s surely about to sweep the nation! You begin with a stack of n boxes. Then you make a sequence of moves. In each move, you divide one stack of boxes into two nonempty stacks. The game ends when you have m stacks, each containing a single box. You earn points for each move; in particular, if you divide one stack of height a+ b into two stacks with heights a and b, then you score ab points for that move. Your overall score is the sum of the points that you earn for each move. What strategy should you use to maximize your total score? As an example, suppose that we begin with a stack of n 10 boxes. Then the game night proceed as follows Stack Heights 25 points 532 4321 23212 6442 22 1 222 121 111 111121111 1111111111 ats On each line, the underlined stack is divided in the next step. Can you find a better strategy? 1.1 Strong Induction Strong induction and ordinary induc ing a variant of induction called strong induction We'll analyze the unstacking game ion are used for exactly the same thing: proving that a predicate P(n)is true for all n E N

6.042/18.062J Mathematics for Computer Science February 10, 2005 Srini Devadas and Eric Lehman Lecture Notes Induction II 1 Unstacking Here is another wildly fun 6.042 game that’s surely about to sweep the nation! You begin with a stack of n boxes. Then you make a sequence of moves. In each move, you divide one stack of boxes into two nonempty stacks. The game ends when you have n stacks, each containing a single box. You earn points for each move; in particular, if you divide one stack of height a + b into two stacks with heights a and b, then you score ab points for that move. Your overall score is the sum of the points that you earn for each move. What strategy should you use to maximize your total score? As an example, suppose that we begin with a stack of n = 10 boxes. Then the game might proceed as follows: Stack Heights Score 10 5 5 25 points 5 3 2 6 4 3 2 1 4 2 3 2 1 2 4 2 2 2 1 2 1 2 1 2 2 1 2 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Total Score = 45 points On each line, the underlined stack is divided in the next step. Can you find a better strategy? 1.1 Strong Induction We’ll analyze the unstacking game using a variant of induction called strong induction. Strong induction and ordinary induction are used for exactly the same thing: proving that a predicate P(n) is true for all n ∈ N

2 Induction Il Principle of Strong Induction. Let P(n) be a predicate. If P(O)is true, and for all n∈NP(O),P(1),…,P(n) imply F(n+1), then P(n)is true for allnE N The only change from the ordinary induction principle is that strong induction allows you to assume more stuff in the inductive step of your proof! In an ordinary induction argument, you assume that P(n)is true and try to prove that P(n+ 1)is also true. In a strong induction argument, you may assume that P(O), P(1),., P(n-1), and P(n)are all true when you go to prove P(n+1). These extra assumptions can only make your job easier. Despite the name, strong induction is actually no more powerful than ordinary induc tion. In other words, any theorem that can be proved with strong induction can also be proved with ordinary induction. However, an apeal to the strong induction principle can make some proofs a bit easier. On the other hand, if P(n) is easily sufficient to prove P(n+1), then use ordinary induction for simplicity 1.2 Analyzing the Game Let's use strong induction to analyze the unstacking game. We'll prove that your score determined entirely by the number of boxes; your strategy is irrelevant! Theorem 1. Every way of unstacking n blocks gives a score of n(n-1)/2 points There are a couple technical points to notice in the proof The template for a strong induction proof is exactly the same as for ordinary induc tion As with ordinary induction, we have some freedom to adjust indices. In this case, we prove P() in the base case and prove that P(1),., P(n-1) imply P(n) for all n>2 in the inductive step Proof. The proof is by strong induction. Let P(n)be the proposition that every way of unstacking n blocks gives a score of n(n-1)/2 Base case: If n= 1, then there is only one block. No moves are possible, and so the total score for the game is 1(1-1)/2=0. Therefore, P(1)is true

2 Induction II Principle of Strong Induction. Let P(n) be a predicate. If • P(0) is true, and • for all n ∈ N, P(0), P(1), . . . , P(n) imply P(n + 1), then P(n) is true for all n ∈ N. The only change from the ordinary induction principle is that strong induction allows you to assume more stuff in the inductive step of your proof! In an ordinary induction argument, you assume that P(n) is true and try to prove that P(n + 1) is also true. In a strong induction argument, you may assume that P(0), P(1), . . . , P(n − 1), and P(n) are all true when you go to prove P(n + 1). These extra assumptions can only make your job easier. Despite the name, strong induction is actually no more powerful than ordinary induc￾tion. In other words, any theorem that can be proved with strong induction can also be proved with ordinary induction. However, an apeal to the strong induction principle can make some proofs a bit easier. On the other hand, if P(n) is easily sufficient to prove P(n + 1), then use ordinary induction for simplicity. 1.2 Analyzing the Game Let’s use strong induction to analyze the unstacking game. We’ll prove that your score is determined entirely by the number of boxes; your strategy is irrelevant! Theorem 1. Every way of unstacking n blocks gives a score of n(n − 1)/2 points. There are a couple technical points to notice in the proof: • The template for a strong induction proof is exactly the same as for ordinary induc￾tion. • As with ordinary induction, we have some freedom to adjust indices. In this case, we prove P(1) in the base case and prove that P(1), . . . , P(n − 1) imply P(n) for all n ≥ 2 in the inductive step. Proof. The proof is by strong induction. Let P(n) be the proposition that every way of unstacking n blocks gives a score of n(n − 1)/2. Base case: If n = 1, then there is only one block. No moves are possible, and so the total score for the game is 1(1 − 1)/2 = 0. Therefore, P(1) is true

Induction II Inductive step: Now we must show that P(1),., P(n-1)imply P(n) for all n > 2. So assume that P(1),., P(n-1)are all true and that we have a stack of n blocks. The first move must split this stack into substacks with sizes k and n- k for some k strictl between 0 and n. Now the total score for the game is the sum of points for this first move plus points obtained by unstacking the two resulting substack total score=(score for 1st move) +(score for unstacking k blocks +(score for unstacking n-k blocks =M(n-6xk(k-1)(n=k)(n=k-1) 2nk-2k2+k2-k+n2-nk-n-nk+k2+k n(n-1) The second equation uses the assumptions P(k) and P(n-k)and the rest is simplification This shows that P(1), P(2),., P(n)imply P(n+1) Therefore, the claim is true by strong induction. 2 The game of nim Nim is a game involving two players, some pennies, and mathematical induction. The begins with a bunch of pennies arranged in one or more rows. For we have three rows of pennies ooo o The two players take turns. On each turn, a player must remove one or more pennies, ll from a single row. The player who takes the last penny wins. For example, suppose that the first player removes two pennies from the first row Oooo Now the second player removes all the pennies from the last row, leaving this configur- tion:

Induction II 3 Inductive step: Now we must show that P(1), . . . , P(n − 1) imply P(n) for all n ≥ 2. So assume that P(1), . . . , P(n − 1) are all true and that we have a stack of n blocks. The first move must split this stack into substacks with sizes k and n − k for some k strictly between 0 and n. Now the total score for the game is the sum of points for this first move plus points obtained by unstacking the two resulting substacks: total score = (score for 1st move) + (score for unstacking k blocks) + (score for unstacking n − k blocks) (n − k)(n − k − 1) = k(n − k) + k(k − 1) + 2 2 2 2nk − 2k2 + k2 − k + n − nk − n − nk + k2 + k = 2 n(n − 1) = 2 The second equation uses the assumptions P(k) and P(n−k) and the rest is simplification. This shows that P(1), P(2), . . . , P(n) imply P(n + 1). Therefore, the claim is true by strong induction. 2 The Game of Nim Nim is a game involving two players, some pennies, and mathematical induction. The game begins with a bunch of pennies, arranged in one or more rows. For example, here we have three rows of pennies: ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ The two players take turns. On each turn, a player must remove one or more pennies, all from a single row. The player who takes the last penny wins. For example, suppose that the first player removes two pennies from the first row: ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ Now the second player removes all the pennies from the last row, leaving this configuar￾tion: ◦ ◦ ◦ ◦ ◦

Induction II The first player then takes three pennies from the last row: The second player is now in trouble; she must take exactly one of these two pennies Either way, the first player takes the last penny and wins the game There is a compact way to describe a configuration in Nim: list the number of pennies in each row. For example, the starting configuartion in the game above is (3, 4, 5). The game then passed through the configurations(1, 4, 5),(1, 4, 0), and (1,1,0) 2.1 Nimsums A Harvard professor, Charles Bouton, discovered the optimal strategy for Nim in 1901 Boutons strategy relies on a special mathematical operation called a Nimsum. The Nim- sum of natural numbers cl Ck is itself a natural number that is computed as follows Regard C1,..., Ck as binary numbers The i-th bit of the dimsum is the xor of the i-th bits of Cl (or is pronounced"eks-or"and is short for"exclusive-or". The xor of bits b1 and b2 is denoted b, e b2 and defined as follows b1b2b1⊕b2 000 01 10 110 As a consequence of this definition, the xor of bits b1, .. bk is O if the sum of the bi is even and 1 if the sum is odd. For example,1⊕0⊕1⊕1=1 because 1+0+1+1 but1⊕1⊕00=0 because 1+1+0+0=2 Is even) As an example the nimsum of 3 4, and 5 is computed as follows: 011 Here, we xor each column of bits to obtain the Nimsum 010, which is the binary represen tation of 2

4 Induction II The first player then takes three pennies from the last row: ◦ ◦ The second player is now in trouble; she must take exactly one of these two pennies. Either way, the first player takes the last penny and wins the game. There is a compact way to describe a configuration in Nim: list the number of pennies in each row. For example, the starting configuartion in the game above is (3, 4, 5). The game then passed through the configurations (1, 4, 5), (1, 4, 0), and (1, 1, 0). 2.1 Nimsums A Harvard professor, Charles Bouton, discovered the optimal strategy for Nim in 1901. Bouton’s strategy relies on a special mathematical operation called a Nimsum. The Nim￾sum of natural numbers c1, . . . , ck is itself a natural number that is computed as follows: • Regard c1, . . . , ck as binary numbers. • The i­th bit of the Nimsum is the xor of the i­th bits of c1, . . . , ck. (Xor is pronounced “eks­or” and is short for “exclusive­or”. The xor of bits b1 and b2 is denoted b1 ⊕ b2 and defined as follows: b1 b2 0 0 0 1 1 0 1 1 b1 ⊕ b2 0 1 1 0 As a consequence of this definition, the xor of bits b1, . . . , bk is 0 if the sum of the bi is even and 1 if the sum is odd. For example, 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1 because 1 + 0 + 1 + 1 = 3 is odd, but 1 ⊕ 1 ⊕ 0 ⊕ 0 = 0 because 1 + 1 + 0 + 0 = 2 is even.) As an example, the Nimsum of 3, 4, and 5 is computed as follows: 3 = 011 4 = 100 5 = 101 010 = 2 Here, we xor each column of bits to obtain the Nimsum 010, which is the binary represen￾tation of 2

Induction II 2.2 The Winning Strategy Suppose that(c1,., ck)is a configuration in Nim; that is, there are a total of k rows, and the i-th row contains ci pennies. This configuration is called safe if the Nimsum of c1, .. Ck is nonzero unsafe if the Dimsum of c1, .. Ck is zero In this way, all possible configurations in Nim are now partitioned into two groups the safe configurations and the unsafe configurations. Boutons strategy is as follows If you see a safe configuration on your turn, then select a move that leaves your opponent with an unsafe configuration If you see an unsafe configuration on your turn, you're doomed. Every possible move leaves your opponent with a safe configuration; select among them arbitrarily and prepare to lose Thus, if the first player sees a safe position, she selects a move that leaves the second player an unsafe position. Every move available to the second player then leaves the first player with another safe position. This cycle repeats until the first player wins the entire game. 2.3 An Example Lets use Boutons strategy in one example game before trying to prove a general theorem The bizarre French movie "Last Year at Marienbad"features a Nim game beginning in the configuration(1, 3, 5, 7). Let's analyze this configuration by computing the Nimsum: 101 111 000 Since the Nimsum is zero, this is a hopeless situation for the first player. In particular no matter what she does, the second player is left with a safe configuration; that is, one in which the Nimsum is nonzero. For example, suppose that the first player removes the entire fourth row Then the dimsum becomes

Induction II 5 2.2 The Winning Strategy Suppose that (c1, . . . , ck) is a configuration in Nim; that is, there are a total of k rows, and the i­th row contains ci pennies. This configuration is called: • safe if the Nimsum of c1, . . . , ck is nonzero • unsafe if the Nimsum of c1, . . . , ck is zero In this way, all possible configurations in Nim are now partitioned into two groups: the safe configurations and the unsafe configurations. Bouton’s strategy is as follows: • If you see a safe configuration on your turn, then select a move that leaves your opponent with an unsafe configuration. • If you see an unsafe configuration on your turn, you’re doomed. Every possible move leaves your opponent with a safe configuration; select among them arbitrarily and prepare to lose. Thus, if the first player sees a safe position, she selects a move that leaves the second player an unsafe position. Every move available to the second player then leaves the first player with another safe position. This cycle repeats until the first player wins the entire game. 2.3 An Example Let’s use Bouton’s strategy in one example game before trying to prove a general theorem. The bizarre French movie “Last Year at Marienbad” features a Nim game beginning in the configuration (1, 3, 5, 7). Let’s analyze this configuration by computing the Nimsum: 1 = 001 3 = 011 5 = 101 7 = 111 000 = 0 Since the Nimsum is zero, this is a hopeless situation for the first player. In particular, no matter what she does, the second player is left with a safe configuration; that is, one in which the Nimsum is nonzero. For example, suppose that the first player removes the entire fourth row. Then the Nimsum becomes:

350 011 01 11 This is a safe configuration. To maintain her advantage, the second player needs to leave the first player in an unsafe position; that is, a position with Nimsum zero. Only one move accomplishes this: removing three pennies from the third row: 001 1320 011 010 000 000 Now the first player is again confronted with an unsafe position, one with a Nimsum of zero. No matter what she does, the second player will be left with a safe position. For example, suppose that the first player takes all three pennies from the second row. Then che second player is left with 001 0=000 010 000 011 Sure enough, this is a safe position. One again, the second player needs to leave the first player in an unsafe position. Removing one penny from the third row accomplishes this 0=000 000 The first player is clearly going to lose. She must take one of the two remaining pen nies, leaving the second player to take the other and win the game 2.4 Proof of correctness Now lets prove that bouton' s strategy works. We ll need two lemmas

6 Induction II 1 = 001 3 = 011 5 = 101 0 = 000 111 = 7 This is a safe configuration. To maintain her advantage, the second player needs to leave the first player in an unsafe position; that is, a position with Nimsum zero. Only one move accomplishes this: removing three pennies from the third row: 1 = 001 3 = 011 2 = 010 0 = 000 000 = 0 Now the first player is again confronted with an unsafe position, one with a Nimsum of zero. No matter what she does, the second player will be left with a safe position. For example, suppose that the first player takes all three pennies from the second row. Then the second player is left with: 1 = 001 0 = 000 2 = 010 0 = 000 011 = 3 Sure enough, this is a safe position. One again, the second player needs to leave the first player in an unsafe position. Removing one penny from the third row accomplishes this: 1 = 001 0 = 000 1 = 001 0 = 000 000 = 0 The first player is clearly going to lose. She must take one of the two remaining pen￾nies, leaving the second player to take the other and win the game. 2.4 Proof of Correctness Now let’s prove that Bouton’s strategy works. We’ll need two lemmas

Induction II Lemma 2. If a player sees an unsafe configuration on her turn, then every possible move leaves her opponent with a safe configuration Proof. Suppose that the player sees an unsafe configuration; that is, a configuration(C1, ..., Ck) with Nimsum zero. Then the player must remove pennies from some row j, leaving d<cj pennies behind. In binary, the numbers c; and d must differ in some bit position But then the Nimsum of the resulting configuration has a l in that bit position. Therefore, the Nimsum is nonzero, meaning that the resulting configuration is safe 口 Lemma 3. If a player sees a safe configuration on her turn, then she has a move that leaves her opponent with an unsafe configuration Proof. Suppose that the player sees a configuration(c1, .. Ck )with Nimsum s t0 Let i be the position of the most-significant 1 in the binary representation of s. Sind the i-th position of s is nonzero, there must be some row size c, that is nonzero in the i-th position as well. Suppose that the player removes all but d pennies from the j-th row, where di differs from c, in exactly those positions where s has a 1 We must check that d, the number of pennies the player leaves behind, is less than cj the number of pennies originally in the j-th row. This is true because c, has a l in the i-th position, d, has a O in this position, and the two numbers agree in all higher positions Modifying the game configuration by changing c, by d, reduces the Nimsum to zero, because c; and di disagree in exactly those positions where the original Nimsum had a An example may clarify the preceding argument. Suppose that a player sees the con- figuration(1, 2, 4, 4). We can compute the Nimsum as follows 00110 The Nimsum is 011 in binary. The most significant 1 is in the second position from the right. The number of pennies in the second row, 010 in binary, also has a 1 in this position We should leave 001 pennies in this row, since this differs from the number of pennies there now(010)in every position where the Nimsum(011) has a 1. Now we compute the Nimsum of the resulting configuration 4 000

Induction II 7 Lemma 2. If a player sees an unsafe configuration on her turn, then every possible move leaves her opponent with a safe configuration. Proof. Suppose that the player sees an unsafe configuration; that is, a configuration (c1, . . . , ck) with Nimsum zero. Then the player must remove pennies from some row j, leaving cj � < cj pennies behind. In binary, the numbers cj and cj � must differ in some bit position. But then the Nimsum of the resulting configuration has a 1 in that bit position. Therefore, the Nimsum is nonzero, meaning that the resulting configuration is safe. Lemma 3. If a player sees a safe configuration on her turn, then she has a move that leaves her opponent with an unsafe configuration. Proof. Suppose that the player sees a configuration (c1, . . . , ck) with Nimsum s =� 0. Let i be the position of the most­significant 1 in the binary representation of s. Since the i­th position of s is nonzero, there must be some row size cj that is nonzero in the i­th position as well. Suppose that the player removes all but cj � pennies from the j­th row, where c� j differs from cj in exactly those positions where s has a 1. We must check that cj � , the number of pennies the player leaves behind, is less than cj , the number of pennies originally in the j­th row. This is true because cj has a 1 in the i­th position, cj � has a 0 in this position, and the two numbers agree in all higher positions. Modifying the game configuration by changing cj by cj � reduces the Nimsum to zero, because cj and cj � disagree in exactly those positions where the original Nimsum had a 1. An example may clarify the preceding argument. Suppose that a player sees the con­ figuration (1, 2, 4, 4). We can compute the Nimsum as follows: 1 = 001 2 = 010 4 = 100 4 = 100 011 = 3 The Nimsum is 011 in binary. The most significant 1 is in the second position from the right. The number of pennies in the second row, 010 in binary, also has a 1 in this position. We should leave 001 pennies in this row, since this differs from the number of pennies there now (010) in every position where the Nimsum (011) has a 1. Now we compute the Nimsum of the resulting configuration: 1 = 001 1 = 001 4 = 100 4 = 100 000 = 0

Induction II As expected, this is an unsafe position We re ready to prove the main res Theorem 4. If the current player has a safe position, then she can guarantee a win. Otherwise, the other player can guarantee a win es The proof uses induction, with the statement of the theorem as the induction hypoth is. This hypothesis is quite complicated! Suppose that we define three smalle r proposI tions. current player has a safe position b= current player can guarantee a win next player can guarantee a win In these terms, the induction hypothesis is(A-B)A(A-C). Induction hypotheses containing implications are always a bit tricky, but this one has two implications! Some square-bracketed comments are included in the proof to clairfy the structure Proof. The proof is by strong induction on n, the total number of pennies remaining. Let P(n) be the proposition that in all Nim configurations with n pennies, if the current player has a safe position, then she can guarantee a win and, otherwise, the other player can guarantee a win Base case. Suppose that n=0; that is, no pennies remain. This is an unsafe position Therefore the first implication is trivially true because the if-part is false. The second implication is also true, because when the current player is left with no pennies, the other player has just won the game. [In other words, the proposition(A- B)A(A-C)is true because A is false and C is true Inductive step. We must show that for all n >0, the propositions P(O),., P(n)imply P(n+1) Assume P(0),., P(n)and consider a configuration with n+1 pennies remain ing. Now we must show two things If the configuration is safe, the current player can guarantee a win. Suppose that the configuration is safe. By Lemma 3, the current player has a move that leaves the next player with an unsafe configuration involving fewer than n+ 1 pennies. If m<n+l pennies remain, then assumption P(m) implies that the player after the next player(which is the current player) can guarantee a win. [This shows A-B. 2. If the configuration is unsafe, the next player can guarantee a win. Suppose that the configuration is unsafe. By Lemma 2, every move leaves the next player with a safe configuration involving m n+1 pennies. The assumption P(m) then implies that the next player can guarantee a win. [This shows A-C

8 Induction II As expected, this is an unsafe position. We’re ready to prove the main result. Theorem 4. If the current player has a safe position, then she can guarantee a win. Otherwise, the other player can guarantee a win. The proof uses induction, with the statement of the theorem as the induction hypoth￾esis. This hypothesis is quite complicated! Suppose that we define three smaller proposi￾tions: A = current player has a safe position B = current player can guarantee a win C = next player can guarantee a win In these terms, the induction hypothesis is (A → B) ∧ (A → C). Induction hypotheses containing implications are always a bit tricky, but this one has two implications! Some square­bracketed comments are included in the proof to clairfy the structure. Proof. The proof is by strong induction on n, the total number of pennies remaining. Let P(n) be the proposition that in all Nim configurations with n pennies, if the current player has a safe position, then she can guarantee a win and, otherwise, the other player can guarantee a win. Base case. Suppose that n = 0; that is, no pennies remain. This is an unsafe position. Therefore, the first implication is trivially true because the if­part is false. The second implication is also true, because when the current player is left with no pennies, the other player has just won the game. [In other words, the proposition (A → B) ∧ (A → C) is true because A is false and C is true.] Inductive step. We must show that for all n ≥ 0, the propositions P(0), . . . , P(n) imply P(n+ 1). Assume P(0), . . . , P(n) and consider a configuration with n+ 1 pennies remain￾ing. Now we must show two things: 1. If the configuration is safe, the current player can guarantee a win. Suppose that the configuration is safe. By Lemma 3, the current player has a move that leaves the next player with an unsafe configuration involving fewer than n + 1 pennies. If m < n + 1 pennies remain, then assumption P(m) implies that the player after the next player (which is the current player) can guarantee a win. [This shows A B → .] 2. If the configuration is unsafe, the next player can guarantee a win. Suppose that the configuration is unsafe. By Lemma 2, every move leaves the next player with a safe configuration involving m < n + 1 pennies. The assumption P(m) then implies that the next player can guarantee a win. [This shows A C → .]

Induction II Putting these arguments together gives P(n+1).[That is, A-B and A-C together imply(A+ B)A(A-C). Therefore, the theorem follows by the principle of induction

Induction II 9 Putting these arguments together gives P(n + 1). [That is, A B → → and A C together imply (A → B) ∧ (A → C).] Therefore, the theorem follows by the principle of induction