Combinatorial Game Theory
who wins, and by how much
Concept

Residue — where it appears

The remainder a whole number leaves on division by a fixed modulus. Residues mod a power of two are the low binary digits, which is why exclusive-or respects them and why a closed form for a nim-sum is usually a statement about residues mod 4 or 8.

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

What is left when the copies pair off. For each position, the difference between n copies and n times the mean, reduced to canonical form. The first two are drawn and the last column says what the sequence does after them: half of these settle into a short cycle and the rest produce a new leftover every time, all of them the same bounded size.

What is left when the copies pair off

A pile of n copies stays within a bounded distance of n times the mean, and the distance never grows. The difference is a game rather than a number, and what it actually is has a much better answer: for a plain switch it alternates between one fight and nothing at all, and for a fight with a follow-up it is different every time — bounded in size and unbounded in complexity.

temperature · Temperature Lasker's Nim in sixteen cells. A four-by-four table. Each row and column is a residue mod 4 of one part of a split heap, with the residue of that part's Grundy value beside it; each cell is the residue mod 4 of the split's value, the nim-sum of the two parts. Every split of every heap to four hundred lands in the cell its residues name.

The proof is sixteen cells

Lasker's Nim has a four-clause formula that was checked on two thousand heaps and never proved. The proof fits in a four-by-four table: the last two bits of a split's value are fixed by the last two bits of its parts, so no split can land in its own heap's class — except at 3 mod 4, where it lands exactly on the one value the takes leave missing and pushes the answer up by one.

impartial · Lasker One split is enough, and some are not. Lasker's Nim beside five versions of it that allow only some splits, over the first twenty-four heaps, with every cell that leaves the formula outlined. Allowing only the split that takes one counter off reproduces the whole sequence; allowing only equal halves turns it back into Nim.

One split is enough

A heap of n in Lasker's Nim offers ⌊n/2⌋ ways to split, and the values use at most one of them. Allow only the split that takes a single counter off and every heap to six hundred keeps its value; of all sixty-three sets of split sizes up to six, a set keeps the formula exactly when it contains 1 or 2. Equal halves alone give back plain Nim, because a split into equal parts is a move to nought.

impartial · Lasker The residue of a sum is the hotter part's. Every hot day-two value added to every hot day-three value, 7,854 sums in all, sorted by what happens to the residues: when the parts differ in temperature, on all 4,712 such pairs, the sum's residue is the hotter part's alone; when they are equally hot the residues add on 880, the sum grows colder on 2,237 and cancels to a number on 25.

The hotter residue survives

Charge a hot position its own temperature and subtract its mean, and an infinitesimal is left — its residue. Add two hot positions and the means add, the temperatures do not, and the residues do something stranger than either: on every one of 4,712 pairs whose parts differ in temperature, the residue of the sum is the hotter part's residue and nothing of the colder's. Cooling is additive, and a part cooled past its own temperature is a bare number. Residues add only when two parts are exactly as hot, and even then the fights usually cancel into something colder. The summary forgets; the game does not.

temperature · Dissociation Colder exactly when the residues cancel. Equally hot pairs of hot values, 3142 from days two and three and 3000 sampled from day three, sorted by whether the sum stays as hot, grows colder or is a number, and by whether the two residues cancel. Every sum that stays as hot has residues that do not cancel, and every sum that grows colder or is a number has residues that do.

Colder exactly when the residues cancel

Add two fights of one temperature and the sum either stays that hot or grows colder, and which one happens is decided by the smallest thing either fight carries. The sum grows colder exactly when the two residues are negatives of each other — on all 3,142 equally hot pairs from days two and three and 3,000 sampled from day three, and by a two-line argument from cooling's additivity. What survives the cancellation is another matter. Group the colder sums by their parts' thermographs and the survivor differs in every group that holds more than one pair: {1 | 0} and {1 | 0, ∗} draw the same diagram and leave different infinitesimals behind. The diagrams fix only the survivor's temperature: nought, or exactly the lowest bend of either part.

temperature · Dissociation

Named alongside it

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

Exhaustive searchDisjunctive sumInfinitesimalMean valueTemperatureThermographClosed formCoolingGrundy valueHot gameImpartialMex

All concepts