Overview
Nim is the most famous impartial game in combinatorial game theory. Its entire strategy is captured by a single binary quantity — the nim-sum.
How to solve The Game of Nim
- Compute the nim-sum: the XOR of all pile sizes (3 ⊕ 4 ⊕ 5 = 2).
- If it's non-zero you can win: find a pile whose XOR with the nim-sum is smaller than it.
- Reduce that pile to that value, making the nim-sum zero and handing your opponent a losing position.
The key insight
A position with nim-sum 0 is a loss for the player to move: any move breaks the balance, and the opponent can always restore it. So aim to leave a zero nim-sum after your turn.
Variations & echoes
- The Sprague–Grundy theorem shows every impartial game reduces to an equivalent Nim pile.
- Misère Nim (take the last stone and you lose) needs only a small tweak near the end.
Frequently asked questions
What if the nim-sum is already zero on my turn?
Then you're in a losing position against perfect play — your best hope is that the opponent slips up.