Matpic
mathematics, in pictures
Theme

Decided by exhaustion — page 6

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.
Five certificates against any two of three decide. A table of every minimal balanced family on three players, what each demands of the game, and whether the grand coalition's value covers it — the complete test for whether a stable split exists. Applied

Five weighings and the question is closed

Searching the triangle of splits can only ever fail to find a stable one, which is not the same as there being none. Weighing five families of coalitions against the whole settles the question outright — and the family that fails is the proof that nothing survives.

 The splits of any two of three decide that nobody can out-argue. The triangle of all splits of a joint gain, with the splits marked at which every player's loudest complaint against every other is matched by an equally loud complaint back. Applied

An objection one player makes to another

The core lets a coalition object to everybody at once. Narrow it to one player objecting to one other, require every such objection to be met by an equally loud one coming back, and exactly one split survives — with no dictionary order anywhere in the argument.

 The most mass 2 deviations out, with only a mean and a variance. The distribution putting as much probability as possible outside a window 2 standard deviations wide, found by searching every triple of support points, with the quadratic certificate that bounds it drawn over. Probability

The bound is the answer to a search

Chebyshev's inequality is not a clever estimate that happens to be sharp. It is the exact answer to a maximisation over all distributions with a stated mean and variance, and the polynomial that proves nothing beats it is the certificate a search of that kind always produces.

 What one input can do, over 1024 cases. A table of functions of several inputs with the largest effect any single input has on each, the bound that effect implies, and the true tail probability — computed by enumerating every input. Probability

No single input can move it far

Independence was never the hypothesis doing the work. A quantity built from many separately drawn inputs concentrates whenever changing one of them moves it only a little — and that covers quantities which are not sums of anything and have no formula at all.

 Reducing abcabc to a standard form. The gluing word abcabc rewritten step by step into one of the classification's standard forms, with the move used and the two invariants recomputed at each step. Topology

Every word driven to a normal form

The classification is usually met as a statement: two numbers name the surface. The proof is a procedure — a short list of cut-and-reglue moves that drive any gluing word to one of the standard forms, with a measure that never rises to say why the procedure stops.

 4 surfaces with an edge, and the three numbers they need. Polygons whose gluing words leave some edges unpaired, each with its Euler characteristic, its sidedness and the number of boundary circles the unpaired edges form. Topology

The third number a surface needs

Leave an edge unpaired in a gluing word and the surface acquires an edge of its own. Two numbers no longer name it — a count of boundary circles is needed as well — and with that third number the list is complete again, every triple occurring exactly once.

 The classical centres as three weights each. A table of triangle centres with the weights on the three corners that produce each, and the determinants that decide which triples of them are collinear. Geometry

A centre is three weights

Write each classical centre as a weighted average of the corners and a coincidence becomes a determinant. The Euler line is then one number rather than a construction, the whole catalogue becomes mechanical, and the reason one centre is missing from it is visible in the weights.

 The smallest algebra that refutes each formula. A table of formulas against the smallest finite Heyting algebra refuting each, found by searching every order on a few points, with the formulas no such algebra refutes marked. Logic

Refutable in something small

A formula that is not a theorem of the constructive system fails in some finite algebra, and the algebra can be found by search. That single property is what makes the propositional logic decidable — and the predicate version loses the property and the decidability with it.

 67 starting points that find all 5 roots. The roots of z⁵ − 1 with a ring of starting points around them, each start marked by which root the method reaches from it, and every root reached by at least one. Dynamics

Covering rather than avoiding

Two arguments say no starting guess is safe: the boundary is fractal and some regions are permanently trapped. The repair is not a better guess. It is a fixed list of starting points, computed from the degree alone, from which every root of every polynomial of that degree is found.

 Who survives with two pebbles and who with three, over 4 rounds. A table of three pairs of graphs with, for each, whether the duplicating player survives a two-pebble game and a three-pebble game played to a fixed depth. Logic

The boundary at three variables

Restrict a sentence to two variable names and it can still be arbitrarily long, because the names are reused. What it cannot be is deep: every satisfiable two-variable sentence has a small model, so asking whether one is satisfiable is a bounded search. Allow a third name and the question becomes undecidable.

 Even and Paz's halving, for 4 people. The recursive halving procedure run on a cake valued differently by 4 people: each round's marks and cuts, and the final pieces, each worth at least a 1/4 share to its owner. 8 marks are made. Applied

How many cuts a fair share costs

Every person can be guaranteed a share of a cake worth at least one n-th by their own measure, and the oldest rule that does it asks about n²/2 questions. Splitting the people into halves and the cake at a median mark asks about n log n — and a theorem says nothing can ask fewer. Fairness has a price, and it can be counted.

 Maximising the product of two people's values. The frontier of value pairs from dividing 4 goods between two people, with the points maximising the product, the sum and the smaller value. The product's maximum is (65.0, 54.2) and is envy-free. Applied

The product that makes a division fair

Divide goods to make the total happiness as large as possible and the result can be monstrously unfair; make the least happy person as happy as possible and it can waste. Multiply the people's values together and maximise the product instead, and something unexpected happens — nobody envies anybody when goods can be split, and nobody envies by more than one item when they cannot.

 The one line from which the nearfield plane looks Desarguesian. A grid of the 91 lines of the nearfield plane of order nine shaded by how many of 40 Desargues configurations with that line as axis failed; only the line at infinity has none, and every other line at least 20. Computation

A plane no field built

