4.4. Nim is a two-person game that starts with some piles of stones. A player's move consists of removing one or more stones from a single pile. Players alternate moves, and the loser is the one who is left with no stones to remove. It turns out there is a winning strategy for one of the players that is easy to carry out but is not so obvious. To explain the winning strategy, we need to think of a number in two ways: as a nonnegative integer and as the bit string equal to the binary representation of the number-possibly with leading zeroes. For example, the XOR of numbers r;s;:: is defined in terms of their binary representations: combine the corresponding bits of the binary representations of r;s;::: using XOR, and then interpret the resulting bit-string as a number. For example 2XOR7XOR9=12 because, taking XOR's down the columns, we have \begin{tabular}{lllll} 0 & 0 & 1 & 0 & (binary rep of 2) \\ 0 & 1 & 1 & 1 & (binary rep of 7) \\ 1 & 0 & 0 & 1 & (binary rep of 9) \\ \hline 1 & 1 & 0 & 0 & (binary rep of 12) \end{tabular} The XOR of the numbers of stones in the piles is called their Nim sum. In this problem we will verify that if the Nim sum is not zero on a player's turn, then the player has a winning strategy. For example, if the game starts with five piles of equal size, then the first player has a winning strategy, but if the game starts with four equal-size piles, then the second player can force a win. (a) Prove that if the Nim sum of the piles is zero, then any one move will leave a nonzero Nim sum. (b) Prove that if there is a pile with more stones than the Nim sum of all the other piles, then there is a move that makes the Nim sum equal to zero. (c) Prove that if the Nim sum is not zero, then one of the piles is bigger than the Nim sum of the all the other piles. Hint: Notice that the largest pile may not be the one that is bigger than the Nim sum of the others; three piles of sizes 2,2,1 is an example. (d) Conclude that if the game begins with a nonzero Nim sum, then the first player has a winning strategy. Hint: Describe a preserved invariant that the first player can maintain