Matpic
mathematics, in pictures
Theme

Decided by exhaustion — page 2

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.
A subgroup of 2, and the 4 blocks it cuts the group into. The 8 symmetries of a 4-gon, split into 4 blocks by composing every element onto the subgroup {e, r²}. The blocks all have 2 elements and no element is in two of them. Algebra

The blocks a subgroup cuts out

Take any part of a group that is closed under composition, and it slices the whole group into blocks of its own size that do not overlap. Everything Lagrange's theorem says is arithmetic about that picture — and whether the blocks can be multiplied is a separate question with a surprising answer.

 five values, unevenly weighted, and the mass outside 3 standard deviations. A distribution drawn as bars, with the windows one and a half, two and three standard deviations wide marked. The probability outside each window is summed and compared with the bound that knows only the variance. Probability

How far from the average a thing can be

Knowing only an average and a spread — nothing about the shape, nothing about the number of outcomes, nothing about symmetry — the chance of landing three standard deviations out is at most one in nine. And there is a distribution that lands there exactly that often, so the bound cannot be improved.

 5,040 orders, 7 thresholds, one best rule. For each number of candidates passed over, the share of the 5,040 possible arrival orders in which the rule ends up with the best of the 7. The count is exhaustive. Probability

When to stop looking

Candidates arrive one at a time in a random order. Each must be accepted or rejected on the spot, with no going back and no way to know what is still to come. The best possible rule is to look at about a third of them and then take the first one that beats everything seen — and it works about a third of the time, however many there are.

 Two graphs that will not lie flat, and one that will. K4, K5 and K3,3 in the best straight-line drawings a search could find. K4 has no crossings; the other two have one each, and Euler's formula shows that none can have none. Discrete

Two graphs that will not lie flat

Five points, every pair joined: no matter how the points are placed or how the lines are drawn, two of the lines cross. The proof is not about drawing at all — it counts edges against faces and finds one edge too many.

 Trisect every angle, and an equilateral triangle appears. A triangle with angles 78°, 54°, 48°, its six angle trisectors, and the triangle whose corners are where the trisectors nearest each side meet. That inner triangle is equilateral, which is Morley's theorem. Geometry

Three trisectors and a triangle nobody expected

Cut every angle of a triangle into three. The trisectors nearest each side meet in three points, and those three points are always the corners of an equilateral triangle — for every triangle there is, with no exceptions and no reason anybody finds obvious.

 The tree of Pythagorean triples. A tree rooted at 3-4-5. Each triple has three children, obtained by three fixed integer matrices, and every primitive triple appears exactly once somewhere in it. Number

A tree that holds every triple

Three fixed matrices, applied to 3-4-5 over and over, produce every primitive Pythagorean triple there is — each of them once, none of them twice, and with no test for common factors anywhere in the procedure.

 x ↦ cos x: two starts, one destination. A map whose graph is nowhere steeper than a fixed factor under one, with staircases from two different starting points converging on the same crossing, and the distance to it falling under a geometric bound. Analysis

A map that shrinks everything

One extra hypothesis — that every distance is shortened by at least a fixed factor — turns the existence of a fixed point into its uniqueness, an algorithm for finding it, and a bound on the error after any number of steps.

 Between every number and its double. The interval from n to twice n, drawn for n up to 26, with the primes inside each marked. Every interval contains at least one. Number

Always one before the double

A density says what happens on average and permits long empty stretches. This says something a density cannot — that the stretch from any number to twice it contains a prime, at every scale, without exception.

 A matching that covers all 5 of one side. A bipartite graph with every possible pairing drawn thin and one complete matching drawn thick, so that each vertex on the left is joined to a distinct vertex on the right. Discrete

One bottleneck and nothing else

A set of jobs can be filled by distinct people unless some group of jobs has too few candidates between them — and that single obstruction is the only one there is, which is what makes the theorem worth having.

 3 rounds on chains of 4 and 5. Two chains of dots with pebbles placed in turn, and the transcript of a play: Spoiler picks an element of one chain, Duplicator answers in the other, and the pebbles must keep the same order. Logic

A game that decides what can be said

Two players take turns pointing at elements of two structures; if the second can survive k rounds, then no sentence with k quantifiers tells the structures apart — a statement about infinitely many formulas, settled by a finite search.

 A resolution refutation of four clauses on three variables. A derivation tree: the given clauses at the top, each later clause obtained by cancelling one variable between two clauses above it, ending in the empty clause. Logic

A proof with one rule

Two clauses that disagree about exactly one variable can be combined into a third that forgets it; repeat, and if the clauses cannot all be true the empty clause eventually appears — a complete proof system with a single move.

 Two coefficient arrays, one with determinant zero and one without. The Sylvester matrices of two pairs of polynomials drawn as grids of coefficients, one pair sharing a root and one not, with each determinant computed in whole numbers and checked against whether a shared root exists. Algebra

A shared root, found without finding it

