The game of Nim is played with a collection of piles of sticks. In one move a player may remove any nonzero number of sticks from a single pile. The players alternately take turns making moves. The player who removes the very last stick loses. Say that we have a game position in Nim with k piles containing s1 , -. ., Sk sticks. Call the position balanced if, when each of the numbers si is written in binary and the binary numbers are written as rows of a matrix aligned at the low order bits, each column of bits contains an even number of is. Prove the following two facts.
a. Starting in an unbalanced position, a single move exists that changes the position into a balanced one.
b. Starting in a balanced position, every single move changes the position into an unbalanced one.