Combinatorial Game Theory
who wins, and by how much
Concept

Fibonacci nim — where it appears

One heap, where a move may take at most twice what the previous player took. The heaps the opener loses are exactly the Fibonacci numbers, and the factor of two is one member of a family whose other members give other integer sequences.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

What a component has to carry. Four impartial games, one of which is Nim. In the other three a component cannot say what its own legal moves are without knowing something about the past or about the rest of the board, so the Sprague–Grundy recipe does not apply — and the table says by how much. Every outcome was obtained by solving the sum outright rather than by any formula.

What a component has to carry

Three impartial games on this site break the sum, and they break it for the same reason: a component cannot say what its own legal moves are. Measured with one instrument — one number per part, exclusive-ored — the failure rate runs from a quarter to nearly half, against a control where the same recipe is a theorem and is never wrong.

limits · Memory The Fibonacci numbers are one row of a table. The losing heaps of Fibonacci Nim with the factor two replaced by one, three, four and up to eight. Each factor gives a different integer sequence: the powers of two, the Fibonacci numbers, and four more with no common name.

The family the Fibonacci numbers belong to

Fibonacci Nim lets a player take at most twice what the last one took, and the heaps the opener loses are the Fibonacci numbers. Two is an arbitrary number. At one the losing heaps are the powers of two, at three and four and five they are four more sequences, each with a linear recurrence whose lag is twice one less than the factor — until the factor is six, where the pattern stops.

impartial · Fibonacci nim The gap is the factor. The separation condition of each factor's greedy numeral system: the smallest gap between the indices of two terms. It is one at factor one, two at factor two — Zeckendorf's non-adjacency — and the factor itself at every factor swept.

What the numerals knew

Every factor in the Fibonacci Nim family gives a numeral system, and the rung below predicted its separation condition would be the lag of the recurrence the losing heaps satisfy. It is not. The gap is the factor — one at c = 1, Zeckendorf's two at c = 2, and c at every factor to eight — while the lag goes 1, 2, 4, 6, 8, 11, 14, 17 and leaves its own pattern at six. The numerals then solve every one of 194,480 states, cap and all.

impartial · Fibonacci nim Two statements, two routes. The two measured identities the rung below left unproved, with the argument each was expected to need.

One proof, and one wrong lemma

Two measured identities were left for a proof: the move rule by induction, the gap condition from the reply bound. The induction is exact on 31,731 heaps at eight factors. The reply bound holds at c = 2 and on one index pair in twenty-seven at c = 3 — and the inequality that does the work is a third one nobody proposed.

impartial · Fibonacci nim

Named alongside it

The objects these essays reach for when they reach for this one.

ImpartialCounterexampleEnumerationPeriodicityStateZeckendorf representationFibonacciGolden ratioGrundy valueInvariantOutcome classRecurrence

All concepts