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