Combinatorial Game Theory
who wins, and by how much
Concept

Zeckendorf representation — where it appears

The unique way of writing an integer as a sum of Fibonacci numbers no two of which are neighbours. Its smallest term names a winning move in Fibonacci Nim, so a numeral system turns into a strategy.

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

The cold positions, written in Fibonacci base. The first several cold pairs of Wythoff's game with both heap sizes written in Fibonacci base — as sums of non-consecutive Fibonacci numbers, which every integer has exactly one of. Blue is the smaller heap and red the larger. Read as digits, the pair is a shift: the larger numeral is the smaller one with a zero appended, and the smaller one always ends in an even number of zeros.

The digits say which move wins

Wythoff's cold positions are usually given as a pair of golden-ratio formulas. Written in Fibonacci base they are a statement about digits instead — the smaller heap ends in an even number of zeros and the larger is the same numeral shifted up a place — and a rule about digits answers a question about a heap of a trillion.

applied · Wythoff's game Every heap up to 40, won or lost. Heap sizes with the outcome for the player who moves first. The lost ones are shaded; they are exactly the Fibonacci numbers, which is a fact about a game with one heap, no board and no geometry in it anywhere.

The heap is not the position

Fibonacci Nim bounds a move by twice the previous move, which puts the state outside the board: a heap of six with a cap of two and a heap of six with a cap of five are different games. So there is nothing to add and no Grundy value to compute — and the game is completely solved anyway. The opener loses on exactly the nine Fibonacci numbers up to 120, and the smallest term of the Zeckendorf numeral is a winning move in all 110 winnable heaps.

impartial · Fibonacci nim One number per heap, and one number per state. Sums of Fibonacci Nim components solved in full, against two predictions. Giving each component the number its heap size suggests gets a quarter of the pairs wrong; giving it the Grundy value of its state — the pair of heap size and cap — gets every pair and every triple right.

What restores the theorem

Fibonacci Nim breaks the recipe every impartial game is supposed to obey: one number per heap, exclusive-ored, gets a quarter of two-heap sums wrong. Index the recursion on the pair of heap size and cap instead and the recipe is exact on every pair and every triple — and the number a heap of nine carries turns out to be five rather than one.

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 One set, described three ways that share no arithmetic. Wythoff's cold positions can be stated as the Beatty pairs of the golden ratio, as a greedy construction over the integers that mentions no constant, and as a condition on Fibonacci numerals. None of the three consults the game. The fourth column is the game — a mex table over the moves — and all four name the same set of cold pairs over the whole square, which is what the figure counts.

A set with three descriptions, and a function with none

Wythoff's cold positions can be written three ways that share no arithmetic — an irrational constant, a greedy rule, a condition on Fibonacci digits — and all three are exact. The same game's Grundy values have no closed form at all. Both facts are about one table, and the gap between them is the subject.

applied · Wythoff's game

Named alongside it

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

Golden ratioGrundy valueImpartialEnumerationExhaustive searchPeriodicityBeatty sequenceClosed formFibonacci nimInvariantStateCold position

All concepts