Sprague Grundy Theorem

The Sprague-Grundy theorem is a statement about impartial games.

In Combinatorial Games - Winning Positions, we analyzed winning positions of impartial games. Several questions arose in trying to find a general characterization for whether a set of nim piles is a winning position or a losing position. Here, we answer these questions by giving the complete characterization for winning and losing positions of nim.

Claim

Suppose we have nim piles of sizes \((a_1, a_2, \ldots, a_n)\). Let \(b_i\) be the base 2 representation of \(a_i\). A nim position is losing if over all the numbers in \(\{b_i\}_{i=1}^{n}\), the number of 1s in each binary position is even and winning otherwise.

Before we prove this statement, let’s look at an example to see what we mean. If the nim piles have sizes \((3,6,8)\), then we can write these numbers as \(11_2, 110_2, 1000_2\). We want to look at each binary position of these numbers, so let’s arrange them in a table:

\[ \begin{array}{cccc} & & 1 &1\\ & 1 &1 &0\\ 1 & 0 & 0 & 0\\ \end{array}\]

We can construct a number that represents the parity of the number of 1's in each binary position. We call this the nim-sum of these numbers. Looking at each column of the table, we see that the 1's column has a single 1, the 10's column has two 1's, and the 100's column and the 1000's column each have a single 1. Our nim-sum here is \(1101_2\ = 13\).

If the piles have sizes \(7,9,14\), then we can write these numbers as \(111_2, 1001_2, 1110_2\). We want to look at each binary position of these numbers, so let’s arrange them in a table:

\[ \begin{array}{cccc} & 1& 1 &1\\ 1& 0&0 &1\\ 1 & 1& 1 & 0\\ \hline 0 & 0 & 0 & 0 \\ \end{array}\]

The last line represents the parity of the number of 1's, which gives us that the nim-sum of these numbers is 0.

We will modify our description of a winning position to be one where the nim-sum of the pile sizes is not 0, which is equivalent to the original definition. To verify that this accurately describes the set of winning and losing positions, we check 3 things.

First, it is clear that the game with no stones is losing, and has nim-sum 0.

Second, if we are in a losing position, we have nim-sum 0. If we remove stones from a single pile, we are changing the positions of 1's in a single column, which will make the nim-sum no longer 0.

Third, if we are in a winning position, we have nim-sum of the form \(1x_2\), where \(x\) is a binary string. We choose a pile that has a 1 in the same position as the leftmost 1 in the nim-sum. We change this number by flipping each digit for which there is a 1 in the corresponding position in the nim-sum. The nim-sum of these new numbers will be 0, which is a losing position. It is left as an exercise to show that the new number is less than the original number and thus constitutes a valid move. \( _\square\)

The nim-sum actually gives us more information than determining whether a position is winning or losing; it also assigns a value to that position. If a position has nim-sum \(k\), then from that position it will always be possible to move to a position with nim-sum \(j\) for any \(j < k,\) and not possible to move to a position with nim-sum \(k\). To see this, consider the proof that any winning position can get to a 0 position, and replace 0 with any smaller number. The described method will extend to this.

We have spent a lot of time developing the theory for a single impartial game, Nim. In fact, this is all the theory that we need to understand any general impartial game! We have the following surprising result:

Sprague-Grundy Theorem

Any position of an impartial game is equivalent to a nim pile of a certain size. \(_\square\)

We can assign a nim-sum to the positions in any impartial game by building up sequentially through small cases. The nim-sum of a position is the smallest non-negative integer \(k\) such that we cannot move to a position with nim-sum \(k\). This requires us to calculate the nim-sum of every position that we can move to. Since the game will always end, this calculation is finite. However, it can get computationally intensive, and a computer may be useful.

The proof of the Sprague-Grundy theorem is identical to our previous proof, where we checked 3 statements.

Two players play a game starting with a pile of \(n\) stones. On each turn, a player removes from the pile \(1,2,3,\ldots, \mbox{ or } k\) stones. The person who takes the last stone wins. Determine, in terms of \(n\) and \(k\), the nim-sum of each position.

---

For \(j \leq k\), the nim-sum of the game with \(j\) stones will be \(j\). This is easy to see inductively starting at \(j = 0\). When \(j = k+1\), this is a losing position, so the nim-sum will be 0. If we repeat this, we see inductively that the nim-sum of \(i\) and \(i + k + 1\) will always be the same. So the nim-sum of \(n\) stones where we can remove at most \(k\) is \(n \pmod{k + 1}.\) \(_\square\)

Odd Nim is like Nim, except you can only remove an odd number of stones from a pile. Determine the nim-sum for a single pile of \(n\) stones.

---

Since we can only take an odd number of stones from the pile, the game will always be a losing position if the number of stones is even and a winning position if the number of stones is odd. From a winning position, we can only get to the 0 position, so all winning positions have nim-sum 1. Thus the nim-sum is \(n \pmod{2} \). \(_\square\)