A Look at Nim

Recall that 1-pile Nim is an N position. Take all except the last coin. Recall also that in 2-pile Nim, it’s an N position if the two piles are not equal – use strategy stealing.

\((1, 2, 3)\):

  • \((0, 2, 3) \in N\)
  • \((1, 1, 3) \in N\)
  • \((1, 2, 2) \in N\)
  • \((1, 2, 1) \in N\)
  • \((1, 2, 0) \in N\)

so \((1, 2, 3)\) is in \(N\)

What about \((25, 13, 39)\)? It looks like we’re going to need a different method.


Bouton’s Method

Charles Bouton (1962) found a way to solve Nim games. Here’s his approach:

  • Split the piles into piles of powers of 2; ie. binary.1
  • Then, you XOR all the piles, which is called finding the Nim-Sum of the numbers.2 The intuition here is that for an \(N\) position, it is possible to reduce the current set into a strategy-stealing solution. In other words, we should take out the coins that differ from the two sets; ie. an XOR of the two sets.
  • We have 2 cases. Iff3 the xor (or Nim-Sum) is 0, then the position is a \(P\)-position. Otherwise, the position is a \(N\)-position.
  • To generate a valid number, take out coins from the largest pile until the xor of the piles is 0.

Formally, a Nim position \(x = (x_1, x_2, ..., x_k) \in P \iff x_1 \oplus x_2 \oplus ... \oplus x_n = 0\).

Proof:
Let \(Z \subseteq X\) consist of all positions \(x\) such that the Nim Sum of pile sizes is 0. This gives us two sets, \(Z, Z^\complement\). We must now check 3 conditions:

  1. Terminal positions are in \(Z\).
  2. Let \(x \in Z, x = (x_1, x_2, ... x_k)\), where not all \(x_i = 0\). WLOG, suppose we move by reducing \(x_1\) to \(y\), \(y < x_1\). The new Nim Sum is \(y \oplus x_2 \oplus ... \oplus x_k\). We know this is not 0, since if it were, \(y = x_1\) (which is a contradiction).
  3. Let \(z \in Z^\complement, z = (z_1, ... z_n)\). \(z_1 \oplus z_2 \oplus ... \oplus z_k \neq 0\). In the Nim Sum, consider the leftmost column that has an odd number of ones. We pick the largest pile, flipping zeros into ones and ones to zeros to turn the column sum to 0. This gives a move to \(Z\).

This proves the theorem, as \(\forall y \in Z, \exists \textrm{ move into } Z \implies Z = P, Z^\complement = N\).


An Example

Let’s revisit \((25, 13, 39)\).

  • In binary, we have \((11001_2, 1101_2, 100111_2)\).
  • Next, we XOR all our numbers: \(11001_2 \oplus 1101_2 \oplus 100111_2 = 110011_2\)
  • To generate our winning strategy, we want to take out enough coins from the largest pile until the xor of the piles is 0. In other words, we want the largest pile to become \(010100_2\), or to take out 19 from that pile. (To verify, \(25 \oplus 13 \oplus 20 = 0\))

Another Example

Is \((27, 23, 22, 15)\) in \(P\) or \(N\)?

\((11011_2, 10111_2, 10110_2, 01111_2)\) gives a Nim Sum of \(10101\). We can move \(27\) to \(14\). The remainder of the winning moves is left as an exercise for homework.


Footnotes

  1. A tutorial 

  2. Wikipedia on XOR 

  3. If and only if