Two polynomials have a root in common exactly when one determinant built from their coefficients is zero. No root is computed, nothing is approximated, and the same construction turns two equations in two unknowns into one equation in one.

 Every order of arrival for three partners, and what each player adds. A table with one row per order in which the players could arrive, giving what each adds to the group already present, and the average of each column as that player's share. Applied

The order everybody arrives in

Three people jointly earn nine, and the question is what each is owed. Ask instead what each adds on walking into a room the others are already in, average that over every order they could have arrived in, and four modest conditions leave no other answer.

 The splits no group can beat, for three partners. The triangle of ways to split a fixed total between three players, with each coalition's demand drawn as a straight cut across it, and the region surviving every cut shaded. Applied

A split nobody can walk away from

Every way of dividing what a group earns is a point of a triangle, and every coalition's threat to leave cuts a straight line across it. What survives all the cuts is the set of stable divisions — and for one three-player game there is nothing left.

 3 consistent judges, and a majority that is not. A table of judges against three questions, every judge's row internally consistent, with the majority answer to each question underneath forming a combination no judge holds. Applied

The court that contradicts itself

Three judges each answer three questions, and each answers them consistently. Take the majority on each question separately and the answers no longer hang together — the body as a whole asserts a combination no member of it holds, and no rearrangement of the procedure removes the problem.

 256 consecutive pairs from xₙ₊₁ = 137xₙ + 187 mod 256. Consecutive outputs of a linear congruential generator plotted as points of a square, falling on a small family of evenly spaced parallel lines. Computation

The planes a recurrence cannot leave

One multiplication and one addition, taken modulo a fixed number, produce a sequence that passes for random one value at a time. Taken two or three at a time it does not, and the reason is a whole-number relation that pins every point onto one of a small family of parallel lines.

 Which axioms hold on which frames. A table of frames against modal axioms, each cell decided by checking the axiom under every valuation. Logic

The axiom is the shape of the graph

Add one operator meaning necessarily and the choice of which axioms to accept stops being a matter of taste. Each candidate axiom is true of exactly those worlds-and-arrows diagrams whose arrows have a stated property, and a logic is a class of graphs.

 The nine-point grid, and the lines they force. 9 points with all 20 of their connecting lines drawn. The 12 carrying exactly two points are drawn solid and the rest faintly; the count is computed from the coordinates rather than read off the drawing. Geometry

The line with only two points on it

Scatter finitely many points on a page, not all in one line, and draw every line through two or more of them. However cunningly the points are placed, some line ends up carrying exactly two — and the proof is a minimisation with no algebra in it at all.

 The most triangle-free edges on 6 points. A graph on 6 points carrying 9 edges and no triangle, found by examining every graph on those points, with the two sides its edges cross between drawn apart. Discrete

The edge that forces a triangle

A graph on six points can carry nine edges with no three of them closing a triangle. It cannot carry ten. The bound is n²/4, the graphs that achieve it are all the same shape, and both facts fall out of examining every graph there is.

 A largest flow of 5 through two wide ends and a narrow middle. A network with a capacity on every road, the amount a largest flow sends along each, and the cut whose capacity equals that flow's value drawn as a line separating the places. Discrete

The bottleneck is the whole story

However much a network can carry from one place to another, there is a way of cutting it in two whose total capacity is exactly that number. One quantity is a maximum over ways of routing and the other a minimum over ways of severing, and they are never off by even one.

 The widest layer of the subsets of a set of 4. A Hasse diagram of a small order with the widest layer marked, and the largest set of mutually incomparable elements found by examining every subset. Discrete

The widest layer and the longest chain

Order sixteen subsets by inclusion and ask for the largest collection with no two comparable. The answer is the six subsets of size two — the widest layer — and no cleverer collection beats it. Ask instead for the fewest chains covering everything, and the answer is the same number again.

 The quietest loudest complaint in any two of three decide. The triangle of all splits of what a three-player group is worth, with the split minimising the largest excess marked, the average split beside it, and the loudest complaint named. Applied

The objection nobody can make louder

When no split of the winnings survives every group's objection, the core is empty and the question changes — which split makes the loudest objection as quiet as it can be? Sorting the complaints and minimising them in dictionary order picks exactly one split, always, whether or not the core exists.

 17 points coloured by whether their difference is a square. 17 points on a circle with every pair joined, coloured by whether the difference of their labels is a square modulo 17; the largest set of points all joined by one colour has 3 members. Discrete

Eighteen people, and the seventeen that escape

Among any eighteen people, four are mutual acquaintances or four are mutual strangers. Seventeen can be arranged so that neither happens, and the arrangement is not a lucky find — it is a rule about squares.

 Two colours avoid a progression up to 8, and no further. The numbers 1 to 8 in the two colours that avoid three equally spaced numbers in one colour, with the number 9 beside them in both colours and the pattern each choice forces. Discrete

Three in a row on the number line

Colour the numbers one to eight in two colours and it can be arranged that no three equally spaced numbers agree. Add the ninth and it cannot. The structure being forced is arithmetic rather than graphical, and the proof is a different proof.

All themes