Decided by exhaustion — page 13
Lines that leave half on each side
Scatter ten points on a page and draw every line through two of them that leaves four on each side. There are at least five such halving lines and at most thirteen, and every point lies on an odd number of them. Both facts come from turning a line through half a revolution, the argument that halves two shapes with one cut. How many halving lines n points can have is the k-set problem, and its answer lies somewhere between a little more than n and n to the four-thirds.
How often a table of random signs is flat
Fill a square table with random plus and minus signs and ask whether its determinant is nought. For four rows the answer is yes two times in three. The chance then falls, and since 2020 it has been known to fall at exactly the rate of the dullest accident, two rows or columns equal or opposite. The conjecture is that this accident is, in the end, the whole story. Every size a computer can reach says otherwise, and the theory says the computer has not gone far enough.
A core is a rare thing to find at random
A game has a core when the whole can be shared so that no group would do better on its own, and Bondareva and Shapley turned that into a finite list of checks. For three players there are five checks; for four, forty-one; for five, 1,291. Draw the coalitions' values at random and the list wins: a third of three-player games fail, nineteen four-player games in twenty, and not one five-player game in two thousand passes. The cores that theorems promise come from structure, and structure is exactly what a random game lacks.
A code built from an icosahedron
Write down which corners of an icosahedron are not joined by an edge, put the table beside a diagonal of ones, and add the twelve rows together in every combination. The 4,096 strings of 24 bits that come out differ from each other in at least eight places, occur in only five weights, and — with one bit deleted — fill the space of 23-bit strings so exactly that every one of the 8,388,608 lies within three flips of exactly one of them. This is the Golay code, which carried Voyager's pictures home, and its words of weight eight cover every five of the twenty-four positions exactly once.
The busiest point in a set
Scatter points in the plane, not all on one line, and draw every line through two of them. Some point lies on many of those lines — but how many must? Gabriel Dirac guessed half: in any such set, some point is on about half of the lines it could be on. Split the points evenly between two lines and no point does better than half plus one, so the guess cannot be raised. Proving it is another matter. Seventy years on, the best theorem says a third.
Syllogisms that say most
The syllogism knew four words — all, no, some, some not — and two thousand years of logic decided which of its 256 forms were valid. Add 'most', a word everyone uses in arguments, and the 256 become 864. A diagram with marks for 'empty' and 'occupied' can no longer decide them, because 'most' compares sizes; but writing the number of things in each region turns every form into a linear programme, and the programme decides all of them at once. Thirty-one are valid, including one Augustus De Morgan found in 1847: if most M are S and most M are P, then some S are P. And 'most' cannot be passed along a chain: ninety-nine per cent of S can be M, ninety-nine per cent of M can be P, and no S be P at all.
A small quotient for every denominator
Pick a denominator, any whole number. Among the fractions with that denominator, is there always one whose continued fraction has no large entries — whose path down the Stern–Brocot tree never turns the same way more than five times running? Stanisław Zaremba guessed so in 1972, for a reason to do with sampling a square evenly. Every denominator up to a hundred thousand obeys, with only 6, 54 and 150 needing a five. The guess is proved for almost every denominator and not for all, and the reason it ought to be true is a dimension: the reals whose quotients stay at most five fill a set of dimension 0.837, enough to give each denominator thousands of good fractions on average, and the open question is whether averages are kept everywhere.
Two fields that every prime confuses
Reduce x⁸ − 3 and x⁸ − 48 modulo any prime other than 2 and 3 and factor them: the two lists of factor degrees are the same, at all 9,590 such primes below 100,000. The fields the two equations define are still different. The reason is a pair of ways for one group to permute eight roots, with the same cycle lengths element by element and different fixed points — the same coincidence, in degree seven, as the points and lines of the Fano plane.
How often the rules find the majority favourite
When one candidate beats every rival head to head, a voting rule ought to elect it. Plurality does about three times in four when every ranking is equally likely, the runoff between the top two 96 times in a hundred, Borda's count 90. Every profile of up to 51 voters is counted exactly, the limit is sampled, and adding candidates pulls plurality down below one half.
A code that survives a lost bit
A flipped bit leaves the word the right length and wrong in one place; a lost bit leaves it one short, with no sign of where the gap was. Keep only the words whose 1s sit at positions adding up to a multiple of n + 1, and any single lost bit can be put back. The price is about log₂(n + 1) bits, the same as the Hamming code pays for a flip.
The search that reuses a point
To find the peak of a function that rises and then falls, evaluate it at two points and throw away the part beyond the lower one. Place the points so that the survivor can be used again, and there is exactly one way to do it: at the golden ratio. Each new evaluation then shrinks the bracket to 0.618 of its width, and with a fixed number of evaluations nothing does better than Fibonacci's numbers.
A quarter of the bases at most
Carmichael numbers pass Fermat's test for every base they share no factor with, so Fermat's test can be fooled for ever. Watch the squarings on the way to aⁿ⁻¹ instead, and a prime allows only one pattern; 561 lets just 10 of its 320 bases through, and Monier and Rabin proved that no odd composite but 9 lets through more than a quarter. Four fixed bases prove every number below 3.2 billion prime or not.
Curves that cross a line and close
Draw a closed curve that crosses a straight line 2n times and never crosses itself. Above the line it is a set of nested arches, below it another, and every such curve is a pair of the Catalan number's arch systems that happen to close into one loop. There are 1, 2, 8, 42, 262, 1,828 of them, and every count computed so far grows by a factor creeping towards 12.26 — a number nobody can prove, with an exponent conjectured from the physics of random surfaces.
An electorate too large for a dictator
Arrow proved that a voting rule with his four properties must have a dictator, and his proof uses the finiteness of the electorate exactly once. With infinitely many voters the dictator can vanish: the sets of voters who get their way form an ultrafilter, and every free ultrafilter is a rule with all four properties and nobody in charge. The catch is that no such rule can be written down. Its existence is a fragment of the axiom of choice.
Four quantifiers, one of them blind
In 'for every x there is a y, and for every u there is a v', the last choice may depend on everything before it. Leon Henkin asked in 1961 what happens if v may depend on u alone. Using nothing but the equals sign, four such quantifiers then say that a set has an even number of points, or that it is infinite — things no ordinary sentence can say — and the game behind the sentence can end with neither player able to win.
A second empty square
With one empty square a sliding tray can reach exactly half its arrangements, and the half it misses is guarded by a sign. Leave a second square empty and the guard disappears — every arrangement is reachable, two tiles can be exchanged in four moves, and the far end of the three-by-three tray comes in from thirty-one moves to twenty-four. Searching every tray with every number of holes shows what each extra square of room is worth.
Two lost bits
One congruence repairs any single lost bit, and the set of words it defines is believed to be the best possible. Two lost bits defeat it. An exhaustive search finds the largest codes that survive two — 2, 2, 4, 5, 7 and 11 words for lengths 4 to 9 — and Helberg's congruence, with weights that grow like Fibonacci numbers, gives a code that provably works at every length but spends a fixed share of every bit on protection. The best codes need only about four times the logarithm of the length.
Three arrows in and three out
Put an arrow on every edge of the cubic grid so that every point has three arrows in and three out. On the square grid the same question — two in, two out — has an exact answer, found by Elliott Lieb in 1967: about 1.5396 arrangements per point. On the cubic grid nobody knows the answer. Pauling's guess of 2.5 is a proven lower bound, and exact counts on prisms of the grid come down towards it from above — 2.794, 2.682, 2.587 as the cross-section widens — without reaching it.
The narrowest refutation
A resolution refutation can be long, and it can be wide — use clauses with many letters. Width turns out to be the easier of the two to compute exactly: derive everything that can be derived without ever writing a clause longer than w, and see whether a contradiction appears. Doing that for small formulas shows the parity formulas of graphs needing wider clauses than they contain, by more on graphs that are harder to cut in half, and the pigeonhole formulas needing no extra width at all — although every refutation of them is exponentially long. Width is not the whole price.
What an incomplete set of connectives can say
Nand alone can express every truth function, and Post's five properties say exactly which sets of connectives can. That answers the question at the top. Below it lies a whole landscape: and alone expresses 7 of the 256 functions of three letters, xor 8, implication 38, and the sixty-four sets that can be drawn from and, or, not, xor and the two constants fall into just 22 different classes of expressible functions. The classes fit together into Emil Post's lattice of 1941 — countably infinite, completely described, and on three letters small enough to draw.
Divisors that take a prime whole
Six is perfect because its proper divisors 1, 2 and 3 add up to 6. Keep only the divisors that take each prime of a number completely or not at all — for 60, that is 1, 3, 4, 5, 12, 15 and 20 — and ask for the same coincidence. Below ten million it happens four times: 6, 60, 90 and 87,360. The fifth has twenty-four digits. And unlike ordinary perfect numbers, where nobody knows whether an odd one exists, here a two-line argument rules every odd number out.
Nineteen fourth powers, and then sixteen
Edward Waring claimed in 1770 that every number is a sum of at most nineteen fourth powers. It is true, and it is needed: 79 takes nineteen, because its remainder on division by sixteen forces fifteen ones. But only seven numbers need nineteen, the last of them 559; the last to need eighteen is 1,248, and the last to need seventeen is 13,792. Counting every number to ten million shows the stragglers thinning out and the one obstruction that never goes away — the remainder modulo sixteen, which makes 31, 496, 7,936 and every 31·16ᵐ need sixteen for ever.
A prime leaves no room for a comb
Take the table of powers of a root of unity, pick any rows and any equal number of columns, and take the determinant. At order 12 about one such determinant in six is exactly nought. At order 11, among 184,756 of them, none is, and in 1926 Chebotarev proved that none ever is at a prime. It means a signal on p places and its transform together occupy at least p + 1, while a comb on twelve places and its transform take 4 and 3.
How few distances fix a word
An unknown word of a thousand bits can be read one bit at a time with a thousand questions. Ask instead for its distance from a chosen word, and each answer is worth about half of log₂ n bits, so roughly two hundred distances fix it. A balance reading many coins at once is the same question. So is Mastermind, in which Knuth's rule finds any of the 1,296 codes in at most five guesses and a mean of 4.476, and no first guess is best on both counts.