A position loses exactly when every move from it leads to a winning position. That definition is a recurrence whose entries are two symbols rather than numbers, and evaluating it upward from zero labels the whole game. With moves 1, 3 and 4 the losing positions are 0, 2, 7, 9, 14, 16 — a period of seven that is not the multiples of anything, and that the table exhibits over nineteen positions without proving.
Core ideas
The hard idea is the last one: the period is measured over the positions on screen, and the proof that the labels are eventually periodic is a separate and quite different argument.
There is no arithmetic here. A position is losing when every move from it reaches a winning position, and winning when some move reaches a losing one. Those are the two quantifiers, and they are duals, so one definition suffices. The base case falls out of it: a position with no legal move has vacuously every move reaching a win, so it loses.
Every move strictly decreases the position, so the label of p depends only on labels below p, and counting upward from zero is the order that has them all. The lab checks this against a memo-free recursion that labels each position from scratch, so the table is compared with a second computation rather than displayed and believed.
The panel reports the smallest k for which the labels agree at every pair of positions k apart, within the range shown. That is a statement about nineteen positions. The general fact — that such a game's labels are eventually periodic — comes from a pigeonhole argument over windows of labels, and it bounds the period rather than giving its value.
The material
The definition, the labelling, the second computation that checks it, and the exact status of the pattern.
Two players alternate. From a position p a player may move to p − m for any m in a fixed subtraction set with m ≤ p. A player with no legal move loses. A position is losing if the player about to move from it loses under perfect play, and winning otherwise.
A position p is losing if and only if every move from p leads to a winning position; equivalently, p is winning if and only if some move from p leads to a losing position. A position with no legal moves is losing.
By strong induction on p. Suppose every position below p is correctly labelled. If some move from p reaches a losing position, the player to move takes it and hands the opponent a position from which, by hypothesis, the opponent loses; so p is winning.
If every move from p reaches a winning position, then whatever the player does, the opponent is handed a position from which the opponent, by hypothesis, wins; so p is losing. The two cases are exhaustive, and the vacuous case — no moves at all — falls under the second, which is why a terminal position loses.
□
Notice that this table has no objective to optimise. Every other page on this course computes a best value; this one computes a truth value, and the recurrence is a pair of quantifiers rather than a minimum or a sum. That is worth seeing once, because it separates the technique — a table, an order, a recurrence — from the arithmetic that usually accompanies it.
The labels come out L W L W W W W L W L W W W W L W L W W. The losing positions are 0, 2, 7, 9, 14 and 16. Position 2 loses because its only legal move is to 1, which wins; position 7 loses because its moves reach 6, 4 and 3, all winning. The panel reports the smallest period over the positions shown as 7, and a memo-free minimax recursion agrees with the table at every position.
That period is not the multiples of anything. Losing positions are those congruent to 0 or 2 modulo 7, which is two residues rather than one. Change the subtraction set to 1, 2 and 3 and the losing positions are exactly the multiples of 4, and that pattern has an argument a reader can give in one line. Change it to 1 and 2 and the answer is the multiples of 3. Change it to 2 and 5 and positions 0 and 1 both lose, so the pattern does not even begin with a single loss.
The panel's period is computed by testing, for each k in turn, whether the labels agree at every pair of positions k apart among the positions labelled. With nineteen positions on screen and a reported period of 7, that is two full repetitions and a bit. It is a measurement, and if the pattern broke at position 40 the panel would say nothing about it.
Let M be the largest element of the subtraction set. The label of a position is determined by the labels of the M positions below it. There are at most 2^M distinct windows of M consecutive labels, so some window repeats, and from that point the sequence of labels repeats with a period at most 2^M.
Consider the sequence of windows w(p) consisting of the labels of positions p−M through p−1. The recurrence determines the label of p from w(p) alone, and therefore determines w(p+1) from w(p). So the sequence of windows is generated by a function from a finite set to itself.
A sequence of elements of a set of size at most 2^M generated by iterating a function must repeat a value within the first 2^M + 1 steps, and once a window repeats, everything after it repeats too. Hence the labels are eventually periodic with period at most 2^M. For the subtraction set 1, 3, 4 that bound is 16, and the measured period is 7 — the bound is true, loose, and says nothing about which value below it occurs.
□
Those two results are exactly the pairing this Subject insists on. The table measures a period of 7 over nineteen positions. The pigeonhole argument proves eventual periodicity with period at most 16, for every subtraction set. Neither implies the other: the measurement does not establish that 7 continues, and the proof does not say the period is 7 or that it starts at position zero rather than later. Raising the range on the lab extends the measurement and never turns it into the theorem.
The cost is the least interesting thing on the page and is worth one sentence: nineteen positions are labelled with nineteen calls, each looking at up to three predecessors, so labelling n positions is Θ(n) for a fixed subtraction set. The memo-free recursion that checks it is exponential and is capped at position 24 for that reason.
Interactive
The definition evaluated upward, and checked against a recursion
Method
The first three steps are mechanical; the fourth is the one this page exists for.
Losing when every move wins, winning when some move loses. Resist turning it into a formula about the position's value: the two quantifiers are the recurrence, and games where the pattern is not arithmetic are exactly where a formula would be invented.
The fill order is forced by the fact that a move strictly decreases the position. There is nothing to choose and nothing to get wrong, which makes this the cheapest table on the course to be confident about.
A memo-free minimax recursion at each position shares no state with the table. Run it at every position while the positions are small, and compare. The lab does this on every redraw up to its cap.
Say over how many positions it was observed. If you want the claim that it continues, the argument is the pigeonhole one over windows of labels, and it gives eventual periodicity with a bound rather than the value you measured.
With moves 2 and 5, positions 0 and 1 both lose, so the pattern opens with two losses in a row and a reader who has assumed a single loss at zero will misread the whole table. The beginning is where measured patterns most often mislead.
Each position is labelled from the definition using only the labels below it. A position is losing when every move from it reaches a winning position.
The residues are the honest way to state what was seen: the losing positions are those congruent to 0 or 2 modulo 7, over the range labelled. Two residues, not one, which is why no multiple-of-something description fits and why the table had to be computed rather than guessed.
Compare with the subtraction set 1, 2, 3, where the losing positions are 0, 4, 8, 12, 16 and the argument is one line: from a multiple of four, whatever you take, your opponent takes the complement to four and hands back another multiple of four. That argument is a proof for every position, and nothing like it is available for 1, 3, 4 — the lab measures 7 and the general theorem bounds the period by 16.
For a faded rehearsal, switch the subtraction set to 2 and 5 before running it. The supplied first move: from position 1 there is no legal move at all, so 1 loses, and so does 0. Predict the first six labels, then check — and note how much harder the pattern is to see when it does not begin the way you expect.
You should be able to write the two quantifiers, explain why a terminal position falls out of them, check the labels against a second computation, and separate a period measured over a range from the eventual periodicity a pigeonhole argument proves.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.