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 each column of bits contains an even number of 1s 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. 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.

Let NIM = {(s₁, . . . , s_k)| each s_i is a binary number and Player I has a winning strategy in the Nim game starting at this position}. Use the preceding facts about balanced positions to show that NIM ∈ L