## Nim

### Strategy

Here's a simple procedure to find whether a Nim position has a winning move, and if so, what it is.

First imagine each row partitioned up into groups containing a power of two dots (1, 2, 4, 8, 16 etc). So, with the starting position 5 7 9:

Now cancel out pairs of partitions of the same size. So in this example we can cancel out the two groups of size 4, and two of the groups of size 1:

If all the groups are cancelled out the position is said to have a zero Nim-sum, and it's a losing position for the next player to move. The best they can do it to make a move that leaves the position as complicated as possible in the hope that the opponent will make a mistake.

If there are any groups not cancelled out, the next player can win by removing dots to make the Nim-sum zero. Here Blue's winning move is to remove 7 counters from the bottom row:

Whatever Red does will make the Nim-sum non-zero again, and Blue can find a move to make it zero, or win the game.

**Mathematics**

Mathematically, the Nim-sum is obtained by writing the size of each row as a binary number, and then taking the exclusive-or of these numbers. In this example the exclusive-or of 101, 111, and 1001 is 1011, or 11 in decimal.

To find the winning move: find a row such that the Nim-sum of the remaining rows is less than the number of dots in the row. The winning move is then to remove dots from the row to make these numbers equal. However, unless you are good at doing binary arithmetic in your head the partitioning method described above is easier to use when playing the game.