Probably everyone knows that the P-positions (previous player has won) in Nim are exactly those such that , where denotes bitwise XOR. For example, is a P-position, because , whereas one glance at shows it is an N-position (next player wins), because only the pile of size contains in binary. Any winning move must take at least counters from this pile: doing so leaves a pile of size , which is ideal for balancing the contribution from the other piles. Therefore we leave counters, taking , reaching the P-position .
Every finite impartial game is equal to a nimber. Nim is unusual in that knowing the P-positions immediately determines all its nimbers: if and only if (disjoint sum of games) if and only if is a P-position.
Theorem. The nimber of is .
Proof. By the previous paragraph, it suffices to find a winning move when with . By induction, we may assume that all options of have their expected nimbers. By reordering piles we may assume without loss of generality that where and . We take all but counters from the first pile, pause to admire the situation, and then take further counters to leave exactly . The parenthetical quantity is
so this is always possible.
A small generalization of this argument finds explicit moves giving options of with all nimbers with .
Example. Before I learned about Combinatorial Game Theory I got thrashed at Nim by someone whose main tactic was to reduce to the zero position . (Of course my opponent could also win any non-balanced position with two piles.) In memory of this occasion, consider the position . To reach with , we observe that and both have in their binary expansion, but only has (present in the pile ). We mentally cancel out the s, leaving with target , and play, as a first step, to . We then calculate that
We must leave counters in the half-eaten pile of size ; since , this is always possible. For instance, if then since , we leave counters. Since , on restoring the cancelled subpiles, we reach a position of nimber , as required.
Strong players of games instinctively maximize their mobility. This principle gives a decent strategy for games ranging from Settlers of Catan (a resource acquisition game in which early mobility is essential) and Othello (in which weak players often minimize their mobility, by playing to maximizing their counters in the early game; typically this creates multiple good moves for the opponent) and even a reasonable heuristic for chess, albeit one that has been criticized by Turing. It can be seen at work in the proof and example above, where the half-eaten pile of size
gives us ample options.
Nim boils down to a fight over the nimber . With the end firmly in mind, let us ask for a generalization in which is replaced with , the analogue of defined with addition modulo . For instance,
and in the hoped for generalization, will have nimber and (this is just a restatement) options with nimbers , but not . Consider the option . This can be reached only by removing counters from both the piles of sizes and . So it seems we have to permit moves in multiple piles. The position with singleton piles shows that moves in up to piles may be required. So, as a first try, we make the following definition.
Definition. Naive -Nim is the impartial game in which each move consists of up to moves in Nim.
Thus, writing for Hamming distance, a position in naive -Nim has as an option if and only if for each and .
Suppose, inductively, that the options of have the required nimbers. Then has as options all with .
Sketch proof. Take maximal such that appears more often in than . Cancelling as in the example, we may assume that is the greatest power of appearing in the base -forms of . So and . Take subpiles from piles containing in -ary, and in a remaining pile of size take all but of its counters; then use its subpile of size to reach .
However, may well have further options. By the mex rule, the problem occurs when there is an option with . For instance, has the option , which has nimber . This destroys the inductive foundations for the sketch proof above. In fact in naive -Nim.
The obvious fix is to bar all moves taking counters in which . (The square brackets are used to distinguish moves from positions.) But still there are too many options: for instance should be a P-position with nimber but, according to the current rules, we can move by or to the P-positions and (which really do have nimber ). A computer search finds the following illustrative examples, listed with their intended nimber and the additional moves that must be made illegal:
Let denote the highest power of dividing , and let . Some inspection of these examples may suggest the following definition.
Definition. -Nim is naive -Nim barring any move taking counters such that
By the definition of , this generalizes our first attempted rule. Moreover, it bars any move not changing the purported nimber of . The following result is a corollary of Lemmas 3.1 and 3.2 in this paper of Irie.
Theorem [Irie] The nimber of the -Nim position is .
Proof. Let and let . Let and let be the greatest power of appearing in in -ary. Cancelling as before, we may assume that is the greatest power of appearing in the base -forms of . Similarly, we may cancel the powers with between and . So the only powers of that appear are between and . (This will guarantee that our move satisfies the valuation condition.) Now play as in the sketch proof, replacing with
Since is not an option of , the mex rule implies that the nimber of is , as required.
In fact Irie’s result is more general: a surprising effect of the valuation condition is that allowing moves in or more piles does not create options with new nimbers. This leads to the notion of the -saturation of a game. The main focus of Irie’s paper is the -saturation of Welter’s game, which is shown to have a remarkable connection with the representation theory of the symmetric group.
Back to naive -Nim
It seems that in many cases the nimbers in naive -Nim are given by ordinary (naive?) addition. For example, this is true for all -pile positions whenever . When , the exceptions for pile positions (in increasing order) with a small first pile are listed below.
- : ,
- : ,
- : ,
- : , .
For instance, the matrix below shows nimbers for with .
Once the pattern is established (this happens by ), the mex rule implies that it continues.