4
$\begingroup$

I have read about Sprague Grundy Theorem and understand the proof of its correctness. However, I am unable to see the motivation behind the definitions. How do Sprague and Grundy know that they should define the Grundy number in that manner? Why is it the case that xoring the Grundy numbers together work? I don't think they magically came up with this theorem, so I would like to get some intuition to better understand how the theorem is constructed.

Thank you very much!

$\endgroup$
2
  • 1
    $\begingroup$ If you understand Nim, then the Sprague-Grundy theorem mainly says every impartial game is equivalent to a Nim game. So, are you asking why the $\text{XOR}$ operation works in Nim? $\endgroup$ Mar 31, 2013 at 9:13
  • $\begingroup$ Yes, that is part of what I am asking. The full question is: 1. Why is the Grundy Number (lowest non-negative number not in any direct-child game state) defined as such? How did the inventors come up with this idea? 2. Why does XOR works when we compose games? Is there a way for us to deduce this operation? I'm basically wondering how Sprague and Grundy came up with their ideas. I want to know some intuitive or deductive approach that allows us to derive the theorem. Otherwise it seems as if the theorem just dropped from the sky and all they did was to prove its correctness. $\endgroup$
    – simpleton
    Mar 31, 2013 at 20:17

3 Answers 3

4
$\begingroup$

The solution to Nim was known by 1901 (C. L. Bouton. "Nim, a game with a complete mathematical theory", Annals of Mathematics 3 (1901–02), 35–39), over 30 years before the Sprague-Grundy Theorem (1935, 1939). Once you have the idea that Nim might be the most general model for an impartial game, perhaps by reducing Nim variants to Nim, then which Nim heap corresponds to a game is pretty obvious: If an impartial game $G$ contains the option $\star n$ then $G+\star n$ is a first player win, so $G$ can't be $\star n$. By induction, adding the first excluded option makes the game a second player win, so that's what $G$ is.


I'll say a little more to motivate the solution to Nim, inspired by Mark Wildon's answer.

First, if you have two heaps of equal size, this is a second player win by mirroring.

Second, which sizes of heaps can't be expressed as arbitrary sums of smaller heaps? The "primes" in this sense are the powers of two.

Together, these motivate expressing $\star n$ as $\sum \star 2^{a_i}$, and prove that $\star m + \star n = \star x$ where the binary representation of $x$ is $\text{XOR}$ applied to the binary representations of $m$ and $n$.

$\endgroup$
2
  • $\begingroup$ Just to expand on the final line: in the game $G + \star n$, if the first player plays to $\star m$ in $G$ where $m < n$, then the second player can play in $\star n$ to give $\star m + \star m = 0$; if the first player plays to $\star m'$ in $\star n$ where $m' < n$ then the second player can play in $G$ to $\star m'$ to give $\star m' + \star m' = 0$. (We know that $\star m'$ is an option of $G$ because $n$ is the minimum excluded option.) Hence $G + \star n = 0$ and $G = \star n$. $\endgroup$ Apr 1, 2013 at 1:48
  • $\begingroup$ I guess I should have included $\omega, 2\omega, 4\omega, ... \omega^2, 2\omega^2, ...$ among the primes in case you are considering well-founded games with infinitely many options. $\endgroup$ Apr 1, 2013 at 4:01
2
$\begingroup$

You can make Zare's argument (above) a bit more precise. We wrote a pedagogical paper a few years ago on this topic, to understand it ourselves (and then never published it...). The basic idea is that if there is group of game values then they must involve base 2 and xor -- or more formally, products of Z^2.

Here's the link: http://www1.icsi.berkeley.edu/~ejf/pfiles/nimgroups.pdf

$\endgroup$
1
$\begingroup$

I don't know of a really intuitive explanation for the XOR rule, but maybe this short proof will be useful. It is sufficient to prove that if $0\le a_1 < \cdots < a_r$ and $n = \sum_{i=1}^r 2^{a_i}$ then

$$ \star n = \sum_{i=1}^r \star 2^{a_i}. $$

Assume inductively that this result is true for all $t < n$. By playing in $\star 2^{a_k}$ on the right-hand side, we get as options all nim piles of the form

$$\sum_{i \neq k} \star 2^{a_i} + \star t $$

where $0\le t < 2^{a_k}$. By induction the XOR rule holds for addition of $\star t$. So these options are exactly the nim pile of size $\star m$ where the binary expansion of $m$ is obtained from the binary expansion of $n$ by flipping the $1$ in position $a_k$ for some $k$, and also flipping any combination of less significant bits. Hence we can obtain $\star m$ if and only if $m < n$ and $\sum_{i=1}^r \star 2^{a_i}$ plays exactly like the nim pile $\star n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.