MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 edited body

The Sprague-Grundy theorem provides a surjective homomorphism $\mathcal{G}$ from the commutative monoid of symmetric games onto the group $On_2$ (the ordinals with the nim sum). The power point of this quotient is that $\ker \mathcal{G}$ is exactly the class of $\mathcal{P}$ games. So you can see how the Sprague-Grundy theorem defines a partition on all games, which are many. In fact, you can think of a symmetric game as a well founded set (formally a biset with equal side-sets, as presented in On Numbers and Games by J. H. Conway); in this light we are partitioning the whole Von Neumann hierarchy $\mathbb{V}$, where each class is indeed very well populated (it is a proper class).

This bridge theorem, as already outlined, allows to compute the outcome of a game just by computing the nimber of each of its components; this is the main use and its original purpose. But it can also be useful the other way round:

If $n_1 + \cdots + n_k = t \neq 0$, where $+$ is the nim sum, then $$\exists i \in \{ 1, \dots ,k \} \mbox{ such that } n_i + t < n_i.$$

A proof is as follows: since $t \neq 0$, $n_1 + \cdots + n_k$ is a $\mathcal{N}$-position in Nim so there must be a winning move from, say, $n_1$ to $\bar{n}_1$ such that $\bar{n}_1 + n_2 + \cdots + n_k =0$. Since in Nim the only legal moves are to decrease numbers it follows that $n_1 > \bar{n}_1$. But, since $On_2$ satisfies $\forall x\ x+x=0$, adding $n_2 + \cdots + n_k + t$ to each side of the previous equation yields (after cancellations) $\bar{n}_1 + t = n_2 + \cdots + n_k + t = n_1$.

1

The Sprague-Grundy theorem provides a surjective homomorphism $\mathcal{G}$ from the commutative monoid of symmetric games onto the group $On_2$ (the ordinals with the nim sum). The power of this quotient is that $\ker \mathcal{G}$ is exactly the class of $\mathcal{P}$ games. So you can see how the Sprague-Grundy theorem defines a partition on all games, which are many. In fact, you can think of a symmetric game as a well founded set (formally a biset with equal side-sets, as presented in On Numbers and Games by J. H. Conway); in this light we are partitioning the whole Von Neumann hierarchy $\mathbb{V}$, where each class is indeed very well populated (it is a proper class).

This bridge theorem, as already outlined, allows to compute the outcome of a game just by computing the nimber of each of its components; this is the main use and its original purpose. But it can also be useful the other way round:

If $n_1 + \cdots + n_k = t \neq 0$, where $+$ is the nim sum, then $$\exists i \in \{ 1, \dots ,k \} \mbox{ such that } n_i + t < n_i.$$

A proof is as follows: since $t \neq 0$, $n_1 + \cdots + n_k$ is a $\mathcal{N}$-position in Nim so there must be a winning move from, say, $n_1$ to $\bar{n}_1$ such that $\bar{n}_1 + n_2 + \cdots + n_k =0$. Since in Nim the only legal moves are to decrease numbers it follows that $n_1 > \bar{n}_1$. But, since $On_2$ satisfies $\forall x\ x+x=0$, adding $n_2 + \cdots + n_k + t$ to each side of the previous equation yields (after cancellations) $\bar{n}_1 + t = n_2 + \cdots + n_k + t = n_1$.