The binary trick behind Nim
In standard Nim, players take any positive number of objects from a single pile. The player who takes the last object wins. The key is to combine pile sizes with XOR, a binary operation that keeps a bit only when it appears in an odd number of the numbers being combined.
Write each pile size in binary, then XOR the rows column by column. For example, piles of 3, 4, and 5 are `011`, `100`, and `101`. Their columns combine to `010`, or 2. This result is called the nim-sum.
Why a zero nim-sum matters
A position with a nim-sum of zero is losing for the player whose turn it is—assuming the other player responds correctly. From such a position, any legal move changes one pile, so the nim-sum becomes nonzero. But from any nonzero position, there is a move that makes it zero.
To find that move, XOR the nim-sum with a pile size that has a 1 in the nim-sum’s leftmost 1-bit. The result is smaller than that pile, so the player can reduce the pile to that size. With piles of 3, 4, and 5, the nim-sum is 2; changing the 3-pile to `3 XOR 2 = 1` means removing two objects. The remaining piles—1, 4, and 5—have a nim-sum of zero.
The strategy is a reply, not a recipe
A zero nim-sum does not guarantee a win regardless of what happens next. It gives the player a position from which to answer each opponent’s move by restoring zero. Eventually, the opponent must face a zero position with no winning move available. The binary calculation turns a game that looks like a contest over individual objects into a way of steering the whole set of piles.
