How to Be a Player: Impartial Combinatorial Games

We must prove the validity of the two Nim Rules. The proof of Nim Rule 2 is much easier than the proof of Nim Rule 1. Therefore, we present this argument first.

Proof of Nim Rule 2. Suppose that we have Nim position \(\{ n_1, n_2, \ldots , n_k\}\) such that

We show that every move we make results in a position with nim value \(\neq 0\text{.}\)

First, we write out the binary representation for each heap size, one per row. We add leading zeros so that every binary representation has the same number of digits. Since the nim value is zero, we know that every column contains an even number of 1's.

Pick any heap, say heap \(i\) of size \(n_i\text{.}\) Remove some number \(s>1\) of beans. The binary representation of \(n_i - s\) is different from that of \(n_i\text{.}\) Pick any column where the digit has changed. The number of 1's in that column is now odd. Therefore the nim sum of the new position is nonzero:

This is true for every possible choice of heap, and every possible move. In other words, the nim value of every follower is nonzero. This proves Nim Rule 2.

Proof of Nim Rule 1 We will present our proof for an arbitrary Nim position \(\{ n_1 , n_2, \ldots , n_k \}\) where \(n_1 \nimsum n_2 \nimsum \cdots \nimsum n_k \neq 0\text{.}\) However, it will be useful to consider an example as we go through the proof. We will use the Nim position \(\{ 27, 8, 3, 29 \}\text{.}\) As shown in equation \eqref{eqn-nimsum-example}, we have \(27 \nimsum 8 \nimsum 3 \nimsum 29 = 13 \neq 0\text{,}\) so this will be an \(\cN\)-position.

First, we write out the binary representation for each heap size, one per row. We add leading zeros so that every binary representation has the same number of digits. For our example game, this looks like

We say that a column is bad if it has an odd number of ones, and it is good if it has an even number of ones. Since the nim sum of these heap sizes is nonzero, there is at least one bad column. Our example has three bad columns, corresponding to \(2^3\text{,}\) \(2^2\) and \(2^0\) when considered from left to right. These three bad columns are highlighted below:

We now show how to make a Nim move that results in a position with nim value \(=0\text{.}\) Consider the leftmost bad column. In our example, this is the \(2^3\) column, which contains three 1's. There is a winning move for every row that has a 1 in this leftmost bad column. Let's call these the bad rows. Here is our winning move:

Of course, the leftmost digit that you flip will go from 1 to 0 because a bad row must have a 1 in the leftmost bad column (that is what makes it a bad row). Here are the three possible winning moves in our example:

The first, second and fourth rows are bad rows: they have a 1 in the second column from the left. In each winning move, we pick one bad row and change the digits in its entries in the three bad columns. After flipping these digits, every column has an even number of 1's. Therefore the nim value of this new position is 0. This is precisely what Nim Rule 1 claims: there is at least one follower with nim value \(= 0\text{.}\)

It remains to show that these digit flips in a bad row correspond to a valid move in Nim. That is, in the corresponding Nim game, the size of this Nim heap must decrease. This is certainly true for our three example moves, which look like:

It is interesting to note that each of these moves does decrease the heap size, but the size of that decrease depends on the choice of heap. We can write these three winning moves more compactly by using the decimal notation for our nim heap positions:

Here is another way to think about what we are doing as we flip the digits in the three bad columns:

From this expansion, it should be clear that flipping the digits in the bad columns does correspond to removing some beans from the heap.

Let's get back to the general case and show that we always decrease the size of the heap corresponding to the bad row. Suppose that our bad columns correspond to \(2^{k_1} > 2^{k_2} > \cdots > 2^{k_r}\text{.}\) If the digit for \(2^{k_i}\) was 1, we change it to 0, which corresponds to removing \(2^{k_i}\) beans from the \(i\)th heap. That is no problem. However, when the digit for \(2^{k_i}\) changes from a 0 to a 1, this corresponds to adding back \(2^{k_i}\) beans to the heap. We must make sure that we take away more beans than we add. We need the following inequality

(The exercises in Section [cross-reference to target(s) "sec-nim-exercises" missing or not unique] ask you to prove the validity of inequality (2.3.1).) The right hand side is an upper bound on the number of beans that we must add back to the heap, after removing the \(2^{k_1}\) beans corresponding to the leftmost bad column. In other words, the size of the heap decreases. This completes the proof of Nim Rule 1.