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
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
72010302