《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: