What restores the theorem

What a component has to carry pointed one instrument at three games that break the disjunctive sum and found a quarter, a quarter and nearly a half of their sums mispredicted. It closed by naming the repair for the first of them:

For Fibonacci Nim there is an answer — the pair of heap size and cap — and running the census over those pairs rather than over heap sizes should restore the theorem exactly. Whether it does is a computation this machinery could make and has not.

It does, on every pair and every triple, and the number that comes out is not the number the game is famous for.

The heap was never the position #

Fibonacci Nim is one heap and one clause: a player may take any number of counters up to twice what the previous player took, and the opener may not take the whole heap. The losing heap sizes are the Fibonacci numbers, which is the fact the game is known for.

The heap is not the position established what that clause costs. A heap of nine with a cap of two and a heap of nine with a cap of eight are different positions wearing the same number, and the game’s state is the pair — how many counters are left and how many may be taken.

Sprague–Grundy is a theorem about disjunctive sums of impartial games, and it says a position is worth a single number and sums are exclusive-ored. It is not false here. What is false is the identification of the position with the heap, and a recipe fed the wrong object gives the wrong answer.

What the wrong number costs #

Give each heap the number its size suggests — nought if the size is a Fibonacci number and one otherwise, which is the outcome rule of the one-heap game — and exclusive-or.

That is right on 68 of the 91 pairs of heaps from two to fourteen, and on 133 of the 165 triples from two to ten. A quarter wrong in each case.

The failures are not near misses; an outcome rule has two answers and being wrong means naming the wrong winner. And they are not confined to any recognisable family: heaps of four and six, of five and nine, of seven and eleven.

The number a heap actually carries #

Index the recursion on the pair instead. The Grundy value of a state (n, cap) is the smallest non-negative integer not among the values of the states it can move to, and the states it can move to are (n − t, 2t) for each legal t.

Give each component the Grundy value of its opening state — a heap of n with a cap of n − 1, which is the “not the whole heap” clause — and exclusive-or those.

That is right on all 91 pairs and all 165 triples. The census asserts it, so a single miss would stop the build, because the whole page is that the theorem is a theorem again once the state is the state.

The sequence is worth reading rather than summarising. Heaps two, three, five, eight, thirteen and twenty-one carry nought — the Fibonacci numbers, which the census also asserts, since a nought anywhere else would mean the state recursion and the outcome rule had parted company. Between them the values climb: 3 at four; 4 at six and seven; 5 at nine, ten and eleven; 6 at twelve, fourteen and fifteen; 7 at sixteen through twenty; 8 at twenty-two through twenty-four.

So a heap of nine is worth ∗5, not ∗1. The outcome rule was reporting whether the number was nought, and the number is much larger than a bit.

Where the extra information is #

It is worth being precise about what the state number knows that the size number does not, because “more information” is not an explanation.

The outcome rule answers one question about a component: does the player to move in it, alone, win? That is one bit, and one bit is exactly what a two-outcome classification carries.

A Grundy value answers a different question: which Nim heap does this component behave like, in any sum? That is what makes exclusive-or legal, and it needs the whole equivalence class rather than the outcome. Two components that are both first-player wins are both non-zero and they need not be equally non-zero — a heap of nine at ∗5 and a heap of four at ∗3 are both wins alone, and together they are 5 ⊕ 3 = 6, which is a win, where the bit reading gives 1 ⊕ 1 = 0 and calls it a loss.

That single pair is the whole failure mechanism, and it accounts for the shape of the twenty-three misses: they are the pairs where two non-zero values happen to be equal under the bit reading and unequal under the real one, or the reverse.

What restoring it costs #

A theorem restored at a price is worth pricing, and the price is a table where there was a list.

A heap of twenty reaches sixty-six distinct states. A table indexed on heap size alone has twenty entries below it. So the object a solver has to hold is three times larger at this size, and the ratio grows: the states of a heap are pairs, and the number of caps a given remaining count can be reached with grows with the heap.

