Editing Nim (section)

== Variations ==

=== The subtraction game ===
<imagemap>
File:Subtraction_game_SMIL.svg|thumb|Interactive subtraction game: Players take turns removing 1, 2 or 3 objects from an initial pool of 21 objects. The player taking the last object wins.
default [http://upload.wikimedia.org/wikipedia/commons/4/4d/Subtraction_game_SMIL.svg]
</imagemap>
In another game which is commonly known as nim (but is better called the [[subtraction game]]), an upper bound is imposed on the number of objects that can be removed in a turn. Instead of removing arbitrarily many objects, a player can only remove 1 or 2 or ... or ''k'' at a time. This game is commonly played in practice with only one heap.

Bouton's analysis carries over easily to the general multiple-heap version of this game. The only difference is that as a first step, before computing the nim-sums we must reduce the sizes of the heaps [[modular arithmetic|modulo]] ''k''&nbsp;+&nbsp;1. If this makes all the heaps of size zero (in misère play), the winning move is to take ''k'' objects from one of the heaps. In particular, in ideal play from a single heap of ''n'' objects, the second player can win [[if and only if]]

* ''0''&nbsp;=&nbsp;n&nbsp;(mod&nbsp;''k''&nbsp;+&nbsp;1) (in normal play), or
* ''1''&nbsp;=&nbsp;n&nbsp;(mod&nbsp;''k''&nbsp;+&nbsp;1) (in misère play).

This follows from calculating the [[nim-sequence]] of ''S''(1, 2, ..., ''k''),

<math display="block">0.123\ldots k0123\ldots k0123\ldots = \dot0.123\ldots\dot{k}, </math>

from which the strategy above follows by the [[Sprague–Grundy theorem]].

=== The 21 game ===
{{See also|21 (drinking game)}}
The game "21" is played as a misère game with any number of players who take turns saying a number. The first player says "1" and each player in turn increases the number by 1, 2, or 3, but may not exceed 21; the player forced to say "21" loses. This can be modeled as a subtraction game with a heap of {{nowrap|21 − ''n''}} objects. The winning strategy for the two-player version of this game is to always say a multiple of 4; it is then guaranteed that the other player will ultimately have to say 21; so in the standard version, wherein the first player opens with "1", they start with a losing move.

The 21 game can also be played with different numbers, e.g., "Add at most 5; lose on 34".

A sample game of 21 in which the second player follows the winning strategy:

{| class="wikitable"
! Player !! Number
|-
| 1 || 1
|-
| 2 || 4
|-
| 1 || 5, 6 or 7
|-
| 2 || 8
|-
| 1 || 9, 10 or 11
|-
| 2 || 12
|-
| 1 || 13, 14 or 15
|-
| 2 || 16
|-
| 1 || 17, 18 or 19
|-
| 2 || 20
|-
| 1 || 21
|}

=== The 100 game ===
A similar version is the "100 game": Two players start from 0 and alternately add a number from 1 to 10 to the sum. The player who reaches 100 wins. The winning strategy is to reach a number in which the digits are subsequent (e.g., 01, 12, 23, 34,...) and control the game by jumping through all the numbers of this sequence. Once a player reaches 89, the opponent can only choose numbers from 90 to 99, and the next answer can in any case be 100.

=== A multiple-heap rule ===

{{See also|Wythoff's game}}
In another variation of nim, besides removing any number of objects from a single heap, one is permitted to remove the same number of objects from each heap.

=== Circular nim ===

{{See also|Kayles}}
Yet another variation of nim is "circular nim", wherein any number of objects are placed in a circle and two players alternately remove one, two or three adjacent objects. For example, starting with a circle of ten objects,

 . . . . . . . . . .

three objects are taken in the first move

 _ . . . . . . . _ _

then another three

 _ . _ _ _ . . . _ _

then one

 _ . _ _ _ . . _ _ _

but then three objects cannot be taken out in one move.

=== Grundy's game ===

In [[Grundy's game]], another variation of nim, a number of objects are placed in an initial heap and two players alternately divide a heap into two nonempty heaps of different sizes. Thus, six objects may be divided into piles of 5+1 or 4+2, but not 3+3. Grundy's game can be played as either misère or normal play.

=== 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.

=== Index-''k'' nim ===

A generalization of multi-heap nim was called "nim<math>{}_k</math>" or "index-''k''" nim by [[E. H. Moore]],<ref>Moore, E. H. ''A Generalization of the Game Called Nim''. [https://www.jstor.org/stable/1967321 Annals of Mathematics 11 (3), 1910, pp. 93–94]</ref> who analyzed it in 1910. In index-''k'' nim, instead of removing objects from only one heap, players can remove objects from at least one but up to ''k'' different heaps. The number of elements that may be removed from each heap may be either arbitrary or limited to at most ''r'' elements, like in the "subtraction game" above.

The winning strategy is as follows: Like in ordinary multi-heap nim, one considers the binary representation of the heap sizes (or heap sizes modulo ''r''&nbsp;+&nbsp;1). In ordinary nim one forms the XOR-sum (or sum modulo 2) of each binary digit, and the winning strategy is to make each XOR sum zero. In the generalization to index-''k'' nim, one forms the sum of each binary digit modulo ''k''&nbsp;+&nbsp;1.

Again, the winning strategy is to move such that this sum is zero for every digit. Indeed, the value thus computed is zero for the final position, and given a configuration of heaps for which this value is zero, any change of at most ''k'' heaps will make the value non-zero. Conversely, given a configuration with non-zero value, one can always take from at most ''k'' heaps, carefully chosen, so that the value will become zero.

=== Building nim ===

Building nim is a variant of nim wherein the two players first construct the game of nim. Given ''n'' stones and ''s'' empty piles, the players, alternating turns, place exactly one stone into a pile of their choice.<ref>{{cite arXiv|last1=Larsson|first1=Urban|last2=Heubach|first2=Silvia|author2-link= Silvia Heubach |last3=Dufour|first3=Matthieu|last4=Duchêne|first4=Eric|title=Building Nim|eprint=1502.04068|class=cs.DM|year=2015}}</ref> Once all the stones are placed, a game of Nim begins, starting with the next player that would move. This game is denoted ''BN(n,s)''.

=== Higher-dimensional nim ===

''n''-d nim is played on a <math>k_1\times\dots\times k_n</math> board, whereon any number of continuous pieces can be removed from any hyper-row. The starting position is usually the full board, but other options are allowed.<ref>{{cite web|url=http://poj.org/problem?id=1021 |title=1021 - 2D-Nim |publisher=Poj.org |access-date=2019-01-09}}</ref>

=== Graph nim ===

The starting board is a disconnected graph, and players take turns to remove adjacent vertices.<ref>{{Cite journal |last=Erickson |first=Lindsay Anne |date=2011 |title=The Game of Nim on Graphs |url=https://library.ndsu.edu/ir/handle/10365/32839 |journal=North Dakota State University |language=en}}</ref>

=== Candy nim ===

Candy nim is a version of normal-play nim in which players try to achieve two goals at the same time: taking the last object (in this case, candy) and taking the maximum number of candies by the end of the game.<ref>{{Cite arXiv|last=Rubinstein-Salzedo|first=Simon|date=18 May 2018|title=P Play in Candy Nim|class=math.CO |eprint=1805.07019}}</ref>