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

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 . 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. For instance, has the option with 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 but, according to the current rules, we can move by or to the P-positions and . 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 special case of Lemma 3.1 in this paper of Irie.

**Theorem [Irie]** The nimber of the -Nim position is .

*Proof.* 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.