Matpic
mathematics, in pictures
Theme

Decided by exhaustion — page 8

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.
Three places cut apart for 13. A network of eight places with road capacities, three of them lettered, coloured by which of the three sides of the cheapest three-way cut each place falls on, with the cut roads dashed. Discrete

Three places cut apart

Separating two places as cheaply as possible is solved exactly by a flow. Separating three from one another is a different problem: no flow measures it, the pairwise answers do not add up to it, and the best shortcut known in 1994 — cut each place off on its own and throw the dearest cut away — is guaranteed only to within a third of the truth.

 The cheapest way to send 4 units, for 25. A directed network from s to t with a capacity and a price on each road, showing the whole-number flow of 4 units with the least total cost, the arrows thickened by the amount they carry. Discrete

The cheapest way to send

Put a price on every road as well as a capacity and ask for the cheapest way to send four units. Twenty-eight ways exist and one is cheapest, and two certificates prove it without comparing it with the other twenty-seven: no cycle of roads it leaves unused costs less than nothing to push round, and there are prices at the places that every usable road fails to beat.

 Numbers whose divisors add to two, three, four, five and six times themselves. A table of multiperfect numbers with the multiple their divisor sum makes of them, the number itself and its factorisation into prime powers. Number

Divisors that add to three times the number

The divisors of 6 add up to 12, twice 6: a perfect number. The divisors of 120 add up to 360, three times 120, and those of 30,240 to four times it. Numbers like these were a sport for Fermat and Descartes, and they are held together by one fact — the ratio σ(n)/n is a product over the primes, and each prime can add only a little.

 Numbers up to 600 that share their abundancy. A scatter of abundancy against n with horizontal segments joining numbers that have exactly the same abundancy. Number

A ratio nobody else has

Divide the sum of a number's divisors by the number and you get its abundancy: 2 for every perfect number, 12/5 for both 30 and 140. Numbers that share an abundancy are called friends. Some numbers provably have no friend at all, most have friends only far away — and for 10, whose abundancy is 9/5, nobody knows whether a friend exists.

 Three patterns that beat one another in a circle: HHHT, TTHH, HTTH. Three coin-toss patterns at the corners of a triangle with arrows showing which beats which in two-way races, and each pattern's chance of winning when all three race. Probability

Three patterns in a circle

Race three coin patterns at once and the gamblers' accounting still gives each one's chance of arriving first — one fairness equation per pattern. What it does not give is any way to read the three-way result off the two-way ones. HHHT, TTHH and HTTH beat one another in a circle, and HHH loses both its head-to-head races and still finishes ahead of one of the patterns that beat it.

 Several colours on every vertex of a Kneser graph. A grid of Kneser graphs on pairs from five to eight points against the number of colours per vertex, each cell giving the fewest colours needed and the counting lower bound. Topology

Several colours on every vertex

Give every pair from six points three colours, so that pairs with nothing in common share no colour. Counting says nine colours might do; ten are needed. Stahl conjectured in 1976 exactly how many colours every such problem needs — a formula that meets Lovász's topological answer at one colour a vertex and the obvious answer at k — and a search over stars and triangles confirms it in every case small enough to run.

All themes