Decided by exhaustion — page 11
Divisors that make every amount
Twelve's divisors — 1, 2, 3, 4, 6, 12 — can be chosen to add to every whole number from one to twenty-eight. Numbers like that are called practical, a test on their primes decides them, and they turn out to be counted like the primes: about 1.336 x / log x of them below x. For practical numbers Goldbach's conjecture and the twin conjecture are theorems.
The arcs that make the centre cheap
Finding a circle's centre with the compass alone, from two points on it, costs six circles when the points are placed with no special relation — and as few as two when the arc between them is 60°. Searching every arc in steps of five degrees maps the price exactly, and it is not a smooth function of the arc: it is a list of coincidences, each one a small number of compass steps that happens to land on a chord equal to the radius.
Euclid's proof run as a machine
Euclid proved there is no last prime by multiplying the primes on any list, adding one, and noting that the result has a prime factor not on the list. Run the proof as a machine — start from 2, and each time take the smallest prime factor of one more than the product so far — and it produces 2, 3, 7, 43, 13, 53, 5, 6221671, … a sequence that never repeats, that reaches small primes late and large ones early, and that nobody can prove reaches every prime.
The best of thirty-four thousand scramblings
Verhoeff's check digit multiplies digits in the symmetry group of a pentagon after scrambling each one a different number of times, and 34,040 scramblings make it catch every swap of neighbours. Graded on the rarer errors, none of them catches everything, the best catch 86 of 90 doubled-digit slips and 848 of 900 swaps across a digit — and the scrambling Verhoeff published in 1969 is one of the forty that are best at both.
What a junction can save
Join a set of towns by roads that may meet only at towns, and the shortest such network is easy to find. Allow junctions anywhere and the network gets shorter — but never, it is conjectured, by more than 13.4%, the saving the Fermat point makes on an equilateral triangle. Computed exactly on 1,304 random sets of up to seven towns, the average saving is about 3%. An adversarial search drives it down to the bound and no further, and a hexagon with its centre attains it exactly. The proof of the bound that was accepted for twenty years has a gap.
One determinant for every kaleidoscope
Three mirrors close up into a kaleidoscope when the angles of their triangle add to more than half a turn. In more dimensions there is no triangle to add up, but there is a matrix — the inner products of the mirrors' directions — and the mirrors close up exactly when it is positive definite. Trying every arrangement of up to nine mirrors against that one test finds Coxeter's list: three families in every dimension, a fork that runs out at eight mirrors because its determinant reaches zero at nine, and five exceptions. The same search finds the hyperbolic kaleidoscopes, and finds that they stop at five mirrors.
Twenty-seven million cubics, sorted by their symmetry
Write down every cubic x³ + ax² + bx + c with coefficients up to 150 and sort each by its Galois group. 98.7% have all six symmetries of three roots. The rest are reducible at a rate of fifteen in every H², or cyclic at five in every H to the three-halves — and the cyclic ones turn up four times as often as chance would allow, because discriminants are not random numbers.
The quartics whose roots stay paired
A quartic can have five different Galois groups, and in a box of nearly fourteen million quartics they do not come in order of size. The eight-element group D₄ outnumbers the twelve-element A₄ thirty-five to one. Every even quartic has a smaller group than S₄, and moving one step off that plane restores the full group almost everywhere.
Every random game has an odd number of equilibria
Find every equilibrium of eleven thousand random games — pure and mixed, by trying every pair of strategy sets the players might mix over — and the totals are 1, 3, 5, 7, … and never an even number. The count is a sum of signs: equilibria of index +1 outnumber those of −1 by exactly one in every game. The average grows about 28% with each strategy added, and searching for the game with the most turns up the coordination game's 2ⁿ − 1, a pattern that holds only up to five strategies.
Edges that crowd each other out
Pick a spanning tree of a graph uniformly at random, and the presence of one edge makes every other edge less likely — a theorem of Kirchhoff's electricity. Pick a forest instead, or a connected subgraph, and the same is believed and unproved. Checking every pair of edges in every labelled graph up to six vertices, 871,926 pairs for forests alone, finds no exception, and comes as close as 0.9994 to one.
Stable cycles a hair from Hénon's chaos
Nobody knows whether the Hénon map at a = 1.4 is chaotic, because a stable cycle in a window too thin to see would look exactly the same. So hunt the windows: a stable orbit of period 19 at a = 1.4001616, proved to exist and to attract by interval arithmetic, in a window 15 hundred-millionths wide and 0.00016 from the classical value — and nothing nearer, down to a spacing of a ten-billionth.
How far apart two triangulations can be
Any triangulation of a polygon can be turned into any other by flipping one diagonal at a time. On an octagon seven flips always suffice; on a polygon with m vertices the worst case is 2m − 10 flips once m reaches thirteen, a value Sleator, Tarjan and Thurston proved with hyperbolic geometry in 1988. Breadth-first search over all 58,786 triangulations of the 13-gon finds the sixteen.
Resolving one letter away at a time
Davis and Putnam's procedure of 1960 decides a set of clauses by removing its letters one at a time, replacing every clause that mentions a letter by all the ways of resolving it away. On a cycle the clauses never multiply; on a grid they swell by a factor of three and a half for each extra row, and on the 4 × 4 grid each extra unit of the order's width doubles the peak exactly. The cost is not the size of the formula but how wide it is.
One block of quantifiers, read off an algebra
Which properties of words can be stated with existential quantifiers alone — 'there are positions, in this order, carrying these letters' — and Boolean combinations of such statements? Imre Simon answered in 1975: exactly those whose syntactic monoid is J-trivial. Of the 57,068 languages that automata of up to four states recognise, 848 pass the test, and every one of them is decided by which words of length three or less it contains as scattered subwords.
A curve of pixels needs two kinds of touching
On a screen a closed curve is a ring of pixels, and whether it has an inside depends on which pixels count as touching. Let diagonal pixels touch, and the inside leaks out through the corners; forbid it, and a curve can fence in a region while being twelve separate dots. Of the 1,048,575 sets of pixels in a small window, every simple closed curve obeys the Jordan curve theorem exactly when the curve and the rest of the plane are given different rules.
The magic squares are a space
A magic square is a grid whose rows, columns and diagonals share one sum. The conditions are linear, so the squares form a space: three-dimensional for order three, eight-dimensional for order four, n² − 2n in general. Inside the space of order three the eight classical squares are eight points with coordinates ±1 and ±3. Of the 880 squares of order four, 640 are singular matrices, and the search finds the reason: a symmetry of the rows and columns that carries every number to the one it adds to seventeen with.
Sellers on a street stand back to back
Put two ice-cream sellers on a beach and they end up side by side in the middle, though customers would walk half as far if they stood at the quarter marks. Three sellers never settle at all: whoever is squeezed in the middle leaps outside, for ever. Four stand in pairs, five in pairs with one alone in the centre, six in endlessly many ways. Let them set prices too, with travel costing the square of the distance, and the conclusion reverses: the two sellers move as far apart as the beach allows.
Dots that never repeat a step
Place n dots on an n-by-n grid, one in each row and column, so that no two pairs of dots are joined by the same step. These Costas arrays were invented for sonar, and finite fields build them: a primitive root modulo a prime gives one family, a pair of primitive elements in any finite field another. Yet the constructions account for almost none of the arrays that exist — 92 of the 2,160 of order ten — and for orders 32 and 33 nobody has found a single one.
No triangle, and four colours
A graph that contains four mutually joined points needs four colours. The converse looks obvious — a graph needing four colours should contain something like that — and it is false. Grötzsch's graph has eleven points, no three of them mutually joined, and needs four colours. Mycielski found a step that adds one colour to any graph without creating a triangle, so graphs with no triangle can need any number of colours, and their need is spread through the whole graph, with no part to point at.
How often a number can appear in Pascal's triangle
Every number bigger than one appears in Pascal's triangle at least twice, next to the 1 at each end of its own row. A few appear more often: 120 appears six times, and 3003 eight — as C(3003, 1), C(78, 2), C(15, 5) and C(14, 6), each twice. Counting every entry up to a million million finds seven numbers that appear more than four times and none that appear five, seven or more than eight. Whether any number appears ten times, or whether there is any limit at all, is unknown.
A cube through a hole in a cube
Prince Rupert of the Rhine bet that a hole could be cut through a cube large enough for an equal cube to pass through it, and won. The trick is to look at the cube along a direction near its long diagonal, where its shadow is a hexagon wide enough to hold a square face with room to spare: a cube 6% larger can pass. All five Platonic solids turn out to have such a passage, found by searching over the directions from which a solid is seen — and in 2025 a solid was found that has none.
The order that keeps elimination narrow
Eliminating letters one at a time costs whatever the widest step costs, and the least width any order can achieve is the treewidth of the formula's graph. Finding it exactly is NP-hard, but a search over sets of letters instead of sequences finds it for small graphs, and a greedy rule that adds the fewest new edges finds it on 566 of 600 random graphs and misses by more than one only once. On Tseitin's 6 × 6 grid that rule forms twenty-four times fewer resolvents than sweeping row by row. What it cannot do is prove that its order is the best.
Houses traded in cycles
Everyone owns a house and would rather have someone else's. Let each point at the owner of the house they want most, follow the arrows into a cycle, and trade around it; repeat. The result is the only allocation no group can improve with its own houses, and nobody can gain by lying about what they want — the two guarantees stable matching could not give together.
The shortest string holding every ordering
Thirty-three symbols hold all twenty-four orderings of 1, 2, 3, 4 as blocks of four in a row, and no shorter string does. The formula 1! + 2! + … + n! gives the shortest length for up to five symbols and was believed for all of them — until a string of 872 for six beat its 873, and a lower bound posted anonymously on a forum left everything between 867 and 872 open.