Fibonacci nim is one pile of counters. You open by taking anything from 1 to n−1 — never the whole pile — and after that nobody may take more than twice what the opponent just took. Whoever lifts the last counter wins.
The player to move loses exactly when the pile is a Fibonacci number. Over the 299 piles from 2 to 300 that is 11 of them, and they are the obvious 11: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.
👉 Live, runs in your browser: https://dev48v.infy.uk/game/day80-fibonacci-nim.html
Two halves that are never allowed to talk to each other
The solver knows the rules and nothing else. There is no Fibonacci number anywhere in it.
// the definition, memoised - no theory in here at all
function solveState(rem, cap) {
cap = Math.min(cap, rem);
for (let k = 1; k <= cap; k++) {
if (k === rem) return true; // took the last counter
if (!solveState(rem - k, 2 * k)) return true;
}
return false;
}
firstPlayerWins(n) = solveState(n, n - 1) // never the whole pile
The other half is zeckendorf(n) — every positive integer as a sum of non-consecutive Fibonacci numbers, by greedy subtraction. It knows arithmetic and has never heard of the game.
0 disagreements across all 299 piles. And the same rule holds one level down, over the whole state space rather than just the openings: for all 45,150 reachable (remaining, cap) pairs, the mover wins if and only if the smallest Zeckendorf term of what remains fits under the cap — 0 mismatches against the solver.
The strategy is replayed, not asserted
A theorem that says "a winning move exists" is cheap. This one is constructive, so the page plays it back through the solver instead of claiming it:
for (const n of winnablePiles) {
const z = smallestZeckTerm(n);
assert(z <= n - 1); // legal opening
assert(solveState(n - z, 2 * z) === false); // opponent is now lost
}
288 winnable piles replayed, 0 broken.
Every opening that feels right wins nothing
This is the part worth the controls. Judged by the solver, over the same 288 winnable piles:
| opening rule | piles it wins |
|---|---|
| smallest Zeckendorf term | 288 |
| largest Zeckendorf term | 0 |
| take the maximum allowed | 0 |
| take half the pile | 0 |
| largest Fibonacci that fits | 0 |
| always take 1 | 114 |
Four plausible rules — including one built from the same arithmetic read from the wrong end — win zero piles between them. "Always take 1" is the interesting near-miss at 114, and 114 is not a coincidence: it is exactly the count of piles whose Zeckendorf representation contains a 1. The page counts those two numbers by separate routes and they agree.
The correct take is small — mean 1075/288 ≈ 3.73 counters, never more than 2/7 of the pile (worst at n=7). It is still not bounded by a constant: at n=199 the right opening is 55.
"The" winning move is a lie the textbook statement tells
| winning openings | piles |
|---|---|
| none (the pile is lost) | 11 |
| exactly one | 70 |
| two | 143 |
| three | 75 |
218 of 288 winnable piles have more than one winning opening. At n=72 they are 1, 4 and 17; at n=300 they are 1, 12 and 67 — and the extras are usually not Fibonacci numbers at all. The Zeckendorf term is always the smallest of them, which is a real checkable property; the others have no tidy description.
What this does not claim
299 piles agreeing is strong evidence for the theorem. It is not the theorem, and the page says which range it verified. The memo is keyed on rem * 4096 + c, which is sound to n=300 and would silently collide long before it became a general solver. And nothing here makes the strategy playable — finding the smallest Zeckendorf term of 300 counters at a table is exactly as awkward as it sounds.
29 in-page checks, 1,016 verifier asserts, 0 failures. Vanilla JS, one file, no build step.