nim /nIm/ n. a game in which two players must alternately take one or more objects from one of several heaps and seek either to avoid taking or to take the last remaining object. [20th c.: perh. f. archaic nim take (as NIMBLE, or G nimm imper. of nehmen take]
—The Oxford English Dictionary
Consider a game of nim, played with 2 players, where the loser takes the last piece, with N separate piles of pieces. Let ni be the number of pieces in pile i; i∈{1, 2, 3, ..., N}, ni∈{0, 1, 2, ...}. Let the vector n = (n1, n2, n3, ..., nN) represent the state of the game at any point.
Define a winning position to be one where, if you have placed the game in that position, no matter what moves your opponent makes, you can play into another winning position each turn, and your opponent will always lose. Let W be the set of all possible winning positions. Note that the null position where all piles are empty is not a winning position.
Theory 1: If ni∈{0,1}∀i then n∈W iff EOR(n)=1
Theory 2: If ∃ni>1 then n∈W iff EOR(n)=0
Theory 3: If ∃nk>0 and nnot∈W then ∃j∈{1,2,3,...,N} and ∃n'∈W s.t. 0≤n'j<nj and n'i=ni∀i≠j
EOR (otherwise denoted XOR) means 'exclusive OR'. This is a Boolean operator whose properties can be found in many computing and mathematics textbooks. The EOR function is commutative, a EOR b = b EOR a, and associative, (a EOR b) EOR c = a EOR (b EOR c), and furthermore it has the more unusual property that if a EOR b = c then a EOR c = b. The notation EOR(n) is equivalent to (n1 EOR n2 EOR n3 EOR ... EOR nN). The function EOR(n) therefore represents the exclusive ORing of each ni in any order. [Further information on EOR]
Wherever I have used the symbol '∃', I have meant it to mean 'there exists at least one'. These theories do not imply uniqueness of existence (which would be represented by '∃!'), nor do they imply non-uniqueness.
Theory 1: If every pile has at most one piece in it, then this is a winning position if and only if EOR(n)=1.
Theory 2: If there is at least one pile with more than one piece in it, then this is a winning position if and only if EOR(n)=0.
Theory 3: If there is at least one pile with at least one piece in it (i.e. the game is not over) and the game is not at a winning position, then there exists at least one move (consisting of taking at least one piece from one pile only) which will put the game into a winning position.
Given that each pile has at most one piece in it, each turn the only moves either player can make are to take one piece from one of these piles. As such, if there are an even number of pieces (piles) left, you will always take the last piece and lose. If there are an odd number of pieces (piles) left, then your opponent will always take the last piece and lose.
If every pile has either 0 or 1 pieces in it, then EOR(n)=0 if there are an even number of piles with 1 piece in, and EOR(n)=1 if there are an odd number of piles with 1 piece in. EOR(n) can take no other values in this situation. Therefore EOR(n)=1 is true of all possible winning positions, any other value of EOR(n) gives a position from which you cannot win.
I have not produced a complete general proof of theory 2 yet, although I am sure it is possible. I can produce a proof for a given finite range of n. I believe that either a proof by induction or a space-filling argument should work.
Sketches: {0,1}^N hypercube is filled. You cannot move from one winning position to another in one move. A move can be represented as a single straight line movement parallel to axes in the direction of the origin. Working out from the origin (and the {0,1}^N hypercube) the closest free space that cannot move to a winning position must be a winning position (-proof?) leading to a space-filling argument. This forms an EOR pattern by inspection, but is there are proof of how an EOR pattern looks? I think that's where the key is. Only if I know mathematically what EOR looks like, can I prove that this looks the same.
A winning position cannot lead to another winning position in one move (as this would contradict its definition). The purpose of theory 3 is to show that for any position that is not a winning position, you can always reach another winning position. This then allows for a construction of a winning strategy for nim. Consider, then, the three following mutually exclusive situations...
Situation 1: no piles have more than one piece. Following on from the proof of theory 1 above, if the game is not in a winning position, taking away 1 piece (from any of the remaining piles with pieces) will give a position which is a winning position. Note that the theory has to specify at least one pile with pieces in, since otherwise the game is not in a winning position, but no other moves are possible (i.e. someone has taken the last piece and therefore lost the game).
Situation 2: one pile has more than one piece. If you take enough pieces from the single largest pile, you can put the game into the situation where all piles have at most one piece in them. Leaving this pile with either one or no pieces as appropriate will therefore be a winning position. Note that this is also the only possible move into a winning position in this situation, since leaving the game in any other position will allow your opponent to take enough pieces from the largest pile to leave a winning position.
Situation 3: more than one pile has more than one piece. If we assume theory 2 holds, then I can prove theory 3 for this stuation as well. Using the notation of theory 3, EOR(n)>0. Say we have EOR(n)=x. We wish to find n' such that EOR(n')=0 (this comes from theory 2; we can only take from one pile, so at least one pile will have more than one piece in it after this move). From the properties of the EOR function, we can say that EOR(n, x)=0=EOR(n'). Considering the properties of EOR, it suffices therefore to find nj such that EOR(nj, x)=nj' and nj'<nj. This is possible so long as nj has a 1 in the same binary digit as the highest binary digit of x that is 1. And at least one such number must exist in n since EOR(n) (which is x) has a 1 in this digit.
So having shown that theory 3 holds in all three of the above situations, and that these situations are mutually exclusive and together form the total possible situations, this proves theory 3 in general (providing that theory 2 also holds).