Take one, three or four

One heap of counters, and a list of numbers. A move removes a number of counters from the list. The player who cannot move loses.

That is the entire rule, and with the list $\{1, 3, 4\}$ it produces a sequence of values that repeats every seven heaps for ever.

The smallest game worth having #

A subtraction game has one heap, no board, no players with different moves and no structure to speak of. It is about as small as a game can be while still being one, which makes it the right place to watch the general machinery work.

Everything the impartial theory has applies to it. Each heap size is a position; each position gets a Grundy value by the mex rule — the least non-negative integer that is not the value of any option — and a sum of heaps is settled by the nim-sum of their values. Nothing is special-cased, and the answers come out in the same currency as everything else. Every number in this essay is that one operation applied to values already computed, working upward from the empty heap, and every strip below is what comes out of running it.

The smallest list worth drawing is $\{1, 2\}$, and it is the case where the machinery has nothing to do. A heap of $n$ reaches $n-1$ and $n-2$, so the mex never has more than two numbers to avoid and the values cycle immediately.

What makes the family worth its own rung is that its regularity can be proved rather than observed — which is unusual, and which fails one step up the ladder.

The easiest case, and why it is easy #

Take the list $\{1, 2, 3\}$: a move removes one, two or three counters.

The values run 0, 1, 2, 3, 0, 1, 2, 3, … and the rule is $g(n) = n \bmod 4$. The reason is worth seeing directly: from a heap that is a multiple of four, every move lands on a heap that is not — and from any other heap, exactly one move lands on a multiple of four.

That is the whole game of Nim with a cap, and it generalises immediately: with the list $\{1, 2, \ldots, k\}$ the value is $n \bmod (k+1)$ and the losing positions are the multiples of $k+1$. A player who knows this cannot be beaten from a winning position, and a player who does not will lose to anybody who does.

The interesting sets are the ones with a gap in them.

A gap changes everything #

Remove the 2 from the list and the tidy pattern is gone. With $\{1, 3, 4\}$ the values run

$$0,\; 1,\; 0,\; 1,\; 2,\; 3,\; 2,\; 0,\; 1,\; 0,\; 1,\; 2,\; 3,\; 2, \ldots$$

Period 7, and no formula anybody would guess from the rule. There are two losing heaps in each period rather than one — heaps 0 and 2 modulo 7 — so a player must know the sequence rather than an arithmetic rule.

Other gapped sets behave differently again, and the differences are not variations on one theme. The mildest change available is to drop the 1 instead of the 2, which leaves a player with no way to shorten a heap by a single counter.

Push the largest move up instead, keeping the number of takes at three, and the period grows by one while the values stay inside the same small range they already occupied.

A set whose largest move is barely larger again produces a period with no rising run anywhere in it, and one whose length has nothing to do with anything visible in the list.

There is no pattern connecting the set to the period. Removing one element can double the period or leave it unchanged, and neighbouring sets give unrelated sequences — which is a fact worth registering early, because it recurs in every impartial family and gets no better further up.

The guarantee #

Here is what makes this family different from everything above it: the values of a finite subtraction game are always eventually periodic, and the proof needs no cleverness.

Let $m$ be the largest number in the list. The value of a heap depends only on the values of the $m$ heaps below it — nothing further back can be reached in one move. So the state of the computation, as it proceeds upward, is the last $m$ values.

Those values are bounded, and the bound is worth getting tight because it is the whole size of the search. A heap has at most one option per element of the list, so the mex is at most $k$, where $k$ is how many numbers the list contains. Each of the $m$ remembered values is therefore one of $k+1$ possibilities, and there are at most $(k+1)^m$ possible states.

Note which letter is which. $m$ is the largest move and sets how far back the window reaches; $k$ is the size of the list and sets how tall the values can get. For $\{2,5,6\}$ that is $m = 6$ and $k = 3$, giving $4^6 = 4{,}096$ states — where reading the bound as $(m+1)^m$ would have said $117{,}649$, twenty-eight times looser for no reason.

A deterministic process with finitely many states must eventually revisit one, and from that moment everything repeats. So there is a period, and there is a bound on how long the computation can go before it starts.

That bound is still astronomically loose — four thousand states against an observed period of eleven — and the observed periods are single digits. What matters is not the number but the guarantee: a search for a period here is a search for something known to be there, which is a different activity from a search that might come back empty.

Working the values out by hand #

The sequence for $\{1, 3, 4\}$ is short enough to derive completely, and doing it once makes every other sequence in the subject legible.

