Take What You Want, Never Twice as Much

A rule about restraint

Here is a game for two players. There is one pile of stones. On your turn you take some, at least one. Whoever takes the very last stone wins. So far this is the most boring game imaginable: the first player just sweeps the whole pile and wins.

So we add a single rule. On the opening move you may take anything except the whole pile. And from then on, you may never take more than twice what your opponent just took. Take three and I can take up to six. Take one and I am capped at two.

That one clause about restraint turns a trivial sweep into a real contest, and a surprisingly deep one. Play it against the perfect machine in the console above. When you have a way to win it will show you the single move that keeps it, and when you do not, it will tell you that too.

Try the pile of 17 first. It is winnable, and there is a clean opening. Then try the pile of 13, and notice that whatever you do, the machine walks it home. The difference between those two numbers is the whole story.

Which piles are already lost

Every position in a game like this is one of two kinds. Either the player about to move can force a win, or they cannot and a perfect opponent will beat them no matter what. Call the second kind locked. Solving the game means listing the locked piles, because once you have that list, play is mechanical: on your turn, find a move that hands your opponent a locked pile. If one exists you were winning; if none exists you were locked all along.

Run your eye along module 03. The locked piles, the ones you lose from moving first, are

1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

which is to say the Fibonacci numbers, each the sum of the two before it, and nothing else. Not the even numbers, not the multiples of anything, not a pattern you would have guessed from a rule about doubling. The oldest sequence in the book, sitting underneath a children's stone game.

That is the fact to explain: why should a rule that says "never take more than twice the last move" single out exactly the numbers 1, 1, 2, 3, 5, 8, …?

Every number is a sum of Fibonaccis

The answer runs through a theorem most people have never heard of, which is a shame because it is beautiful and it is easy. In 1972 the Belgian amateur Edouard Zeckendorf published the proof, though the result was known earlier: every positive integer can be written as a sum of Fibonacci numbers in exactly one way, if you are not allowed to use two that are adjacent in the sequence.

Seventeen is 13 + 3 + 1. Twenty is 13 + 5 + 2. Thirty-three is 21 + 8 + 3 + 1. There is always a decomposition, it is always unique, and it never uses two neighbouring Fibonaccis. Dial any pile size in module 02 and watch its pieces fall out.

A number that is a Fibonacci number is the boring case: its decomposition is just itself, a single piece, nothing smaller to hand off. Every other number has at least two pieces, and in particular a smallest one.

That smallest piece is the winning move.

Why the smallest piece wins

Say your pile is 20. Its pieces are 13 + 5 + 2, and the smallest is 2. Take 2, and you leave your opponent 18 stones with a cap of 4, since 2 × 2 = 4.

Now watch what they cannot do. To get back to safety they would need to strip away a whole Fibonacci piece of their own, and the smallest piece left in play is the 5. But they are capped at 4. They cannot reach the 5. Whatever they take, 1 through 4, they leave a pile that still has a smallest piece for you to shave off next, and you repeat. The pieces only ever get bigger as you climb the pile, so your cap always grows fast enough to reach the next one, and theirs never does.

The engine of the whole strategy is one small fact about the Fibonacci numbers, and module 02 checks it live for you: non-adjacent Fibonacci numbers are always more than twice apart. The next piece up is always more than double the piece below it. That gap is exactly the margin that keeps your opponent from undoing your move, and it is why the answer had to be Fibonacci and not some other sequence. The rule caps them at twice; the Fibonacci spacing puts the next escape at more than twice. The two numbers meet at the golden ratio, and the game turns on the sliver between them.

Peel a pile down this way and it can only end one place: on a single Fibonacci piece with a large enough cap to take it whole. You take it, and you take the last stone.

The same constant, a different door

This is the second game on this site that the golden ratio quietly decides. Wythoff's game wore φ on its sleeve: two piles instead of one, and its locked positions fall on two straight rays whose slope is φ ≈ 1.618, laid down by the golden ratio directly. This game hides the same constant one level down, inside the Fibonacci numbers, whose ratios march onto φ as they grow: 34/21, 55/34, 89/55, closing in on 1.618… one term at a time.

Two different rulebooks, two different-looking answers, one number underneath both. That is the habit combinatorial game theory never breaks. The surface of a game tells you almost nothing about the exact structure that decides it, and when you finally dig the structure out it is rarely the arithmetic you would have bet on. Turning Turtles looked nothing like Nim and was Nim exactly. Chomp had a winner you could prove exists without ever naming their move. And this pile of stones, governed by nothing but a rule about not being greedy, is run from top to bottom by the Fibonacci sequence and the golden ratio it grows toward.

You never need any of that to play. Take the smallest piece, then never surrender the lead. But the reason it works is that the whole number line is quietly built out of Fibonacci numbers, and this small game is just a way of making you count in them.