The Secret of Nim

A Mathematical Game of Strategy

“The Game of Nim is a battle of wits — where binary arithmetic decides the winner.”

Nim is a mathematical strategy game where two players take turns removing objects from heaps. The goal? Be the player who takes the last object. Though it seems complex, Nim hides a beautiful winning strategy based on binary arithmetic and the Nim-sum.

📜 Historical Context

The game of Nim has ancient roots, but its mathematical foundations were laid in 1901 by Charles L Bouton, who developed a complete mathematical theory of Nim based on binary addition modulo 2 — an operation equivalent to the bitwise XOR of heap sizes, now commonly called the Nim-sum. (Bouton, 1901).

• 1951: Inspired the Nimrod computer, one of the first gaming machines.
• Today: A cornerstone of combinatorial game theory.

🔗 Explore the code: GitHub — ratwolfzero/NIM

Image by the author

Image by the author

🎮 How to Play

1. Setup: Start with multiple heaps (e.g., sticks, stones). Adjust heap sizes in the interactive demo.
2. Turns: Players alternate removing any number of objects from a single heap.
3. Winning: Take the last object to win.

🔢 The Nim-Sum: Binary XOR (⊕)

The secret to winning lies in the Nim-sum, calculated via bitwise XOR (^).

How It Works

Binary Conversion:

• 5 (decimal) → 0101 (4-bit binary).

XOR Operation:

• 0 ^ 0 = 0 | 1 ^ 1 = 0
• 0 ^ 1 = 1 | 1 ^ 0 = 1

🧮 Example: Calculating the Nim-Sum

Take heaps of 1, 3, 5, 7:

Get Ralf Becker’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

HeapBinary10001300115010170111

Nim-sum = 0001 ⊕ 0011 ⊕ 0101 ⊕ 0111 = 0000 (0)

Every bit cancels out!

🏆 Winning Strategy

🔴 Unsafe State (Nim-sum ≠ 0)

• You can win if you play optimally.
• Force your opponent into a losing position.

🟢 Safe State (Nim-sum = 0)

• Any move you make gives your opponent the advantage.

Steps to Victory

1. Compute Nim-sum (h₁ ⊕ h₂ ⊕ … ⊕ hₙ).
2. If Nim-sum ≠ 0, find a heap hᵢ where:

reducing it to:

hᵢ’ = hᵢ ⊕ Nim-sum with hᵢ’< hᵢ

guarantees that the new Nim-sum becomes 0, putting your opponent in a losing position.

💡 Why This Works

By forcing Nim-sum = 0, you leave your opponent with no winning moves — just like tic-tac-toe’s perfect play!

In mathematical terms, each heap in Nim has a Grundy number equal to its size — a value that allows us to generalize Nim’s logic to many other games.

Beyond Nim: How Grundy Numbers Solve Impartial Games

While Nim itself is a classic and elegant game, the concept of Grundy numbers (also known as nimbers) extends far beyond it. These numbers provide a universal way to analyze and solve a wide range of impartial games — games where the available moves depend only on the state of the game, not on whose turn it is. By translating complex game positions into equivalent Nim heaps using Grundy numbers, we unlock a powerful and general winning strategy.

The winning strategy in Nim is based on these Grundy numbers. In Nim, the Grundy number for a heap is simply its size. In other impartial games, a position’s Grundy number is found by taking the Mex (Minimum Excluded value) of the set of Grundy numbers of all possible next moves. This means it’s the smallest non-negative integer not present in that set. This method allows us to reduce complex impartial games to Nim and apply the same winning strategy (see Sprague–Grundy theorem Wikipedia ).