Nim: the game you cannot lose
Helpful first: Binary from Counting to 31 on one hand. Ready if you can write 13 in binary without looking it up.
Tonight's idea
The rules. Put coins in piles, say 3, 5 and 7. Two players take turns. On your turn you choose one pile and take as many coins from it as you like, at least one. Whoever takes the last coin wins. That is all.
Play a few games of 1-2-3 with someone before reading on. You will start to feel that some positions are doomed: whoever has to move from them loses, if the other player is careful. Two equal piles, like 4-4, is one. Whatever you take from one pile, your opponent copies on the other, and they get the last coin.
The secret. Write each pile size in binary (see Counting to 31 on one hand) and stack them up, lining up the columns. Now count the 1s in each column. If every column has an even number of 1s, the position is balanced, and the player who has to move from it will lose against good play. If any column has an odd count, the position is unbalanced, and the player to move can win by making a move that balances it.
Charles Bouton proved this in 1901. It was the first game ever to be completely solved, and it was solved with binary, forty years before computers.
Unbalanced = find the move that makes every column even, then play it.
Watch one: 3, 5, 7. Your move.
| pile | 4s | 2s | 1s |
|---|---|---|---|
| 3 | 0 | 1 | 1 |
| 5 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 |
| count of 1s | 2 | 2 | 3 |
The 4s and 2s columns are even. The 1s column has three 1s: odd. Unbalanced, so there is a winning move. We need to fix the 1s column without breaking the others, which means changing a pile's 1s digit from 1 to 0 and nothing else. Take one coin from the 3 to make it 2 (binary 010). Now the columns count 2, 2, 2. Balanced. Hand it over.
Taking one from the 5 (making 4 = 100) or one from the 7 (making 6 = 110) also works. Check them.
Your turn
Tonight's core: the example and exercises 1 to 3. The rest can wait for another visit.
- Write out the binary table for 1-2-3. Is it balanced? If you are the first player in 1-2-3, do you want to be?
- Classify each position as balanced or unbalanced: 2-2, 4-6, 1-4-5, 2-3-4.
- For each unbalanced position in question 2, find a move that balances it. Say which pile and how many coins.
- 5-6-7. Find all the winning moves. (There is more than one.)
Hint
Only one column comes out odd. Every pile with a 1 in that column gives one winning move: turn that 1 into a 0 and leave its other digits alone. - The classic opening is 1-3-5-7, four piles. Should you offer to go first or second? Explain using the table.
- Play 3-5-7 against someone three times, going first and using the rule. Did you win all three? If not, check your binary table and your moves.
Practise against the computer at mathdetours.com/demos/nim.html, which can show the columns as you play.
Stretch: why it works
You need to convince yourself of two things.
From a balanced position, every move unbalances. You change exactly one pile. Changing a number changes at least one of its binary digits, so at least one column's count changes by one, from even to odd.
From an unbalanced position, some move balances. Look at the leftmost odd column. Some pile has a 1 there. Take that pile and flip its digit in every odd column (1 to 0 or 0 to 1). The new number is smaller, because its leftmost change was a 1 becoming a 0. So the move is legal and it fixes every column at once.
Put those together with the fact that the empty position 0-0-0 is balanced, and the player facing a balanced position is handed one again after every exchange, until they face 0-0-0 and have already lost. Write this argument out in your own words, as if explaining it to someone who has never seen binary.
Answers
- 1 = 01, 2 = 10, 3 = 11. Columns count 2 and 2: balanced. The first player in 1-2-3 loses against correct play, so you want to go second.
- 2-2 balanced. 4-6 unbalanced (100 and 110: the 2s column has one 1). 1-4-5 balanced (001, 100, 101: columns 2, 0, 2). 2-3-4 unbalanced (010, 011, 100: columns 1, 2, 1).
- 4-6: take 2 from the 6, leaving 4-4. 2-3-4: take 3 from the 4, leaving 2-3-1 (010, 011, 001: columns 0, 2, 2).
- 5 = 101, 6 = 110, 7 = 111: columns count 3, 2, 2, so only the 4s column is odd and we must turn a 1 in that column into a 0. Three choices: 5 to 1 (leaving 1-6-7), 6 to 2 (leaving 5-2-7), or 7 to 3 (leaving 5-6-3). Each leaves every column even. Check 1-6-7: 001, 110, 111, columns 2, 2, 2.
- 1 = 001, 3 = 011, 5 = 101, 7 = 111. Columns count 2, 2, 4: balanced. Whoever moves first from 1-3-5-7 loses against correct play. Offer to go second.
- Going first from 3-5-7, you can guarantee a win by leaving a balanced position after every move. If you lost, check your binary and your moves. Going second does not guarantee a win: your opponent can take one from the 3 and hand you the balanced position 2-5-7.
Stretch. The two facts together mean: if you hand your opponent a balanced position, they must hand you back an unbalanced one, and you can always balance it again. The piles shrink every turn, so the game ends, and it ends with your opponent facing 0-0-0, which is balanced and already lost.