Nim is a very simple game. Like Magic Squares, it's based on Boolean arithmetic and, in addition, a binary representation of integers. The most important operation for Nim is exclusive or or XOR defined by the following table

^ | 0 | 1 |

0 | 0 | 1 |

1 | 1 | 0 |

XOR applies bitwise to the binary representation of two or more numbers. For example, if x=7 and y=11 are two decimal numbers then their binary representations will be

_{2}=111 and (y)

_{2}=1011,

respectively. Therefore, x ^ y = 1100.

If a, b, c denote the number of checked boxes in the three consecutive rows, then the winning move should leave

(1) | a ^ b ^ c = 0. |

Quite often this would imply that the sum of two of the numbers equals the third one. For example, take a=1, b=4, c=5. However, it's not always the case. For example, if a=3, b=5, c=6 with 3^5^6=0. The reverse does not hold either (say, consider a=3, b=5, c=8. In this case, 3^5^8 = 14). Oftentimes such simplified strategy would result in loosing initiative to your computer which will never give it back.

Now, bit is a position in a binary representation. There is a 0th bit (the rightmost one), the next is 1st, and so on. A bit is said to be turned on if the corresponding digit is one. Otherwise, it's turned off. The relationship a^b^c=0 is equivalent to saying that, considering all three numbers, every bit is turned on an even number of times, i.e., either 0 or 2.

Here is a proof. First of all, if after your move (1) holds while a, b, c are not 0, your opponent can't win on the next move. Condition (1) assures that for every bit turned on there is another bit on but in a different row. Since at every turn a player is allowed to uncheck boxes only in one row, it is impossible to turn all the bits off in one move.

What must be shown is this:

*A) Any move in a position where (1) holds will result in a position where (1) does not hold.*

*B) In a position where (1) does not hold there is always a move that leaves (1) true.
*

To prove A) let us assume (1) and that c is not 0. Assume also that after c' boxes have been unchecked in the third row we still have

(2) | a ^ b ^ (c-c') = 0. |

However, notice that (1) is equivalent to a^b = c whereas (2) is the same as a^b = c-c'. Therefore, c'=0. Which does not constitute a move. Contradiction.

Proving B) will actually be giving away the algorithm used by the computer. Thus assume (1) does not hold, i.e. a^b^c = X different from 0. The most significant bit of X was contributed either by all three numbers or by just one of them. Let Y denote the binary number corresponding to this bit. Since it makes no difference let us assume that it's c that has contributed the most significant bit of X. With this we make a decision on our next move to uncheck boxes in the third row. The question is how many. The answer is clear from the previous - remove (c - (a^b)) checks. After that move the third row will contain a^b boxes so that a^b^(a^b)=0. We only have to prove that

(3) | c - (a^b) > 0. |

Let Z denote the binary number comprising bits from c that canceled out by a^b. Then (c-Z) => Y > (a^b-Z) which proves (3).

In practical terms, the program first finds the largest of a&X, b&X, and c&X. The largest of these three numbers contains the most significant bit of X. Here conjunction & is defined by the following table

& | 0 | 1 |

0 | 0 | 0 |

1 | 0 | 1 |

Assume c&X is the largest of the three numbers. Then remove from the c's row (c-a^b) boxes. This number is bound to be positive and, after this operation, rows will contain a, b, and a^b boxes, respectively. These quantities satisfy (1).

If, say, a&X proved to be the maximum, remove (a-b^c) boxes from the first row.

The right move is not always unique. For example, assume we have the following distribution:

Row | #Boxes | Binary |

1 | 19 | 10011 |

2 | 20 | 10100 |

3 | 21 | 10101 |

Note that in this case X=19^20^21=(10010)_{2}=18 with the most significant bit corresponding to 16. The bit has been contributed by all three rows. Therefore, for all three rows there exists a winning move:

Take from row | #Boxes | Remains in rows |

1 | 18=(19-20^21) | 1,20,21 |

2 | 14=(20-19^21) | 19,6,21 |

3 | 14=(21-19^20) | 19,20,7 |

The game of Nim and the XOR operation are so fundamental in the Theory of Impartial Games that the latter has been often called a *nim-sum*. Nim has many incarnations of which some do not at all have an obvious relationship to the game. *Nim-sum* is even more widely spread and appears as an agent that glues together even not Nim - like games. Here is a list of pertinent games available at this site:

## Reference

- D.Fomin,S.Genkin,I.Itenberg,
*Mathematical Circles (Russian Experience)*, AMS, 1996 - M.Gardner,
*Hexaflexagons and other mathematical diversions*, The University of Chicago Press, 1988 - R.J.Wilson,
*Graphs and Their Uses*, MAA, New Math Library, 1990.

Copyright © 1996-2018 Alexander Bogomolny

64241041 |