Sixty-six against twenty is the figure at a heap of twenty, and the ratio at smaller heaps is smaller — a heap of five reaches six states against five sizes, a heap of ten reaches nineteen against ten. Three times is a small price and it is the right order of magnitude to expect. The cap is bounded by twice the last take and the last take is bounded by the heap, so a remaining count of m can carry only so many caps; the state space is quadratic in the heap where the heap space is linear, and quadratic in a small number is a small number.

The comparison worth making is with the alternative, which is having no theorem at all. Without the state, a sum of Fibonacci Nim heaps has to be searched as a whole — a product of the components’ state spaces — and with it each component is evaluated once and the results are exclusive-ored. The saving is the difference between a product and a sum, and it is a number rather than a figure of speech.

So the two factors move in opposite directions and only one of them moves with the board. Re-indexing costs a component about three times its states, and that ratio is a property of one heap: it is three whether the board has two components or six. The cost of giving up decomposition is a product, so it is 6.3 at two components and 16.9 at three on these pools, and it keeps going. Paying a fixed three to avoid a factor that grows is not a trade anybody would refuse.

One pair is enough to see the whole of it, and the smallest failure is heaps of four and six.

A heap of four is a first-player win: the opener takes one, leaving three with a cap of two, and three with a cap of two is a loss because the taker of one leaves two with a cap of two and the taker of two leaves one. A heap of six is a first-player win by the same kind of argument. Two first-player wins, exclusive-ored under the bit reading, give nought — a second-player win.

Solved directly, the sum is a first-player win.

The state numbers say why. The opening state of four carries 3 and the opening state of six carries 4, and 3 ⊕ 4 = 7, which is not nought. So the first player has a move to a position of value nought and the bit reading missed it because both components were merely non-zero and it had no way to tell 3 from 4.

The move itself is what the Grundy value produces and the bit reading cannot. Finding it means finding a component and a take that changes that component’s value to the exclusive-or of the others, which is the ordinary Nim recipe applied to states rather than to heaps. That it is available is not a separate fact: it is what Sprague–Grundy says, and the reason the recipe was unavailable before is that it was being applied to the wrong objects.

Four and six is the smallest failure of the bit reading in the sweep, and every other failure has the same shape — two components whose sizes agree on being non-Fibonacci and whose values do not agree on anything.

What this does and does not generalise to #

The repair works here and the reason it works is narrow, so it is worth saying exactly what the narrowness is.

Fibonacci Nim’s clause looks across time and not across the board. The cap depends on what the previous player did in this component, and a component can therefore be given a state that records it. Nothing about the rest of the board enters.

The other two games the rung below measured are not like that. A move that must be answered has a clause that compels a reply anywhere, so the compulsion is a fact about the sum rather than about a part, and no per-component state can hold it. A held pass is the same: whether a pass is legal is a question about the whole position.

So the class the repair belongs to is the games whose extra rule is local, and stating that class properly is a question about rule tables rather than about positions. Fibonacci Nim is the smallest interesting member of it and this page is the demonstration that membership is worth something.

What the repair says about the famous rule #

There is a reading of all this that makes the well-known result look smaller than it is, and it is worth resisting.

The losing heaps are the Fibonacci numbers is a statement about one heap played alone, and it is exactly right. What this page shows is that it is the bottom row of the analysis rather than the whole of it: the Grundy value is nought precisely on those heaps, so the famous rule falls out as the special case of asking whether the number is nought.

That is the normal relationship between an outcome rule and a value theory and it is worth noticing here because Fibonacci Nim is usually presented as a solved game. It is solved in the sense that a single heap has a rule and a winning move — the smallest Zeckendorf term — and it was not solved in the sense that two heaps side by side had no rule at all until the state was the state.

The gap between those two senses of “solved” is what this page closes, and it is the gap the whole complexity ladder is about: a game with a rule for one component and no arithmetic for sums is a game with an answer to a smaller question than the one anybody asks.

What the right component was all along #

The result reads as a repair and it is worth putting the other way round, because the other way round is what it actually says about the rung below.

The theorem was never in trouble. Sprague–Grundy applies to any impartial game whose positions decompose into independent components, and Fibonacci Nim is such a game — its components are heap-and-cap pairs. What failed was not the theorem but an identification: somebody decided that a component of Fibonacci Nim is a heap, and a heap is not one.

