Theme

Decided by exhaustion — page 14

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.

A sorting network on 8 wires. Batcher's odd-even merge network with 8 wires, 19 comparators and depth 6; it sorts every input, checked on all 256 strings of noughts and ones.

Computation

A sort that never looks at the answers

Most sorting decides its next comparison from the last one. A sorting network decides them all in advance: a fixed sequence of swaps-if-out-of-order, wired up before any number arrives. Whether such a thing sorts everything can be settled by trying 2ⁿ strings of noughts and ones instead of n! orderings. Nineteen comparators sort eight numbers, and proving that nothing shorter sorts eleven took decades and a satisfiability solver. Over neighbours only, one single test, the reversed row, decides the whole question.

The twenty monotone functions of three letters. All 20 monotone Boolean functions of three letters drawn on the cube of inputs, from the constant false to the constant true.

Logic

Functions that only go up

Of the 256 logical functions of three letters, only twenty never turn off when a letter is turned on. Dedekind asked in 1897 how many such monotone functions there are for n letters. Computing the count is hard enough that the answer has advanced one letter every twenty-five years or so, and the ninth arrived in 2023, from two groups in the same month, at forty-two digits. Almost everything about the number comes from a single layer of the cube.

Why 78,557 · 2ⁿ + 1 is never prime. For k=78557: 3 divides when n is 0 mod 2; 5 divides when n is 1 mod 4; 7 divides when n is 1 mod 3; 13 divides when n is 11 mod 12; 19 divides when n is 15 mod 18; 37 divides when n is 27 mod 36; 73 divides when n is 3 mod 9; every exponent covered with period 36.

Number

Numbers that never make a prime

Multiply 78,557 by a power of two and add one. The result is never prime, for any power, though almost every other odd number gives a prime within a few doublings. The reason is that seven small primes take it in turn to divide the result, on a schedule repeating every 36 steps that leaves no step uncovered. Proving nothing smaller does this has taken sixty years of search, and five candidates are still running.

A full board has exactly one winner. A random 11 by 11 Hex board filled with two colours: second colour connects with a chain of 11 cells.

Topology

A board that cannot be drawn

Colour a rhombus of hexagons in two colours. One colour must join its two sides, and only one: in all 65,536 colourings of the four-by-four board, no exception. The proof is a walk along the colour boundary, the same walk that proves Sperner's lemma, and David Gale showed that the no-draw theorem of this board game is equivalent to Brouwer's fixed-point theorem. Nobody knows the winning strategy for a full-sized board, though a short argument proves one exists.

A game of Sprouts. A game on two spots in four moves: each move joins two spots with a free life and adds a new spot on the curve; at the end the two surviving spots lie in different regions.

Topology

A game decided before it starts

Draw some crosses on paper. Players take turns joining two free arms with a curve and adding a new cross on it. However they play, a game on n crosses lasts exactly 5n − 2 moves, so the winner is known before the first move: Euler's formula has already decided it. Its close relative Sprouts differs by one rule, leaving a real game whose winner for each size is known only by huge search, and which seems to depend on the size modulo six for no known reason.

All themes