Maximum usable frequency

2013-07-21T12:32:17Z

58.170.83.172:

{{Cleanup|date=June 2007}}
In [[combinatorial game theory]], the '''Sprague–Grundy theorem''' states that every [[impartial game]] under the [[normal play convention]] is equivalent to a [[nimber]]. The '''Grundy value''' or '''nim-value''' of an impartial game is then defined as the unique nimber that the game is equivalent to. In the case of a game whose positions (or summands of positions) are indexed by the natural numbers (for example the possible heap sizes in nim-like games), the sequence of nimbers for successive heap sizes is called the '''nim-sequence''' of the game.

The theorem was discovered independently by [[Roland Sprague|R. P. Sprague]] (1935) and [[Patrick Grundy|P. M. Grundy]] (1939).

==Definitions==
For the purposes of the Sprague–Grundy theorem, a ''game'' is a two-player game of [[perfect information]] satisfying the ''ending condition'' (all games come to an end: there are no infinite lines of play) and the ''normal play condition'' (a player who cannot move loses).

An ''[[impartial game]]'' is one such as [[nim]], in which each player has exactly the same available moves as the other player in any position. Note that games such as [[tic-tac-toe]], [[checkers]], and [[chess]] are ''not'' impartial games. In the case of checkers and chess, for example, players can only move their own pieces, not their opponent's pieces. And in tic-tac-toe, one player puts down X's, while the other puts down O's. Impartial games fall into two ''outcome classes'': either the next player wins (an ''N-position'') or the previous player wins (a ''P-position'').

An impartial game can be identified with the set of positions that can be reached in one move (these are called the ''options'' of the game). Thus the game with options ''A'', ''B'', or ''C'' is the set {''A'', ''B'', ''C''}.

The normal play convention is where the last player to move wins. Alternatively, the player who first does not have any valid move loses. The opposite - the [[misère]] convention is where the last person to have a valid move or makes the last move loses.

A ''[[nimber]]'' is a special game denoted *''n'' for some ordinal ''n''. We define *0 = {} (the empty set), then *1 = {*0}, *2 = {*0, *1}, and *(''n''+1) = *''n'' ∪ {*''n''}. When ''n'' is an integer, the nimber *''n'' = {*0, *1, ..., *(''n''−1)}. This corresponds to a heap of ''n'' counters in the game of [[nim]], hence the name.

Two games ''G'' and ''H'' can be ''added'' to make a new game ''G''+''H'' in which a player can choose either to move in ''G'' or in ''H''. In set notation, ''G''+''H'' means {''G''+''h'' for ''h'' in ''H''} ∪ {''g''+''H'' for ''g'' in ''G''}, and thus game addition is commutative and associative.

