Nim

Ancient Origins

Nim is an ancient mathematical game of strategy with origins dating back thousands of years to ancient China (known as Jianshizi, or "picking stones"). In European history it was played with matchsticks, coins, or counters.

The Rules

• Two players take turns removing objects from distinct heaps (piles).
• On your turn, you must take at least 1 object.
• You may take any number of objects, provided they all come from the same heap.
• Misère Play (Default): The player who takes the last remaining object loses!
• Normal Play: The player who takes the last remaining object wins.

The Secret of Nim (Bouton's Theorem, 1901)

In 1901, Harvard mathematician Charles L. Bouton proved that Nim can be completely solved using binary arithmetic and the bitwise XOR operation (called the Nim-sum, denoted \(\oplus\)).

Convert the number of objects in each pile into binary:

• Pile 1: 3 tokens = 0 1 1
• Pile 2: 4 tokens = 1 0 0
• Pile 3: 5 tokens = 1 0 1

Sum each column in binary without carry (addition modulo 2). If all columns contain an even number of 1s, the Nim-sum is 0 (a balanced or P-position). If any column has an odd number of 1s, the Nim-sum is \(\neq 0\) (an unbalanced or N-position).

The Winning Formula: Whenever you are in an unbalanced state (\(\text{Nim-sum} \neq 0\)), there is always at least one legal move that leaves a balanced state (\(\text{Nim-sum} = 0\)) for your opponent. Your opponent is then mathematically guaranteed to return an unbalanced state, allowing you to control the game from start to finish!