Theme

Decided by exhaustion — page 11

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.
Twelve's divisors make every total up to twenty-eight. Stacked bars for each total from 1 to 28, each built from distinct divisors of 12. Number

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 price of the centre, arc by arc. 10°: 5, 15°: 4, 20°: 4, 25°: 6, 30°: 3, 35°: 6, 40°: 6, 45°: 5, 50°: 5, 55°: 6, 60°: 2, 65°: 6, 70°: 5, 75°: 4, 80°: 6, 85°: 6, 90°: 5, 95°: 6, 100°: 4, 105°: 4, 110°: 5, 115°: 6, 120°: 6, 125°: 6, 130°: 5, 135°: 5, 140°: 4, 145°: 6, 150°: 3, 155°: 6, 160°: 6, 165°: 4, 170°: 5, 175°: 6. Computation

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 argument run twenty times. The first 20 terms of the Euclid–Mullin sequence: 2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957. Number

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.

Every swap-proof scrambling, graded on twins and jump swaps. 34040 permutations; twin errors caught range 50–86 of 90, jump transpositions 600–848 of 900; Verhoeff's at (848, 86). Computation

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.

Seven towns joined with junctions and without. Seven random points: spanning tree 1.65407, Steiner tree 1.54997 with 2 junctions, ratio 0.93707. Geometry

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.

Every finite kaleidoscope on up to eight mirrors. 1: A₁; 2: A₂ B₂ H₂ G₂; 3: A₃ B₃ H₃; 4: D₄ A₄ B₄ H₄ F₄; 5: D₅ A₅ B₅; 6: E₆ D₆ A₆ B₆; 7: E₇ D₇ A₇ B₇; 8: E₈ D₈ A₈ B₈. Geometry

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.

Every cubic x³ + bx + c up to 30, sorted by its Galois group. A 61 by 61 grid of cubics x³ + bx + c: 309 reducible, lying on lines c = −r³ − rb; 20 cyclic with square discriminant; 3392 with group S3. Algebra

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.

Even quartics never have the full group, and one step away almost all do. Even quartics x^4 + bx^2 + d to 20: reducible 199, S4 0, A4 0, D4 1338, C4 20, V4 124. With +x: reducible 157, S4 1524, A4 0, D4 0, C4 0, V4 0. Algebra

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.

Where the equilibria of a random four-by-four game are found. 7 equilibria with supports (1, 1), (3, 2), (4, 3), (13, 12), (14, 13), (34, 23), (134, 123). Applied

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.

Two edges of a small graph, and whether one makes the other less likely. tree: 8 total, 5 with e, 5 with f, 3 with both, ratio 0.9600; forest: 24 total, 10 with e, 10 with f, 4 with both, ratio 0.9600; connected: 14 total, 10 with e, 10 with f, 7 with both, ratio 0.9800. Probability

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.

Two stable cycles a hair from the classical Hénon attractor. The Hénon attractor at a = 1.4 with the certified stable period-13 orbit at a = 1.39945 and period-19 orbit at a = 1.4001616 drawn over it. Dynamics

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.

Seven flips between the octagon's farthest triangulations. A shortest flip path of length 7 between two of the 132 triangulations of the octagon. Discrete

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.

Eliminating a letter by resolving it away. Tseitin triangle: 6 clauses; eliminating x: 4 resolvents, 2 tautologies, 4 clauses left; clause counts 6 → 4 → 2 → 1 ending with the empty clause. Logic

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.

A subword can be checked with one quantifier block; a factor cannot. Subword aba: monoid 7, J-trivial, degree 3; factor aba: monoid 12, aperiodic, not J-trivial; witness abab / abba. Logic

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.

Four ways to say which pixels touch. curve 8, rest 4: curve 1 pieces, rest 2 pieces; curve 8, rest 8: curve 1 pieces, rest 1 pieces; curve 4, rest 4: curve 12 pieces, rest 2 pieces; curve 4, rest 8: curve 12 pieces, rest 1 pieces. Topology

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.

Every magic square of order three is a point in a space of three. Basis J, U = (1,-1,0,-1,0,1,0,1,-1), V = (0,-1,1,1,0,-1,-1,1,0); Lo Shu = 5J − 3U + V; dimension of the order-3 magic space 3. Algebra

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.

Where sellers stand when nobody wants to move. 2 sellers: 1 equilibria (e.g. 12,12 of 24); 3 sellers: 0 equilibria; 4 sellers: 3 equilibria (e.g. 6,6,17,18 of 24); 5 sellers: 4 equilibria (e.g. 4,4,12,19,20 of 24); 6 sellers: 25 equilibria (e.g. 3,3,9,14,20,21 of 24). Applied

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.

Ten dots that never repeat a step. Welch array p=11, g=2: 0,1,3,7,4,9,8,6,2,5; difference triangle rows: 1 2 4 -3 5 -1 -2 -4 3 / 3 6 1 2 4 -3 -6 -1 / 7 3 6 1 2 -7 -3 / 4 8 5 -1 -2 -4 / 9 7 3 -5 1 / 8 5 -1 -2 / 6 1 2 / 2 4 / 5. Computation

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.

Eleven vertices, no triangle, four colours. Grötzsch graph: 11 vertices, 20 edges, triangle-free; 3-colouring search 27 nodes, none; 4-colouring 10120121230; proper 4-colourings 12480 (520 up to relabelling). Discrete

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.

Where 3003 appears eight times. 3003 = C(3003,1) = C(78,2) = C(15,5) = C(14,6) and their mirror images; N(3003) = 8. Discrete

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 passes through a hole in a smaller cube. Cube passage: λ = 1.060660172 (3√2/4 = 1.060660172); outer hexagon, inner square. Geometry

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.

An elimination order is a tree of bags. 3 × 3 grid, optimal order a, c, g, i, b, d, f, h, e; bags abd, bcf, dgh, fhi, bdef, defh, efh, eh, e; treewidth 3. Logic

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.

Everyone points at the house they want. Favourite owners: A→F, B→G, C→H, D→F, E→B, F→G, G→B, H→H, I→G. Cycles: GB; H. Final allocation: A gets F's, B gets G's, C gets A's, D gets I's, E gets D's, F gets C's, G gets B's, H gets H's, I gets E's. Applied

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.

Every ordering of four in thirty-three symbols. 123412314231243121342132413214321: windows 1234 2341 3412 4123 (1231) 2314 3142 1423 4231 (2312) 3124 1243 2431 4312 (3121) (1213) 2134 1342 3421 4213 (2132) 1324 3241 2413 4132 (1321) 3214 2143 1432 4321. Computation

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.

All themes