Number Duel Math

The Nim Game and the Sprague-Grundy Theorem

Imagine a simple game: there are piles of stones on a table. Two players take turns removing stones. On each turn, you pick one pile and take any number of stones from it (at least one). The player who takes the last stone wins.

This is Nim, and it is one of the most important games in mathematics. Not because people play it for fun (though they do), but because understanding Nim gives you the tools to solve an entire family of strategy games.

The Basic Game

Let us start with a concrete example. Three piles: 3, 4, and 5 stones.

Pile A: ●●●
Pile B: ●●●●
Pile C: ●●●●●

You go first. What is the winning move? Intuition will not help here — the answer involves binary arithmetic.

The Binary Trick

Charles Bouton proved in 1901 that Nim has a complete solution. The key is the nim-sum: the XOR (exclusive or) of all pile sizes, computed in binary.

For our example (piles of 3, 4, 5):

  3 = 0 1 1
  4 = 1 0 0
  5 = 1 0 1
XOR ---------
      0 1 0  =  2

Bouton's theorem states:

If the nim-sum is 0, the position is losing (the next player to move will lose with perfect play).
If the nim-sum is non-zero, the position is winning (the next player can force a win).

Since our nim-sum is 2 (non-zero), the first player can win. The winning move is to remove stones from a pile so that the new nim-sum becomes 0.

We need to find a pile where removing some stones makes the total XOR zero. Try pile C (5 stones):

  3 = 0 1 1
  4 = 1 0 0
  ? = 0 1 1  (we need XOR = 0, so ? must be 3)

So removing 2 stones from pile C (5→3) is the winning move. After this, all piles are 3, 4, 3, and the nim-sum is 0. Now the opponent is in a losing position — no matter what they do, you can always respond to restore nim-sum 0.

Why XOR?

The reason XOR works is subtle and beautiful. XOR has a property called self-inverse: a ⊕ a = 0. This means that if you split any pile into two groups and XOR them together, matching bits cancel out. In Nim, the winning strategy is to make your move cancel out all the "excess" bits, leaving a balanced (zero nim-sum) position for your opponent.

Think of it this way: a nim-sum of 0 means the piles are "paired up" in binary. Whatever your opponent takes from one pile, you can take a corresponding amount from another pile to restore the pairing. This is why the opponent cannot escape — you always have a matching response.

Variants of Nim

Nim has many variants, each with its own mathematical structure:

Bash Game (Bachet's Game)

A single pile of N stones. Each player can take 1 to K stones. Who wins?

Answer: if N is a multiple of (K+1), the second player wins. Otherwise, the first player wins by taking N mod (K+1) stones, then mirroring the opponent's moves to maintain multiples of (K+1).

This is the simplest possible take-away game, and it already contains the seed of the general theory: the losing positions form a regular pattern, and the winning strategy is to push your opponent onto those positions.

Wythoff's Game

Two piles. You can remove any number of stones from one pile, or the same number from both piles simultaneously. This small change makes the game much harder to analyze.

The losing positions follow a remarkable pattern involving the golden ratio φ = (1+√5)/2:

(a₁, b₁) = (⌊1·φ⌋, ⌊1·φ²⌋) = (1, 2)
(a₂, b₂) = (⌊2·φ⌋, ⌊2·φ²⌋) = (3, 5)
(a₃, b₃) = (⌊3·φ⌋, ⌊3·φ²⌋) = (4, 7)
(a₄, b₄) = (⌊4·φ⌋, ⌊4·φ²⌋) = (6, 10)
...

These are called Beatty sequences, and they guarantee that the losing positions never overlap and cover every positive integer exactly once. The golden ratio appears because it is the most irrational number — the one hardest to approximate with rationals — which prevents the sequences from colliding.

Subtraction Games

A single pile where you can only remove numbers from a given set S. For example, if S = {1, 3, 4}, you can take 1, 3, or 4 stones. These games develop periodic patterns that can be computed by dynamic programming.

The Sprague-Grundy Theorem

Here is the breakthrough. In 1935, Roland Sprague and Patrick Grundy independently proved that every impartial two-player game is equivalent to a Nim pile.

"Impartial" means both players have the same available moves (unlike chess, where White and Black have different pieces). "Equivalent" means the game has the same winning/losing structure as a Nim pile of some specific size.

The theorem works by assigning a Grundy number (also called a "nimber") to every position:

A position with no moves gets Grundy number 0 (losing).
For any other position, the Grundy number is the mex (minimum excludant) of the Grundy numbers of all positions you can reach in one move. Mex is the smallest non-negative integer not in the set.

Example: if from position P you can move to positions with Grundy numbers {0, 1, 3}, then the Grundy number of P is mex{0, 1, 3} = 2.

The power of this theorem is that you can analyze any impartial game by computing Grundy numbers, and then treat the whole thing as a game of Nim. If a game is the "sum" of several independent sub-games (like Nim itself is the sum of individual piles), you XOR their Grundy numbers together — exactly like the nim-sum.

Connection to Number Duel

The games in Number Duel are not purely impartial (players own different numbers), but the same style of thinking applies:

In Sum Duel, every move changes the available cells and the opponent's options. Like Nim, you want to leave the opponent in a "losing position" — a board state where no good move exists.
In Fifteen Duel, the game is equivalent to tic-tac-toe, which has been completely solved. The first player can always force a draw.
The concept of Grundy numbers is directly useful: if you can compute which board positions are "winning" and "losing," you can play perfectly.

The Sprague-Grundy theorem is the theoretical foundation for this kind of analysis. It tells us that no matter how complicated the game looks, underneath there is always a Nim-like structure waiting to be found.

Nim in Computer Science

Beyond games, Nim has practical applications:

Network protocols: The XOR-based balancing in Nim is related to parity checks in error-detecting codes.
Compiler theory: Grundy numbers appear in the analysis of pebble games used to model register allocation.
Artificial intelligence: The minimax and Sprague-Grundy analysis of games is foundational to game-tree search algorithms used in chess engines and game AI.

Try the Theory

In Number Duel, the AI uses game-tree search to evaluate positions. The same mathematical principles — computing the value of each position, looking ahead to find forcing moves — are at work. When you play against the AI, you are doing a human version of what the Sprague-Grundy theorem formalizes.