Editing Nim (section)

=== Greedy nim ===

Greedy nim is a variation wherein the players are restricted to choosing stones from only the largest pile.<ref name="Greedy Nim">
{{cite book | title=Winning Ways for your Mathematical Plays | edition=2nd | publisher=A K Peters Ltd | year=2001 | volume=4 vols.}}; {{cite book|title=vol. 1|isbn=978-1-56881-130-7|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}}; {{cite book|title=vol. 2|isbn=978-1-56881-142-0|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}}; {{cite book|title=vol. 3|isbn=978-1-56881-143-7|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}}; {{cite book|title=vol. 4|isbn=978-1-56881-144-4|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2004-06-15}}
</ref> It is a finite [[impartial game]]. Greedy nim misère has the same rules as greedy nim, but the last player able to make a move loses.

Let the largest number of stones in a pile be ''m'' and the second largest number of stones in a pile be ''n''. Let ''p''<sub>''m''</sub> be the number of piles having ''m'' stones and ''p''<sub>''n''</sub> be the number of piles having ''n'' stones. Then there is a theorem that game positions with ''p''<sub>''m''</sub> even are ''P'' positions.
<ref name="Nim restrictions">
{{cite journal
| first1 = M. H.
| last1 = Albert
| first2 = R. J.
| last2 = Nowakowski
| title = Nim Restrictions
| year= 2004
| journal= Integers
| page = 2
| url= http://www.emis.de/journals/INTEGERS/papers/eg1/eg1.pdf
}}</ref> This theorem can be shown by considering the positions where ''p''<sub>''m''</sub> is odd. If ''p''<sub>''m''</sub> is larger than 1, all stones may be removed from this pile to reduce ''p''<sub>''m''</sub> by 1 and the new ''p''<sub>''m''</sub> will be even. If ''p''<sub>''m''</sub> = 1 (i.e. the largest heap is unique), there are two cases:
* If ''p''<sub>''n''</sub> is odd, the size of the largest heap is reduced to ''n'' (so now the new ''p''<sub>''m''</sub> is even).
* If ''p''<sub>''n''</sub> is even, the largest heap is removed entirely, leaving an even number of largest heaps.
Thus, there exists a move to a state where ''p''<sub>''m''</sub> is even. Conversely, if ''p''<sub>''m''</sub> is even, if any move is possible (''p''<sub>''m''</sub> ≠ 0), then it must take the game to a state where ''p''<sub>''m''</sub> is odd. The final position of the game is even (''p''<sub>''m''</sub> = 0). Hence, each position of the game with ''p''<sub>''m''</sub> even must be a ''P'' position.