The heap is not the position

One heap of counters. The first player takes any positive number short of the whole heap. After that, a player may take at most twice what the opponent just took. Whoever takes the last counter wins.

That is Fibonacci Nim, and the clause in bold puts it outside everything else on this site.

A position here is not a heap. It is a heap and a cap, and the cap is a fact about the move that has just been made rather than about anything on the table. A heap of six reached by taking one counter and a heap of six reached by taking four are different games with different answers, and no arrangement of the counters distinguishes them.

Nothing to add #

The Sprague–Grundy theorem says every impartial game is a Nim heap, and it earns its keep by making sums computable: a position with several components is worth the nim-sum of their values, and a player wins by moving to zero.

Every word of that needs each component to answer for itself. A component’s Grundy value is a function of the component, and the theorem’s whole content is that the function exists.

Here it does not. A heap of six has no value, because “a heap of six” is not a position — and even if the pair $(6, \text{cap})$ is taken as the position, there is still nothing to add, because a sum of Fibonacci Nim heaps has no agreed rules. Does the cap apply to the whole board, or to the heap that was moved in? Both are defensible and they are different games, and neither has a component structure: the first because the cap is global, the second because it is a fact about which heap was touched.

So the game is not a component of anything, and it is not the sum of anything. It is a single object.

The nearest neighbour on this site is Top Entails, where a move compels the opponent to reply in the same heap, so a component’s legal moves depend on what has just happened elsewhere and the nim-sum misreads the sum for exactly that reason. Fibonacci Nim’s dependence is one step worse than that. Top Entails at least has components: the constraint says which heap the reply must be in, so a heap is still a thing with an identity in the position. Here the constraint is not about a component at all, it is about the previous move, and there is nothing on the table it could be a property of.

And it is completely solved #

None of which stops the game having an answer, and the answer is short.

The first player loses exactly when the heap is a Fibonacci number.

Over every heap from two to a hundred and twenty, the opener loses nine of them, and the nine are $2, 3, 5, 8, 13, 21, 34, 55$ and $89$ — every Fibonacci number in the range, and nothing else.

That is a strange rule to arrive at in a game with one heap, no board, no geometry and no continuous quantity anywhere in it. It is the same strangeness Wythoff’s game has, from a completely different direction, and the two are connected by more than a family resemblance.

The move the numeral names #

Every positive integer has exactly one representation as a sum of non-consecutive Fibonacci numbers. That is Zeckendorf’s theorem, and the representation is found greedily: take the largest Fibonacci number that fits, subtract, repeat.

$$50 = 34 + 13 + 3 \qquad 100 = 89 + 8 + 3$$

The winning move is: take the smallest term.

Over the 110 winnable heaps up to 120, the smallest Zeckendorf term is a winning move in all 110. It is not always the only one — 66 of the 110 have more than one winning opening, and the mean is 1.7 — but it is always available and it is always right.

The proof is two lines of Fibonacci arithmetic #

The strategy is an induction and the induction is entirely about the numerals.

Suppose the heap is $n$ with numeral $f_{i_1} > f_{i_2} > \dots > f_{i_k}$, and $k > 1$ so the heap is not itself a Fibonacci number. Take $f_{i_k}$.

The move is legal, because $f_{i_k} < n$ — there is at least one larger term above it.

The opponent cannot clear a term. Their cap is $2 f_{i_k}$, and the smallest term now facing them is $f_{i_{k-1}}$, which is at least $f_{i_k + 2}$ because the numeral has no consecutive terms. And

$$f_{i_k+2} = f_{i_k+1} + f_{i_k} > 2 f_{i_k}$$

since $f_{i_k+1} > f_{i_k}$. So the opponent must leave part of a term behind, and the position handed back is one with a numeral again.

A Fibonacci heap is lost, because its numeral is a single term, the opener cannot take it all, and whatever they do leaves a smaller numeral for which the same argument applies to the opponent.

The two computations agree: the census over 120 heaps confirms the outcome rule, and the numeral check over 2,000 heaps confirms that the move is legal and safe in all 1,984 cases where the numeral has more than one term.

How large the state space gets #

The figure at the head of this essay reports the cost of the extra coordinate, and the numbers are worth reading rather than glancing at.

A heap of twenty reaches 66 distinct positions, against Nim’s twenty. Eleven counters is the heap size reached with the most different caps — six of them — and six of the twenty heap sizes below it have two states with opposite answers.

