Sprague-Grundy Theorem

This note has been used to help create the Sprague Grundy Theorem wiki

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 (a1,a2,,an)(a_1, a_2, \ldots, a_n). Let bib_i be the base 2 representation of aia_i. A Nim position is losing if over all the numbers in {bi}i=1n\{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)(3,6,8), then we can write these numbers as 112,1102,1000211_2, 110_2, 1000_2. We want to look at each binary position of these numbers, so let’s arrange them in a table:

111101000 \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 11012 =131101_2\ = 13.

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

111100111100000 \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 1x21x_2, where xx 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 kk, then from that position it will always be possible to move to a position with Nim Sum jj for any j<kj < k and not possible to move to a position with Nim Sum kk. 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 kk such that we cannot move to a position with Nim Sum kk. 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 nn stones. On each turn, a player removes from the pile 1,2,3,, or k1,2,3,\ldots, \mbox{ or } k stones. The person who takes the last stone wins. Determine, in terms of nn and kk, the Nim Sum of each position.

Solution: For jkj \leq k, the Nim sum of the game with jj stones will be jj. This is easy to see inductively starting at j=0j = 0. When j=k+1j = 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 ii and i+k+1i + k + 1 will always be the same. So the Nim Sum of nn stones where we can remove at most kk is n(modk+1).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 nn 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(mod2)n \pmod{2} .

Note by Calvin Lin
7 years, 2 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...