Combinatorial Game Theory
who wins, and by how much
Concept

Golden ratio — where it appears

The number satisfying φ² = φ + 1, which turns up here as the slope of a game's losing positions rather than as geometry. It appears here thirty years before Beatty sequences were studied, in a paper about a game rather than about numbers.

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

A golden ratio in a table that never mentions it. Grundy values for Wythoff's game, computed by the mex rule alone — a queen moving left, down or diagonally toward the corner, and whoever cannot move loses. The circles are Wythoff's 1907 description of the losing positions, which came thirty years before any of this machinery: the pairs formed from the golden ratio. They land on the zeros exactly. Nothing in the computation knows about φ and nothing in Wythoff's argument knows about Grundy values.

A golden ratio thirty years early

Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.

history · Wythoff's game Wythoff's game, and the line the losing squares lie on. A queen moves left, down, or diagonally down-left any distance, and whoever cannot move loses. Every square carries the Grundy value the mex rule gives it. The squares worth nothing — the ones a player wants to hand over — lie along two lines whose slopes are the golden ratio and its reciprocal, in a game with no geometry and no continuous quantity in its rules.

Wythoff's game, and the ratio nobody put there

Two heaps, three kinds of move, and losing positions that lie along a line of irrational slope. Nothing in the rules mentions a ratio, a length or a continuous quantity — and the golden ratio comes out anyway.

impartial · Wythoff's game 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 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 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.

Beatty sequenceZeckendorf representationClosed formExhaustive searchGrundy valueImpartialMexPeriodicityWythoff's gameCold positionCounterexampleEncoding

All concepts