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 lemmas6 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