Theme

The thread: A theorem that names no move — page 5

Knowing who wins and knowing what to play are different achievements, and the subject is full of results that supply the first and refuse the second. A bound is sometimes all there is.

The law, on a board rather than in a bag. The parity law applied to every position of a real board that has fallen into chains and loops, with the verdict computed independently from the board's own strings. The components are the ones the geometry produces rather than the ones a sweep constructs.

Out in the world

A thousand positions and no exception

The parity law was fitted to constructed bags of chains and loops inside a string budget. A board's positions are a different population — the sizes are what the geometry allows, the components come correlated, and a six-box board holds exactly one position that is a loop of six. Tested on all 1,032 of them and all 160 of the four-box board's, the law is right every time, against a verdict computed from the strings by a walk that has never heard of a component.

One substitution, thirty-four years. Bouton's criterion and the Sprague–Grundy theorem run side by side over a family of games. They differ in one quantity: the heap's size against the heap's Grundy value. The exclusive-or that combines them is the same operation in both, and it is the one Bouton published in 1901.

How it was found

The step nobody took for thirty-four years

Bouton's criterion is that the heap sizes exclusive-or to nothing. The 1935 theorem is that the heap Grundy values do. The exclusive-or is the same operation in both and it is his, so the whole of the intervening thirty-four years is one substitution — and run over eight games and 672 positions, the substituted criterion is exact on every one while the original is exact on Nim and nowhere else.

Bouton's argument, indexed by a value. Bouton's two closure properties stated for every Grundy value rather than for nought alone: no move stays inside a value class, and every class above a value can reach it. Checked on each game and each value in range.

How it was found

The picture Bouton's proof leaves behind

His argument is two closure properties of one set, and the Sprague–Grundy theorem is the same two sentences with nought replaced by a variable — checked here on five games and every value in range, with no move staying inside a class and no class failing to be reachable from above. What the argument also leaves behind is a picture in which the values descend, and that is false: 99 of 444 moves here raise a value, and none of them is in Nim.

All themes