Two games ''G'' and ''G''' are ''equivalent'' if for every game ''H'', the game ''G''+''H'' is in the same outcome class as ''G'''+''H''. We write ''G'' ≈ ''G'''.

A game can refer to two things. It can define a set of possible positions and their moves through its rules, for example, chess, or nim. It can also refer to a certain position, for example, the game *5. Generally, the meaning to be taken is clear from the context.

==Lemma==
For impartial games, ''G'' ≈ ''G''' if and only if ''G''+''G''' is a ''P-position''.

First, we note that ≈ is an [[equivalence relation]] since equality of outcome classes is an equivalence relation.

We now show that for every game G, and ''P-position'' game ''A'', ''A''+''G'' ≈ ''G''. By the definition of ≈, we need to show that ''G''+''H'' is in the same outcome-class as ''A''+''G''+''H'' for all games ''H''.
If ''G''+''H'' is ''P-position'', then the previous player has a winning strategy in ''A''+''G''+''H'': to every move in ''G''+''H'' he responds according to his winning strategy in ''G''+''H'', and to every move in ''A'' he responds with his winning strategy there. If ''G''+''H'' is ''N-position'', then the next player in ''A''+''G''+''H'' makes a winning move in ''G''+''H'', and then reverts to responding to his opponent in the manner described above.

Also, ''G''+''G'' is ''P-position'' for any game ''G''. For every move made in one copy of ''G'', the previous player can respond with the same move in the other copy, which means he always makes the last move.

Now, we can prove the lemma.

If ''G'' ≈ ''G''', then ''G''+''G''' is of the same outcome-class as ''G''+''G'', which is ''P-position''.

On the other hand, if ''G''+''G''' is ''P-position'', then since ''G''+''G'' is also ''P-position'', ''G'' ≈ ''G''+(''G''+''G''') ≈ (''G''+''G'')+''G''' ≈ ''G''', thus ''G'' ≈ ''G'''.

==Proof==
We prove the theorem by [[structural induction]] on the set representing the game.

Consider a game <math>G = \{G_1, G_2, \ldots, G_k\}</math>. By the induction hypothesis, all of the options are equivalent to nimbers, say <math>G_i \approx *n_i</math>. We will show that <math>G \approx *m</math>, where <math>m</math> is the [[mex (mathematics)|mex]] of the numbers <math>n_1, n_2, \ldots, n_k</math>, that is the smallest non-negative integer not equal to some <math>n_i</math>.

Let <math>G'=\{*n_1, *n_2, \ldots, *n_k\}</math>. The first thing we need to note is that <math>G \approx G'</math>. Consider <math>G+G'</math>. If the first player makes a move in <math>G</math>, then the second player can move to the equivalent <math>*n_i</math> in <math>G'</math>, and conversely if the first player makes a move in <math>G'</math>. After this the game is a P-position (by the lemma), since it's the sum of some option of <math>G</math> and a nim pile equivalent to that option. Therefore, <math>G+G'</math> is a P-position, and by another application of our lemma, <math>G \approx G'</math>.

So now, by our lemma, we need to show that <math>G+*m</math> is a P-position. We do so by giving an explicit strategy for the second player in the equivalent <math>G'+*m</math>.

Suppose that the first player moves in the component <math>*m</math> to the option <math>*m'</math> where <math>m'<m</math>. But since <math>m</math> was the ''minimal'' excluded number, the second player can move in <math>G'</math> to <math>*m'</math>.

Suppose instead that the first player moves in the component <math>G'</math> to the option <math>*n_i</math>. If <math>n_i < m</math> then the second player moves in <math>*m</math> to <math>*n_i</math>. If <math>n_i > m</math> then the second player, moves in <math>*n_i</math> to <math>*m</math>. It's not possible that <math>n_i = m</math> because <math>m</math> was defined to be different from all the <math>n_i</math>.

Therefore, <math>G'+*m</math> is a P-position, and hence so is <math>G+*m</math>. By our lemma, <math>G \approx *m</math> as desired.

==Development==
The Sprague–Grundy theorem has been developed into the field of [[combinatorial game theory]], notably by [[E. R. Berlekamp]], [[John Horton Conway]] and others. The field is presented in the books ''[[Winning Ways for your Mathematical Plays]]'' and ''[[On Numbers and Games]]''.

==See also==
*[[Genus theory]]
*[[Indistinguishability quotient]]

==References==
*{{cite journal
| author = Sprague, R. P.
| title = Über mathematische Kampfspiele
| url = http://www.jstage.jst.go.jp/article/tmj1911/41/0/41_0_438/_article
| journal = [[Tohoku Mathematical Journal]]
| year = 1935–36
| volume = 41
| pages = 438–444}}
*{{cite journal
| author = Grundy, P. M.
| title = Mathematics and games
| journal = [[Eureka (University of Cambridge magazine)|Eureka]]
| url = http://www.archim.org.uk/eureka/27/games.html
| year = 1939
| volume = 2
| pages = 6–8 |archiveurl = http://web.archive.org/web/20070927192024/http://www.archim.org.uk/eureka/27/games.html |archivedate = 2007-09-27}} Reprinted, 1964, '''27''': 9–11.
*{{cite journal
| author = Schleicher, Dierk; Stoll, Michael
| title = An introduction to Conway's games and numbers
| year = 2004
| arxiv = math.CO/0410026}}
*{{cite journal
| author = Milvang-Jensen, Brit C. A.
| year = 2000
| url = http://www.itu.dk/people/brit/Brits%20thesis.pdf
| title = Combinatorial Games, Theory and Applications}}

==External links==
* [http://www.cut-the-knot.org/Curriculum/Games/Grundy.shtml Grundy's game] at [[cut-the-knot]]
* [http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf Easily readable, introductory account from the UCLA Math Department]
* [http://sputsoft.com/blog/2009/04/the-game-of-nim.html The Game of Nim] at [http://sputsoft.com sputsoft.com]

{{DEFAULTSORT:Sprague-Grundy theorem}}
[[Category:Combinatorial game theory]]
[[Category:Theorems in discrete mathematics]]

formulasearchengine - User contributions [en]

Maximum usable frequency