Nim

Nim is about as simple as a game gets. Lay out a few heaps of coins. Players take turns; on your turn you pick one heap and remove as many coins as you like from it — at least one. Whoever takes the last coin wins.

That's the whole game. No board, no dice, no hidden information. And yet, if you sit a beginner down against someone who knows the trick, the beginner will lose every single time — the expert can announce the winner before a coin is touched.

The reason is not cleverness or memory. It is a single arithmetic operation hiding inside the pile sizes. Nim is one of the rare games that mathematics has not just studied but completely solved: there is a known formula that tells you the perfect move in every position.

Here are three heaps of coins. On your turn, click a heap to remove coins from it; then the engine moves. The panel shows each heap size in binary and the XOR (the bitwise digital sum) of the column counts.

<p class="hint">{{hint}}</p>
<div id="heaps" class="heaps"></div>
<div class="panel">
  <div class="panel-title">{{panel_title}}</div>
  <div id="bits" class="bits"></div>
</div>
<div class="status" id="status">{{your_move}}</div>
<div class="btns">
  <button id="go" type="button">{{btn_take}}</button>
  <button id="reset" type="button" class="ghost">{{btn_new_game}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.heaps { display: flex; gap: 1.6rem; align-items: flex-end; min-height: 150px; margin: .4rem 0 .6rem; }
.heap { display: flex; flex-direction: column-reverse; gap: 4px; align-items: center; }
.heap-label { margin-top: .4rem; font: 600 13px system-ui; color: #1d3557; }
.coin { width: 34px; height: 14px; border-radius: 7px; background: #f1c40f; border: 1px solid #c79f0c; cursor: pointer; transition: transform .08s; }
.coin:hover, .coin.hl { transform: translateX(4px); background: #f7d33a; }
.coin.sel { background: #e63946; border-color: #c92f3c; }
.panel { background: #f4f7fa; border: 1px solid #d7e0e8; border-radius: 8px; padding: .55rem .7rem; margin: .3rem 0; }
.panel-title { font: 600 12px system-ui; color: #56657a; margin-bottom: .35rem; }
.bits { font: 700 15px ui-monospace, monospace; line-height: 1.5; white-space: pre; color: #1d3557; }
.bits .x0 { color: #0a7d33; }
.bits .x1 { color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

// Code not found

Watch the XOR line. The engine always tries to hand you a position where the XOR is zero — and from a zero position there is no move that keeps it zero, so you are forced to break it and the engine restores it. If you start from a position whose XOR is already zero, the engine is lost and you can win; otherwise it never slips. That single number is the entire theory of the game, made visible bit by bit.

How hard is Nim, really? The astonishing answer: not hard at all — it is completely solved.

• The winning rule. Compute the XOR (bitwise "exclusive or", also called the binary digital sum) of all the heap sizes. If it is nonzero, the player to move can win; if it is zero, the player to move will lose against perfect play. The winning move is always the one that makes the XOR zero again.
• Proven in 1901. The mathematician Charles L. Bouton of Harvard published the full analysis and the name "Nim", proving the XOR rule is both necessary and sufficient. This is a solved game in the strongest sense: optimal play is a closed-form formula, computable in time linear in the number of bits.
• It generalizes. The Sprague-Grundy theorem (Roland Sprague, 1935; Patrick Grundy, 1939) showed that every impartial game — every game where both players have the same moves and the last move wins — is equivalent to a single Nim heap of some size, its Grundy value. Nim is not just one solved game; it is the universal building block for an entire class of them.
• Where it sits. Finding the winning move is in P — trivially fast. This is the opposite end of the spectrum from games like chess, whose perfect play is intractable.

So Nim is the rare trophy: a game with no luck, no hidden state, and a complete, provably optimal strategy that fits in one line of arithmetic.

A game solved by one XOR turns out to touch a surprising amount of mathematics and computing:

• Combinatorial game theory: via Sprague-Grundy, the analysis of Nim becomes a toolkit for solving whole families of impartial games by reducing each to a Grundy value and XOR-ing them.
• The power of XOR: the same bitwise digital sum drives parity checks, RAID storage, simple checksums and the classic "find the unpaired element" trick. Nim is XOR's most charming demo.
• Error-correcting codes and puzzles: XOR-balanced positions are exactly the idea behind certain coin-weighing and hat-guessing puzzles, and behind parity-based codes.
• Teaching strategy: because the optimal rule is short and provable, Nim is a favorite first example of what it means to truly solve a game.

Understand Nim and you've met the cleanest example of a perfectly solved game — the bright opposite of the open and intractable problems like P vs NP.

Nim is a small miracle of certainty. There is no opening theory to memorize, no endgame database to consult — just a single rule: XOR the heaps, and move to make it zero. Bouton settled it in 1901, and Sprague and Grundy showed that this one game secretly contains every impartial game.

That is what "solved" really means. While most interesting questions in computing stay hard, open, or even provably undecidable, Nim sits at the other extreme — a game whose entire future you can read off one number. The next time you face those heaps of coins, you don't have to play well. You just have to count in binary.