Gray code
Named by 7 essays across 4 fields — each of them below, with the objects they name alongside it.
The map that puts neighbours side by side
Reorder the rows of a truth table so that neighbouring squares differ in one letter, and finding a short formula stops being algebra and becomes the problem of covering a shape with rectangles.
A walk that changes one thing at a time
Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.
Every place changes back
A closed walk through every corner of a cube changes one place at each step, and each place, having changed, must change back before the walk returns home. So every place changes an even number of times — which is why no walk on three places can share the work evenly, why perfect sharing is possible only when the number of places is a power of two, and what sorts the 1,344 walks on the 4-cube into exactly four kinds.
The walk through the middle levels
On seven places, the words with three ones and the words with four number thirty-five each. Is there a closed walk through all seventy, changing one place at a time and never leaving those two levels? On five places the answer is 24 walks, on seven and nine a search finds one in moments — and whether one exists for every odd length was open for thirty years, until Torsten Mütze proved in 2016 that it always does.
The cube that takes every corner
The simplex method is fast on every program anybody meets in practice. In 1972 Victor Klee and George Minty squashed a cube so that the method, choosing the steepest edge each time, visits all of its corners — 2ⁿ − 1 moves in n variables, with the optimum one edge from the start.
A quarter turn quiets the echoes
Lay a sequence of signs on a shifted copy of itself and add up the squares of the overlaps. Random signs leave the total near n²/2, and the squares modulo a prime, started a quarter of the way along, cut it to a twelfth. Exhaustive search finds far quieter short sequences, and no infinite family is proved to do better than 6.342.
One tour through every position of the Tower of Hanoi
Draw every position of the Tower of Hanoi as a point and every legal move as a line, and the picture is a Sierpiński triangle. The famous shortest solution runs straight down one side of it, spelling the binary Gray code as it goes. The slowest honest solution threads through every position once and spells the ternary one. And unlike the cube the binary Gray code walks, which has 1,344 closed tours at four dimensions, the triangle has exactly one at every size.
Named alongside it
The objects these essays reach for when they reach for this one.
HypercubeParityCounting argumentBinaryExhaustive searchGraphHamming distanceKarnaugh mapRecursionAutocorrelationBinomial coefficientBipartite graph