Editing Nim (section)

== Mathematical theory ==
Normal-play nim (or more precisely the system of [[nimber]]s) is fundamental to the [[Sprague–Grundy theorem]], which essentially says that in normal play every [[impartial game]] is equivalent to a nim heap that yields the same outcome when played in parallel with other normal play impartial games (see [[disjunctive sum]]).

While all normal-play impartial games can be assigned a nim value, that is not the case under the misère convention. Only [[Genus theory#Tame|tame games]] can be played using the same strategy as misère nim.

Nim is a special case of a [[poset game]] where the [[poset]] consists of disjoint [[Total order|chains]] (the heaps).

The evolution graph of the game of nim with three heaps is the same as three branches of the evolution graph of the [[Ulam–Warburton automaton]].<ref>{{cite arXiv |eprint=1405.5942|last1=Khovanova|first1=Tanya|last2=Xiong|first2=Joshua|title=Nim Fractals|class=math.CO|year=2014}}</ref>

Nim has been mathematically [[solved game|solved]] for any number of initial heaps and objects, and there is an easily calculated way to determine which player will win and which winning moves are open to that player.

The key to the theory of the game is the [[Binary numeral system|binary]] [[digital sum in base b|digital sum]] of the heap sizes, i.e., the sum (in binary), neglecting all carries from one digit to another. This operation is also known as "[[bitwise xor]]" or "vector addition over [[finite field|'''GF'''(2)]]" (bitwise addition modulo 2). Within [[combinatorial game theory]] it is usually called the '''nim-sum''', as it will be called here. The nim-sum of ''x'' and ''y'' is written {{nowrap|''x'' ⊕ ''y''}} to distinguish it from the ordinary sum, {{nowrap|''x'' + ''y''}}. An example of the calculation with heaps of size 3, 4, and 5 is as follows:

 [[Binary numeral system|Binary]] [[Decimal]]
 &nbsp;
   011<sub>2</sub>    3<sub>10</sub>    Heap A
   100<sub>2</sub>    4<sub>10</sub>    Heap B
   101<sub>2</sub>    5<sub>10</sub>    Heap C
   ---
   010<sub>2</sub>    2<sub>10</sub>    The nim-sum of heaps A, B, and C, 3 ⊕ 4 ⊕ 5 = 2

An equivalent procedure, which is often easier to perform mentally, is to express the heap sizes as sums of distinct [[Exponentiation|powers]] of 2, cancel pairs of equal powers, and then add what is left:

 3 = 0 + 2 + 1 =     2   1      Heap A
 4 = 4 + 0 + 0 = 4              Heap B
 5 = 4 + 0 + 1 = 4       1      Heap C
 --------------------------------------------------------------------
 2 =                 2          What is left after canceling 1s and 4s

In normal play, the winning strategy is to finish every move with a nim-sum of 0. This is always possible if the nim-sum is not zero before the move. If the nim-sum is zero, then the next player will lose if the other player does not make a mistake. To find out which move to make, let X be the nim-sum of all the heap sizes. Find a heap where the nim-sum of X and heap-size is less than the heap-size; the winning strategy is to play in such a heap, reducing that heap to the nim-sum of its original size with X. In the example above, taking the nim-sum of the sizes is {{nowrap|1=''X'' = 3 ⊕ 4 ⊕ 5 = 2}}. The nim-sums of the heap sizes A=3, B=4, and C=5 with X=2 are
: ''A'' ⊕ ''X'' = 3 ⊕ 2 = 1      [Since (011) ⊕ (010) = 001 ]
: ''B'' ⊕ ''X'' = 4 ⊕ 2 = 6
: ''C'' ⊕ ''X'' = 5 ⊕ 2 = 7
The only heap that is reduced is heap A, so the winning move is to reduce the size of heap A to 1 (by removing two objects).

As a particular simple case, if there are only two heaps left, the strategy is to reduce the number of objects in the bigger heap to make the heaps equal. After that, no matter what move the opponent makes, the player can make the same move on the other heap, guaranteeing that they take the last object.

When played as a misère game, nim strategy is different only when the normal play move would leave only heaps of size one. In that case, the correct move is to leave an odd number of heaps of size one (in normal play, the correct move would be to leave an even number of such heaps).

These strategies for normal play and a misère game are the same until the number of heaps with at least two objects is exactly equal to one. At that point, the next player removes either all objects (or all but one) from the heap that has two or more, so no heaps will have more than one object (in other words, so all remaining heaps have exactly one object each), so the players are forced to alternate removing exactly one object until the game ends. In normal play, the player leaves an even number of non-zero heaps, so the same player takes last; in misère play, the player leaves an odd number of non-zero heaps, so the other player takes last.

In a misère game with heaps of sizes three, four and five, the strategy would be applied like this:

{| class="wikitable"
! A !! B !! C !! Nim-sum !! Move
|-
| 3 || 4 || 5 || 010<sub>2</sub>=2<sub>10</sub> || I take 2 from A, leaving a sum of 000, so I will win.
|-
| 1 || 4 || 5 || 000<sub>2</sub>=0<sub>10</sub> || You take 2 from C
|-
| 1 || 4 || 3 || 110<sub>2</sub>=6<sub>10</sub> || I take 2 from B
|-
| 1 || 2 || 3 || 000<sub>2</sub>=0<sub>10</sub> || You take 1 from C
|-
| 1 || 2 || 2 || 001<sub>2</sub>=1<sub>10</sub> || I take 1 from A
|-
| 0 || 2 || 2 || 000<sub>2</sub>=0<sub>10</sub> || You take 1 from C
|- 
| 0 || 2 || 1 || 011<sub>2</sub>=3<sub>10</sub> || The normal play strategy would be to take 1 from B, leaving an even number (2) heaps of size 1.  For misère play, I take the entire B heap, to leave an odd number (1) of heaps of size 1.
|-
| 0 || 0 || 1 || 001<sub>2</sub>=1<sub>10</sub> || You take 1 from C, and lose.
|}