Combinatorial Game Theory
who wins, and by how much
Concept

Fibonacci — where it appears

The sequence in which each term is the sum of the two before it, and the losing heaps of the game named after it. It turns up here twice for unrelated reasons — a cap on the previous move, and a board with two heaps — which is what makes the coincidence worth a page.

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

Also named here as recurrence — the same set of essays touches all of them, so they are one junction rather than several.

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

Named alongside it

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

CounterexampleEnumerationFibonacci nimGolden ratioImpartialInvariantOutcome classPeriodicityRecurrenceStateZeckendorf representationSubtraction

All concepts