Heap 0 has no moves, so its value is the mex of nothing, which is 0. Heap 1 can only take 1, reaching heap 0 with value 0 — the mex of $\{0\}$ is 1. Heap 2 can only take 1, reaching heap 1 with value 1, and the mex of $\{1\}$ is 0.

Heap 3 can take 1 or 3, reaching heaps 2 and 0, values 0 and 0; the mex of $\{0\}$ is 1. Heap 4 can take 1, 3 or 4, reaching heaps 3, 1 and 0 with values 1, 1 and 0; the mex of $\{0, 1\}$ is 2. Heap 5 reaches heaps 4, 2 and 1 with values 2, 0 and 1, and the mex of $\{0, 1, 2\}$ is 3. Heap 6 reaches heaps 5, 3 and 2 with values 3, 1 and 0, and the mex of $\{0, 1, 3\}$ is 2.

So the first seven are 0, 1, 0, 1, 2, 3, 2 — and heap 7 reaches heaps 6, 4 and 3 with values 2, 2 and 1, giving mex 0, which is where the repeat begins.

Two things are worth taking from the exercise. The losing heaps are those valued 0 — heaps 0, 2, 7, 9 — so a player wants to hand over a heap of two, and the arithmetic rule that worked for $\{1,2,3\}$ has no analogue here. And the value 3 appears exactly once per period, at heap 5, which is the largest value the game ever produces: the mex cannot exceed the number of options, and there are only three.

Two numbers, two jobs #

The distinction between the largest move and the length of the list is worth keeping in view past the bound, because the two control different features of the sequence and it is easy to attribute one to the other.

The largest move sets the window. A value depends on the previous $m$ values and no further back, so $m$ is the width of the state — the amount of history the recursion carries. A set with a large maximum has a long memory whatever else is true of it.

The length of the list sets the ceiling. A mex over $k$ options cannot exceed $k$, so no subtraction game with three moves ever produces a value above 3, however large its numbers are. Takes of two, five or six run to a period of eleven and its values never leave $\{0,1,2,3\}$.

Both are readable off the list before anything is computed, and together they bound the whole search. What neither predicts is the period, which is the point the essay makes about neighbouring sets giving unrelated answers: the same $m$ and the same $k$ are compatible with periods of four, seven, eight and eleven, and nothing shorter than running the recursion distinguishes them.

Which is why the guarantee is worth more than the bound #

That gap — bounds that are cheap and a period that is not — is the shape of the whole result, and it is worth being explicit about which half is being relied on.

The counting argument gives a guarantee and a ceiling. The guarantee is the valuable half: a period exists, so a search for one is a search for something known to be there, and a search that comes back empty means the window was too short rather than that there is nothing to find. The ceiling is nearly useless — four thousand states against a period of eleven.

And the two halves fail differently one step up the ladder. Allow a move to split a heap into two and the value stops depending on a bounded window of the sequence: it depends on nim-sums of pairs drawn from anywhere below, so there is no state of fixed width to pigeonhole. The ceiling goes too — an octal game’s values run into the hundreds, because a nim-sum of two large values is a large value and the mex has more than $k$ options to avoid.

So the guarantee here is not a mild convenience that a slightly harder argument would recover for the octal games. It rests on both of the numbers above being finite, and splitting a heap destroys both at once — which is why this family is the only one in the subject where periodicity is a theorem rather than a hope.

What the period is worth #

The practical payoff is a change in cost from linear to constant.

Without the period, the value of a heap of a billion needs every value below it: a billion applications of the mex rule. With it, reduce the index modulo 7, look up one of seven numbers, done — which matters because a heap size written in binary is a short input and a computation linear in the heap is exponential in the digits.

And the certificate is small: $m$ values, checked against their repeats one period later, and the induction covers the rest. So the closed form is not merely found, it is proved, by a check a reader can do by hand in a minute.

Sums, and why the value is the point #

A single heap is a game a person solves once and finds dull. Several heaps at once is where the value earns its keep.

Three heaps under the rule $\{1, 3, 4\}$, of sizes 10, 11 and 13. Reduce each index modulo seven and read the period off: their values are $\ast$, $\ast 2$ and $\ast 2$. Adding those without carrying — which is what the nim-sum does, and it does exactly what it does for Nim — leaves $\ast$, which is not zero, so the player to move wins.

That is the general machinery working at full strength on the smallest possible example: an expensive-looking question about three heaps under an awkward rule, answered by three table lookups and two exclusive-ors. Nothing in the answer mentions taking one, three or four counters, and nothing needs to.

The move, once the value is known #