That last column is the one that settles the matter. If every heap size had the same answer under every cap it might reach, the cap would be decoration and one could talk about “a heap of eleven” after all. Six of twenty do not, so the cap is load-bearing on nearly a third of the sizes and there is no way to speak about a heap without it.

The growth is quadratic and modest, so a computer solves the game to any heap size instantly. That is worth stating because the failure of the theory here has nothing to do with cost. The game is trivially tractable and structurally outside the theory, and those two things are independent.

The same numerals, two unrelated games #

The digits say which move wins is this site’s essay about Zeckendorf numerals in Wythoff’s game, where the cold positions are the pairs $(\lfloor n\varphi \rfloor, \lfloor n\varphi^2 \rfloor)$ and the winning move is read off a digit rule.

Wythoff’s game is two heaps on a quarter-infinite board with a diagonal move. Fibonacci Nim is one heap with a rule about the previous move. They share no mechanism, no board and no shape of position, and both are decided by the same numeral system.

The honest account of the coincidence is that it is not one. Both games are about the ratio between successive quantities: Wythoff’s diagonal move makes the golden ratio the fixed point of the position sequence, and Fibonacci Nim’s factor of two makes it the fixed point of the numeral’s growth. The golden ratio is the number for which “the next one is more than twice this one” is exactly on the boundary, and both games are built around that boundary from different sides.

That is a connection rather than a derivation, and stating it as more would be overselling it. What the two games share is a constant; the reasons they share it are related and not the same.

Change the two and the numerals change with it #

The section above says the golden ratio appears because “the next one is more than twice this one” is exactly on the boundary at a factor of two, and calls it a connection rather than a derivation. It can be tested, by varying the only number in the rule.

Replace twice what the opponent took with at most $k$ times, solve the game again, and list the heaps the opener loses.

$$k = 1: \quad 2,\; 4,\; 8,\; 16,\; 32,\; 64,\; 128$$

$$k = 2: \quad 2,\; 3,\; 5,\; 8,\; 13,\; 21,\; 34,\; 55,\; 89,\; 144$$

$$k = 3: \quad 2,\; 3,\; 4,\; 6,\; 8,\; 11,\; 15,\; 21,\; 29,\; 40$$

At $k = 1$ the losing heaps are the powers of two. Not a sequence resembling them — exactly them, up to a hundred and fifty. And the winning move is what the parallel demands: take the lowest set bit of the binary numeral, which is the smallest term of the representation of $n$ as a sum of powers of two. Checked on every winnable heap in range, it wins all 142 of them.

So the shape of the whole analysis is preserved and only the numeral system moves. A factor picks a growth rate; the losing heaps are the terms of the sequence with that rate; every integer has a representation as a sum of non-adjacent terms of it; and the winning move is the smallest term of that representation.

Which makes the coincidence a derivation after all #

That is a stronger statement than the essay was in a position to make, and it changes the account of the Wythoff resemblance.

Zeckendorf numerals are not attached to Fibonacci Nim. They are what the base-two argument becomes when the factor is two, and the factor is the only free parameter the game has. Binary is the $k = 1$ answer and Zeckendorf is the $k = 2$ answer, produced by the same mechanism, and neither is a coincidence of anything.

The mechanism, stated once for both: the winning move takes the smallest term, which caps the opponent at $k$ times it, and the next term up is more than $k$ times the smallest — because consecutive terms are excluded from the representation and the sequence grows by at least that rate. At $k = 1$ that is the statement that the next power of two is more than one times this one; at $k = 2$ it is $f_{i+2} > 2 f_i$, which is the essay’s induction. One inequality, two instances.

And it says which fact about the golden ratio is doing the work. Not that $\varphi$ is beautiful or that Fibonacci numbers turn up everywhere — that the sequence with ratio $\varphi$ is the slowest-growing one for which the next term still outruns twice the last. Change the two and a different sequence is the slowest one that clears the bar, and the game finds it.

Larger factors give sequences with slower growth again and no name this site will claim: at $k = 3$ the losing heaps are $2, 3, 4, 6, 8, 11, 15, 21$, and whether they satisfy a clean recurrence is not something four terms of agreement should be asked to settle.

What the model cannot reach #

