Sprague-Grundy Theorem

In our previous post 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. In this post, we answer these questions by giving the complete characterization for winning and losing positions of Nim.

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 1s 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, 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.

Proof: 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 1s in a single column, which will make the Nim Sum no longer be 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 so 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:

The Sprague-Grundy Theorem. Any position of an impartial game is equivalent to a Nim pile of a certain size.

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.

Worked Examples

1. 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.

Solution: 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. And 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}.$

2. 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.

Solution: 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}$.