Values decide who wins; a player still has to move. The rule for finding the move in a sum is the same one Nim uses, and it is worth spelling out in this setting because the heaps are not Nim heaps.

The total is $\ast$, so the player to move wants to reach a total of 0. Take each heap in turn, ask what value it would have to become for the rest to cancel, and check whether a legal take achieves it. The heap of ten is worth $\ast$ and the other two cancel each other, so it has to become 0 — and taking one counter leaves a heap of nine, which the period says is worth 0 exactly. That is a winning move, and the figure above draws the same arithmetic for the heap of ten on its own.

The heap of thirteen supplies a second: the other two total $\ast 3$, and taking one counter leaves twelve, which is worth $\ast 3$. The heap of eleven supplies none. It would have to become $\ast 3$, and its three options are heaps of ten, eight and seven, worth $\ast$, $\ast$ and 0 — so the value the position needs is not among them.

Two features of that procedure are general. It is one pass per heap, so the work is linear in the number of components and needs no search at all. And, as the heap of eleven has just shown, it may find no move in one component and two in the others, which is why the pass runs over all of them: choosing which part to move in is exactly the calculation being done, and the answer is dictated rather than judged.

What it never requires is looking at the game again. Once the values are in a table, the subtraction rule has done its work and everything afterwards is arithmetic on nimbers — which is the sense in which this family, like every impartial one, collapses to Nim entirely.

One step up, and the guarantee is gone #

The natural generalisation is to let a move split the heap in two as well as shorten it, which is what an octal game does. The values of the parts are then nim-summed, and the family becomes enormously richer.

It also loses the theorem. The state of the computation is no longer the last $m$ values — a splitting move can reach any pair of parts — so the counting argument has nothing to count, and no bound replaces it.

Periodicity is still checkable when it occurs, by the Guy–Smith window. What has vanished is the guarantee that there is anything to find. Some octal games settle after a few terms, some after hundreds of thousands, and for some nobody has found a period after computing an extraordinary number of values.

So this rung is the last place in the subject where regularity is free. One rule change away, the same question becomes an open problem that has stood since 1956.

What the sequences leave unsaid #

Three limits, and the first is the one this site’s own figures are careful about.

Nothing here says a period exists for an infinite subtraction set. Take a square number of counters, or a Fibonacci number, and the counting argument collapses along with the bound on $m$. Those games have been studied and are not simply periodic; they are a different subject.

A period is about one game, not a neighbourhood. The sequences for $\{1, 3, 4\}$ and $\{1, 3, 5\}$ have nothing to do with each other, and knowing one gives no purchase on the other.

A value is not an outcome on its own. A heap worth $\ast 3$ is a win for the mover as a game by itself, and inside a sum it is only one term — outcomes do not add, and the total is what decides. That is the whole reason values exist rather than a table of winners.

A value is not a move. Knowing that a heap of ten is worth $\ast 3$ says the position is a win for the mover in a sum where the rest totals something other than $\ast 3$; it does not name the take. Finding the move is one more pass, cheap here and worth stating, because a value is not a strategy anywhere in this subject.

A family to look at all at once #

Lining several sets up beside each other is the fastest way to see that the periods are not predictable, and that the sequences are nonetheless completely regular once they begin.

Every one of those was computed by the mex rule and its period found by search over two thousand values, not looked up. The table is in the essay because it can be regenerated: the same seven lists put through the same code produce the same seven rows, and a reader with a pencil can check any row against the definition in a couple of minutes.

Three observations fall out. The period is not the largest take, nor the number of takes, nor anything else visible in the list: $\{1,3,5\}$ has period 2 and $\{2,5,6\}$ has period 11. Every one of these begins its period at heap 0, with no irregular prefix — which is common for small sets and not guaranteed in general. And the largest value in a period never exceeds the number of takes, for the reason the previous section gave: a mex over three options cannot exceed 3.

Where these came from #

Subtraction games are old and mostly anonymous — the ones with lists $\{1, \ldots, k\}$ are folk games with a dozen names, and the P-positions being the multiples of $k+1$ is the sort of fact that gets rediscovered every generation.

What is not anonymous is the framework that makes them a family rather than a list of puzzles. Sprague and Grundy, working independently around 1935, proved that every impartial position equals a Nim heap; Guy and Smith in 1956 organised the whole class of take-and-break games into octal codes, of which subtraction games are the tamest corner, and asked the periodicity question that is still open one step above them.

Which places this rung precisely. It is the base of the impartial ladder, the easiest thing in the subject to compute, and the only place in it where an infinite claim comes with a guarantee attached rather than a search and a hope.