Small cases lie — page 12
Applied
The market with the most stable matchings
Random preferences give a sixteen-a-side market about five stable matchings. Nesting a two-a-side market inside itself gives the same size 195,472, every one of them listed. That construction is forty years old and nothing has beaten it, while the ceiling above it has fallen from 2¹⁷ⁿ to 3.55ⁿ. The truth lies somewhere between 2.28ⁿ and that.
Discrete
Alone on the track
Runners set off together at different constant speeds. Is each of them, at some moment, far from all the others? A pigeonhole on time gives half the conjectured distance in two lines, and sixty years of work have not closed the other half. The speeds 1, 2, …, k are exactly at the limit, and so, surprisingly, are 1, 3, 4, 7 and 1, 4, 5, 6, 7, 11, 13.
Geometry
Eight points that refuse the cube
Place eight points on a sphere so that the closest pair is as far apart as possible. A cube manages 70.53°. Rotating one face by 45° and pushing the faces together gives 74.86°. A botanist counting pores on pollen grains asked this in 1930, and proofs still stop at fourteen points: one search in five hundred finds the best thirteen, whose failure to reach 60° is why kissing spheres stop at twelve.
Geometry
The triangle a triple point buys
How many triangles can eight straight lines cut out? A count of line segments says at most 16, a parity argument takes off one, and the tables say 15. Yet every one of the 1,232,944 arrangements in which only two lines ever cross stops at 14. The fifteenth triangle exists only if three lines are made to meet at exactly one point, and moving a line by a hundredth loses it.
Logic
The order of the questions
Decide a Boolean function by asking about its variables one at a time, and share every state that behaves alike. For a₁b₁ + a₂b₂ + … the result has 2n + 2 nodes if partners are asked together and 2ⁿ⁺¹ if they are apart. All 40,320 orders of eight variables give anything from 10 to 32 nodes, while multiplication's middle bit grows fast in the best order of all.
Number
Sums with too few primes
Add 2 to 6,436,341 and the sum is 23⁵: three numbers with only four primes between them, and their product 15,042 is far smaller than the sum. The abc conjecture says this can happen only so far. Of 606 such triples up to 200,000, only seven reach quality 1.4, and if the conjecture holds, Fermat's last theorem and much else follows for large exponents in a line.
Number
The comet Goldbach left behind
Count the ways each even number is a sum of two primes, and the points do not form a smear. They split into bands: 12,000 has 302 ways and 12,002 has 115. One small product over odd prime factors explains every band and brings them all to a single line, and it says the count grows without bound. Nobody can prove the count is never nought.