Combinatorial Game Theory
who wins, and by how much
Series

Fibonacci nim — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 1 · impartial
  2. 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.

    part 2 · impartial
  3. 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.

    part 3 · impartial
  4. 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.

    part 4 · impartial

All series