There is no value. Everything above is an outcome — who wins — and nothing here is a Grundy value, because the game has none. A reader used to this site’s habit of computing a value for every position should notice its absence: the position index records this game’s positions with an outcome and no value at all, which is the honest entry.

There is no sum. The whole apparatus this site is built on is inapplicable, not because it is hard but because the hypothesis fails. That is a different kind of limit from an intractable game and a more absolute one.

The convention is normal play and it is doing more work than usual, because “whoever takes the last counter wins” is the rule that makes the induction terminate. Under misère play the base case flips and the whole numeral argument has to be redone; nothing here says what happens, and there is no reason to expect the Fibonacci numbers to survive.

The search is bounded at a heap of 120 for the outcome census, 2,000 for the numeral check and 20 for the state-space count. The proof sketch above is what makes those windows evidence rather than the whole claim.

Playing it, and losing on purpose #

The game is worth playing once, because the losing positions feel wrong.

A heap of eighty-nine is a large pile and the player who moves first cannot win it. A heap of ninety is one counter larger and the first player wins by taking exactly one — because $90 = 89 + 1$ and the smallest term is $1$, so the opening move is to take a single counter from a heap of ninety and hand back eighty-nine.

And it is the only winning move from ninety: the search finds one opening and no other, so a player who takes anything else has lost a pile of ninety counters immediately and irrevocably.

That is the move a beginner will never find. Taking one counter from a pile of ninety looks like doing nothing; what it does is leave a Fibonacci number and a cap of two, and the cap of two is what makes the eighty-nine safe. The opponent cannot take more than two, so they cannot begin to break into the numeral, and every reply leaves a numeral again.

The generalisation is the whole feel of the game: the winning move is nearly always the smallest one available, and the losing move is nearly always the greedy one. Taking a lot leaves the opponent a large cap, and a large cap is exactly what lets them take a whole term.

That inverts the instinct every other game here trains. In Nim the winning move is whatever restores a nim-sum of zero and its size is incidental; in a scoring game the winning move is usually the large one. Here size is the whole of it, in the wrong direction.

Who found it, and when #

The game is folklore with a definite proof attached. It appears in the recreational literature from the mid-twentieth century — Whinihan published the Fibonacci analysis in the Fibonacci Quarterly in 1963 — and the connection to Zeckendorf’s 1972 paper on the representation, though the representation itself is much older and was known to Lekkerkerker in 1952.

The order there is worth noticing. The game’s answer was found before the numeral system it is usually stated in was published under the name it now carries. What Whinihan had was the Fibonacci numbers and an induction; the numeral is a repackaging that makes the winning move visible, and it arrived afterwards.

That is the usual direction in this subject. The notation was the argument is the essay about the opposite case, where a way of writing positions down did the work of a theorem. Here the theorem came first and the notation came later, and what the notation bought was not the answer but the ability to say the answer in four words.

The clause, weighed exactly #

It is worth asking how little of the rule is doing the damage, because the answer is: all of it, and the smallest possible amount.

Remove the cap entirely and the game is Nim with one heap, worth $\ast n$, and the opener wins unless the heap is empty. Fix the cap at a constant $c$ regardless of the previous move and the game is a subtraction game — take between $1$ and $c$ — with Grundy value $n \bmod (c+1)$, a component like any other, addable and analysable.

So a cap is harmless. What is not harmless is a cap that depends on the previous move, and that dependence is one multiplication.

That is the general lesson and it is worth carrying. A component may have any rules whatever about its own contents; what it may not do is consult anything outside itself. The pass that may not be the move that ends the game fails the same test for the same reason, and its failure is also one clause long.

Where the ladder goes next #

The first rung out is the factor. Two is arbitrary: a rule allowing at most $c$ times the previous move gives a different game for each $c$, and the losing positions for $c = 1$ and $c = 3$ are two different integer sequences. The Fibonacci numbers are the $c = 2$ case of a family, and the family’s other members are governed by other linear recurrences.

The second is the sum, taken seriously. Two Fibonacci Nim heaps with a shared cap is a well-defined game and its analysis is not in the literature as far as this site can tell; two heaps with per-heap caps is a different well-defined game. Both are worth solving small and neither has a component structure to lean on.

And the third is the general shape: games whose state includes the last move. Fibonacci Nim is the smallest interesting one, Top Entails is another, and a pass that may not end the game is a third. All three break the sum for the same reason — a component that cannot say what its own legal moves are — and what they have in common is a question nobody here has asked.