You and Gribble alternate turns. Remove one or more gems from exactly one nonempty pile. You may empty that pile. Whoever takes the final gem wins. Click individual gems in the cavern to select them, then press End turn. Selected gems glow gold. Click a selected gem again to deselect it, or use Clear selection to choose a different pile. You can also Tab to a gem and press Enter or Space. Gribble plays optimally. Use Restart to try another approach.
Reveal the mathematical background
Nim is a finite, impartial game: both players have the same legal moves, there is no hidden information, and every move reduces the total. Charles L. Bouton published its mathematical solution in 1901–1902.
1. Write each pile size in binary
We normally write numbers in decimal, where the place values are 1, 10, 100, and so on. Binary uses only the digits 0 and 1, with place values that double: 1, 2, 4, 8, 16…, reading from right to left. A 1 means “include this value”; a 0 means “leave it out”.
For our piles of 3, 4, and 5 gems, we need just three columns, worth 4, 2, and 1:
Converting the pile sizes to binary
| Gems |
4s |
2s |
1s |
Meaning |
| 3 |
0 |
1 |
1 |
0 + 2 + 1 = 3 |
| 4 |
1 |
0 |
0 |
4 + 0 + 0 = 4 |
| 5 |
1 |
0 |
1 |
4 + 0 + 1 = 5 |
So 3 is 011, 4 is 100, and 5 is 101 in binary. The zero at the front of 011 does not change its value; it just keeps the columns lined up.
2. Combine the columns using XOR
The symbol ⊕ means exclusive OR, usually called XOR. For two binary digits, the result is 1 when they are different and 0 when they are the same: 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, and 1 ⊕ 1 = 0.
For several numbers, there is an easy shortcut: count the 1s in each column. An odd count gives 1; an even count gives 0. Zero is even too. Each pair of 1s cancels out.
This is not ordinary addition: you never carry anything into the next column. Work on each column separately.
Working out 3 ⊕ 4 ⊕ 5
| Number |
4s |
2s |
1s |
| 3 |
0 |
1 |
1 |
| 4 |
1 |
0 |
0 |
| 5 |
1 |
0 |
1 |
| Count of 1s |
2 (even) |
1 (odd) |
2 (even) |
| XOR result |
0 |
1 |
0 |
The result is 010 in binary. Read it using the same place values: 0 × 4 + 1 × 2 + 0 × 1 = 2. That is why 3 ⊕ 4 ⊕ 5 = 2. The XOR of all the pile sizes is called the nim-sum.
3. Use the result to choose a move
The goal is to leave your opponent a nim-sum of zero. Zero does not mean that there are no gems left: it means every binary column has an even number of 1s.
With piles of 3, 4, and 5, take 2 gems from the first pile, leaving 1, 4, and 5. Their binary forms are 001, 100, and 101. The 4s column now has two 1s, the 2s column has none, and the 1s column has two. Every count is even, so 1 ⊕ 4 ⊕ 5 = 0.
The nim-sum is not generally the number of gems to take; both happen to be 2 in this example. To find a move systematically, XOR each pile size with the nim-sum. If the result is smaller than that pile, reduce the pile to that result. Here, 3 ⊕ 2 = 011 ⊕ 010 = 001 = 1, so reduce the first pile from 3 to 1.
A nonzero nim-sum means the player whose turn it is can force a win by leaving zero after every move. A nonempty position with nim-sum zero is losing for the player about to move if the opponent plays perfectly. It is not an immediate loss; an opponent's mistake can still give you a chance.
Why it works
If the sum is S and a pile changes from a to b, the new sum is S ⊕ a ⊕ b. When S = 0, every legal change makes this nonzero, since a ≠ b. When S ≠ 0, choose a pile a with a 1 in S’s highest set bit and set b = a ⊕ S. Then b < a, so the move is legal, and the new sum is 0. Repeating this eventually leaves all piles empty after your move.
At university level, interpret XOR as vector addition over the field with two elements, and investigate the Sprague–Grundy theorem, which connects other finite impartial games to Nim.
The game works offline. The further-reading link needs an internet connection.