CS Unplugged activity
Nim: the binary secret
If you’ve played multi-pile Nim on Nim: the take-away game, you already know there’s a pattern to which piles are safe to leave your opponent and which ones lose no matter what you do. Here’s the pattern, worked out in full. It’s exact: it will tell you whether any position is a win or a loss, and if it’s a win, exactly which move to make.
The trick uses binary, the same 0-and-1 way computers store every number. If you’ve never worked with binary before, this page still works, just go a little slower through Step 1.
Step 1: write every pile in binary
Binary numbers use place values that double each time you move left: 1, 2, 4, 8, 16, and so on, instead of the 1, 10, 100 you’re used to. Writing a pile size in binary just means figuring out which of those place values add up to it, the same way you did with dot cards if you’ve done that activity.
Take the piles 3, 5, 7. In binary:
| Pile | 4 | 2 | 1 |
|---|---|---|---|
| A (3) | 0 | 1 | 1 |
| B (5) | 1 | 0 | 1 |
| C (7) | 1 | 1 | 1 |
| Nim-sum | 0 | 0 | 1 |
Each pile gets its own row, and every pile is written with the same number of digits (padded with leading zeros) so the columns line up. That lining up is the whole point, the next step only works if every number has digits in the same place values.
Step 2: add the columns without carrying
Now add straight down each column, but with one twist: no carrying. For each column, count how many piles have a 1 there. Write 1 in that column of the answer if that count is odd, and 0 if it’s even. That’s it, no tens to carry, no borrowing.
That answer row is called the nim-sum. For piles 3, 5, 7:
- Rightmost column: three 1s (odd) → 1
- Middle column: one 1 → 1
- Leftmost column: one 1 → 1
Nim-sum: 001, which is 1 in ordinary decimal.
Step 3: the nim-sum tells you if you can win
If the nim-sum is 0, you’re in a losing position. No matter what you do, your opponent can always answer in a way that brings the nim-sum back to 0, and eventually you’ll run out of stones with nothing left to take. This assumes your opponent knows the trick too. If they don’t, you can still win by luck, just not by strategy.
If the nim-sum isn’t 0, you have a winning move, one that leaves your opponent at nim-sum 0. Piles 3, 5, 7 have nim-sum 1, which isn’t 0, so there’s a winning move to find.
Step 4: find the winning move
Look at the leftmost column where the nim-sum has a 1. Find a pile that also has a 1 in that same column, and check: does that pile, combined with the nim-sum the same no-carry way, give a smaller number than the pile started with? If so, that’s your move: shrink that pile down to that smaller number.
For 3, 5, 7 (nim-sum 1): pile A (3) combined with 1 the no-carry way gives 2, which is smaller than 3. So the move is: take 1 stone from pile A, leaving it at 2. Check it: 2, 5, 7 now has nim-sum 0, exactly what you want to hand your opponent.
Take 1 from pile A (3 down to 2).
A second worked example, with four piles
The steps don’t change with more piles, there’s just one more row.
| Pile | 4 | 2 | 1 |
|---|---|---|---|
| A (1) | 0 | 0 | 1 |
| B (4) | 1 | 0 | 0 |
| C (5) | 1 | 0 | 1 |
| D (6) | 1 | 1 | 0 |
| Nim-sum | 1 | 1 | 0 |
Nim-sum: 110, which is 6. Not zero, so there’s a winning move. Take 2 from pile B (4 down to 2). Check it yourself: write out the new piles and add their binary columns without carrying, you should get all zeros.
Not every position has a winning move
Here’s one that doesn’t:
| Pile | 4 | 2 | 1 |
|---|---|---|---|
| A (2) | 0 | 1 | 0 |
| B (4) | 1 | 0 | 0 |
| C (6) | 1 | 1 | 0 |
| Nim-sum | 0 | 0 | 0 |
Nim-sum: 000, which is 0. That’s zero, so this is a losing position: No winning move: any move you make leaves your opponent a winning position. Try it yourself on paper. Whatever pile you shrink and however much you take, at least one column stops matching, and the nim-sum becomes nonzero, a winning position for whoever moves next. That’s your opponent.
Practice: classify these positions
For each position, decide if the player about to move has a winning move. If they do, use the steps above to find it. Write your answer in the table.
| # | Piles | Win or lose? | Winning move (if any) |
|---|---|---|---|
| 1 | A 4, B 7, C 10 | ||
| 2 | A 5, B 7, C 9, D 11 | ||
| 3 | A 3, B 4, C 5 | ||
| 4 | A 1, B 4, C 5 | ||
| 5 | A 2, B 5, C 8, D 12 | ||
| 6 | A 7, B 9, C 14 | ||
| 7 | A 8, B 9, C 10 | ||
| 8 | A 1, B 2, C 3 |
Want unlimited fresh positions instead, with the binary work filled in for each one? Try the Nim position generator.
Check your answers
“Win” means the player about to move has a winning move. Pile letters match the order piles are listed above.
1. Piles A 4, B 7, C 10. Nim-sum 1001 (9). Win. Take 7 from pile C (10 down to 3).
2. Piles A 5, B 7, C 9, D 11. Nim-sum 0000 (0). Lose. No winning move: any move you make leaves your opponent a winning position.
3. Piles A 3, B 4, C 5. Nim-sum 010 (2). Win. Take 2 from pile A (3 down to 1).
4. Piles A 1, B 4, C 5. Nim-sum 000 (0). Lose. No winning move: any move you make leaves your opponent a winning position.
5. Piles A 2, B 5, C 8, D 12. Nim-sum 0011 (3). Win. Take 1 from pile A (2 down to 1).
6. Piles A 7, B 9, C 14. Nim-sum 0000 (0). Lose. No winning move: any move you make leaves your opponent a winning position.
7. Piles A 8, B 9, C 10. Nim-sum 1011 (11). Win. Take 5 from pile A (8 down to 3).
8. Piles A 1, B 2, C 3. Nim-sum 000 (0). Lose. No winning move: any move you make leaves your opponent a winning position.
Version history
- Loading commit history…