Editing Sprague–Grundy theorem (section)

{{short description|Every impartial game position is equivalent to a position in the game of nim}}
{{multiple issues|
{{more footnotes|date=June 2014}}
{{technical|date=June 2014}}
}}

In [[combinatorial game theory]], the '''Sprague&ndash;Grundy theorem''' states that every [[impartial game]] under the [[normal play convention]] is equivalent to a one-heap game of [[nim]], or to an infinite generalization of nim. It can therefore be represented as a [[natural number]], the size of the heap in its equivalent game of nim, as an [[ordinal number]] in the infinite generalization, or alternatively as a [[nimber]], the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.

The '''Grundy value''' or '''nim-value''' of any impartial game is the unique nimber that the game is equivalent to.  In the case of a game whose positions are indexed by the natural numbers (like nim itself, which is indexed by its heap sizes), the sequence of nimbers for successive positions of the game is called the '''nim-sequence''' of the game.

The Sprague–Grundy theorem and its proof encapsulate the main results of a theory discovered independently by [[Roland Sprague|R. P. Sprague]] (1936)<ref name = "SpraguePaper">{{cite journal
 | last = Sprague | first = R. P. | author-link = Roland Sprague
 | title = Über mathematische Kampfspiele
 | url = http://www.jstage.jst.go.jp/article/tmj1911/41/0/41_0_438/_article
 | journal = [[Tohoku Mathematical Journal]]
 | language = de
 | year = 1936
 | volume = 41
 | pages = 438–444
 | zbl = 0013.29004 | jfm = 62.1070.03}}</ref> and [[Patrick Michael Grundy|P. M. Grundy]] (1939).<ref name = "GrundyPaper">{{cite journal
 | last = Grundy | first = P. M. | author-link = Patrick Michael Grundy
 | 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 |archive-url = https://web.archive.org/web/20070927192024/http://www.archim.org.uk/eureka/27/games.html |archive-date = 2007-09-27}} Reprinted, 1964, '''27''': 9–11.</ref>