That is a modelling error rather than a mathematical one, and it is the easiest kind to make invisibly, because a heap looks like a component. It has a size, it can be drawn, it is what a player points at. The cap is not drawn anywhere and is not part of the picture, so a description of the position that a reader would call complete leaves it out.

The measure of how much was thrown away is the number a heap carries. Under the heap-only reading a heap of nine is worth one; under the correct one it is worth five. That is not a small correction to a nearly-right value — the two readings do not even agree about the size of the answer set, since the honest per-heap reading has only two values in it and the correct one has as many as the caps allow.

So the lesson to carry into a new game is a question rather than a check. Before applying the theorem, ask what a component has to know in order to list its own moves — and if the answer includes anything not visible in the drawing, the drawing is not the position.

What the census does not say #

Three limits.

The sum is the local-cap sum. Two Fibonacci Nim heaps side by side is a well-defined game only once it is said whether the cap is per-heap or shared, and everything here is per-heap: a player moving in one component is capped by what was last taken in that component. The shared-cap version is a different game, it is the one a naive reading of the rules gives, and no per-component state repairs it — because a shared cap is a fact about the board.

Fourteen and ten. The pairs run to heaps of fourteen and the triples to ten, which is 91 and 165 positions. Both are exact and neither is large, and the reason is the cost of solving the sums directly rather than of computing the states.

Nothing here says the values are small. The largest opening value up to a heap of twenty-four is eight, which is comfortable, and there is no argument on this page that it stays comfortable. A Grundy value is bounded by the number of options and the number of options grows with the heap, so the values may well grow without limit — slowly, on the evidence, and that is evidence rather than a bound.

And the Grundy sequence is reported, not explained. Nought at the Fibonacci numbers, then a staircase — 3, 4, 4, 5, 5, 5, 6 — which looks as though it should have a description in terms of the Zeckendorf representation and this page does not have one. The obvious guesses do not survive twelve, where the value is 6 and the neighbours are 5.

The convention, named #

Normal play. A move takes between one counter and twice the previous take in the same component; the opener in a component may not take the whole of it, which is the “cap of n − 1” the opening states carry. A cap larger than the heap and a cap equal to it permit the same moves, so the cap is clamped to the heap and the two are one state.

Every sum is solved by direct search over tuples of states, and the two rules are asked to predict the result rather than being used to produce it. The Grundy value of a state is computed by the mex recursion over that state’s own options and depends on nothing else.

Where the ladder goes next #

memory has two rungs to here: three games that break the sum because a component cannot say what its own moves are, and now the one of the three where enlarging the component repairs it completely.

There is no rung above this yet, and the reason is worth stating rather than leaving as an absence. The repair here is not a method; it is a fact about Fibonacci Nim. The cap belongs to the heap, so a heap-and-cap pair is a component, and the game over those pairs is a genuine disjunctive sum with the theorem intact. Nothing about that generalises: Top Entails’ obligation names another component and a held pass’s legality is a predicate over the whole board, so neither has a local state to enlarge.

That splits the anchor’s three games into two kinds with a sharp boundary. Carrying history is repairable and carrying a fact about the rest of the board is not, and the first kind costs a bigger table while the second costs the theorem. The rung this anchor still wants is the general condition — which rules let a component state its own legal moves? — which is a question about rule tables rather than about positions, and which would let a reader classify a new game by reading its rules rather than by sweeping its sums.

The other direction is quantitative and this page has taken one step along it. Re-indexing multiplies the table by the number of caps a heap can have, which is bounded by the heap size, so the repair costs a polynomial factor — measured here at about three. Against it, giving up decomposition costs a factor of 6.3 over pairs and 16.9 over triples, which is the shape of a product rather than of a constant.

What that step does not settle is where the second factor goes. Two arities are two points, and two points name no growth rate: the honest reading is that the cost of searching whole grows with the number of components on the evidence available and that nothing here bounds it. A solver author choosing between a bigger table and a bigger search wants the curve rather than two of its values, and getting it means pushing the direct search past three components, which is the computation this pool was chosen to avoid.