Every finite field builds a projective plane, and for a long time every known plane was built that way. The plane over Dickson's nearfield of order nine has ninety-one points, ninety-one lines and every incidence right — and Desargues' theorem fails in it on most configurations tried, except for one line, from which it never fails at all.

 The conic y = x² in the plane of order 7. A 7 by 7 grid of the affine plane over GF(7) with the points of the conic y = x² filled and its point at infinity marked: 8 points, no three collinear. Computation

The curve that no three points in line define

In a finite plane, take as many points as possible with no three on a line. In odd order the largest such sets have one more point than the order — and every one of them, searched exhaustively in the small planes and proved by Segre for all odd orders, is a conic. In even order every tangent meets at one point, which can be added, and the curves stop being forced.

 The Petersen graph, which a five-edge count rules off the plane. The Petersen graph drawn as an outer pentagon, an inner pentagram and five spokes: ten points, fifteen edges, girth five, and more edges than the 13.33 a flat drawing with five-edge faces allows. Discrete

Five spokes squeezed into K5

The Petersen graph has no point with four neighbours, so no stretched copy of K5 can sit inside it. Contract its five spokes and K5 appears anyway. Kuratowski's theorem forbids stretched copies and Wagner's forbids squeezed ones, the two notions disagree on this graph — and they still name exactly the same planar graphs.

 Every stable matching leaves out the same people. 4 stable matchings of a market with short lists, drawn as two columns joined by edges; every one leaves the same letter and number unmatched. Applied

The people every stable answer leaves out

Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.

 The odd ring that forbids a stable pairing. The ranked lists of 6 people and a stable partition of them drawn on a circle: pairs as plain chords, a ring of three or more as arrows from each person to the one they hold. An odd ring is present, as it is in every stable partition of this instance. Applied

A ring that no pairing can break

Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.

 How far a filter spreads a generator's output. Bars for bit depths 1 to 8: the ceiling ⌊24/v⌋ outlined, the raw generator's count of evenly spread consecutive outputs (24, 3, 3, 3, 3, 3, 3, 3), and the tempered count (24, 12, 6, 6, 3, 3, 3, 3). Computation

A filter that changes only the spread

The generator most simulations use passes every output through a last scrambling step before anyone sees it. The step is reversible, it changes nothing about the period, and it cannot make the generator any less predictable. What it changes is which patterns of consecutive outputs can occur at all — on a small twisted generator, from half of them to every one.

 The most edges with no four-cycle. Points for n = 2 to 9: the largest number of edges with no four-cycle, 1, 3, 4, 6, 7, 9, 11, 13, between the counting bound above and ½n^(3/2) below, far under the complete graph's count. Discrete

The densest graph without a square

Forbid four points joined in a cycle and a graph can keep only about ½n^(3/2) of its edges — far fewer than the quarter of all pairs a triangle-free graph keeps. Counting pairs of neighbours proves the ceiling in two lines. What reaches it is not a random graph but a finite geometry: the points of a projective plane, joined when they are orthogonal.

 Every way to pair the edges of a hexagon. Chord diagrams of all 15 pairings of a 6-gon's edges, shaded by the surface each gluing makes: 5 spheres, 10 tori. Topology

Every way to pair a polygon's edges

A hexagon's six edges can be paired in fifteen ways. Glue each pair head to tail and five of the fifteen give a sphere and ten give a torus; an octagon's 105 pairings give 14 spheres, 70 tori and 21 surfaces with two handles. The spheres are exactly the pairings whose chords never cross, and the whole table obeys one recurrence found in 1986.

 The powers of 2 in 1 to 12: one number, 8, stands alone. The whole numbers from 1 to 12, each with a bar whose height is the power of 2 dividing it. A single number has the tallest bar, which is why the harmonic number H(12) has an even denominator and an odd numerator. Analysis

The sum that steps over every whole number

The harmonic sum 1 + 1/2 + 1/3 + … passes 2 at the fourth term, 3 at the eleventh, 4 at the thirty-first, and eventually every whole number there is. It never lands on one. The proof is a single number in the list 1, 2, …, n that carries more factors of two than any other — and the same arithmetic makes the numerators divisible by squares of primes they have no business knowing about.

 The duality theorem's four cases, counted over 6,561 small programs. A three-by-three table crossing the status of a linear program — optimal, unbounded or infeasible — with the status of its dual, counting every small program with coefficients from minus one to one. Five of the nine cells are empty. Applied

When one of the two numbers is missing

The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.

 The midpoint of AB: simplicity 11. A construction drawn step by step — the midpoint of AB, using ruler and compass — with each circle and line numbered in order and Lemoine's count of its operations beneath. Computation

The price of a construction

Three theorems have shown that a compass alone, a straightedge with one circle, and a compass stuck at one opening all reach exactly the points a full set of instruments reaches. None of them said what the journey costs. Émile Lemoine priced every movement of the hand in 1888, and by his count a compass that collapses when lifted — Euclid's — pays twenty-one operations, by Euclid's own method, for what a compass that holds its opening does in four.

 The cyclic square of order 6: no transversal, and one of 5 cells. A Latin square of order 6 with a partial transversal of 5 cells shaded — one cell in each row and column but one, each with a different symbol. No full transversal exists. Computation

One cell short of a transversal

A transversal of a Latin square picks one cell in every row and every column with every symbol different. The cyclic squares of even order have none, and that was settled by a parity argument centuries old. Whether every square of odd order has one is a conjecture from 1967 that nobody has proved; whether every square comes within one cell of having one was settled only in 2023, and only for squares large enough.

All themes