Matpic
mathematics, in pictures
Theme

Decided by exhaustion — page 1

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.
(p ∨ q) ∧ ¬r, drawn on the cube of 8 assignments. The assignments as corners of a cube, joined when they differ in one variable, with the satisfying corners filled. Logic

A formula is a corner of a cube

A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.

 Post's five classes, and which connectives escape them. A table of connectives against the five closed classes, with the completeness verdict for each. Logic

One connective is enough

Of the sixteen ways to combine two truth values, exactly two can build all the others by themselves. Which two is not obvious, and the reason turns out to be five properties that a connective either has or escapes.

 ((p ∧ q) ∨ (r ∧ s)) ∨ (¬p ∧ ¬r), covered by 3 rectangles. A grid of the assignments arranged so that neighbouring squares differ in one variable. Logic

The map that puts neighbours side by side

Reorder the rows of a truth table so that neighbouring squares differ in one letter, and finding a short formula stops being algebra and becomes the problem of covering a shape with rectangles.

 4 circles, and the 14 patterns they realise. Closed curves overlapping in the plane, with each region of the arrangement identified by which curves contain it. Logic

Four circles cannot do it

Three overlapping circles cut the plane into exactly the eight regions three sets need. Four circles cut it into fourteen, and sixteen are required — so the diagram everyone draws stops working at four, and the reason is a count.

 The 256 syllogistic forms, and the 24 that work. A grid with one cell per syllogistic form, marked according to whether it is valid and what it needs to be valid. Logic

Twenty-four out of two hundred and fifty-six

Aristotle's syllogisms are four sentence forms in four arrangements, which makes 256 patterns of argument. Fifteen of them are valid. Nine more become valid if you assume the things being talked about exist, and the gap between those numbers is a two-thousand-year-old disagreement.

 j is one more than i, counting round — as a grid, with both quantifier readings. A grid of marks for a relation, with the row and column facts the two quantifier orders ask about. Logic

Every row, or one column

For every person there is someone who loves them, and there is someone who loves everyone, are the same six words in a different order. Draw the relation as a grid and they become two obviously different questions — one about rows, one about columns.

 A tree branching at most 3 ways, to depth 4, and the path through it. A tree drawn level by level, with the nodes that die out faint and a highlighted path that always steps to a node with descendants at the bottom. Logic

An infinite tree has an infinite path

A tree that goes on forever, in which every node has only finitely many children, must contain a single branch that goes on forever. The proof is a rule for walking, and the rule is the whole of why finite information can decide an infinite question.

 Two points, and everything one round of compass and straightedge adds. Two starting points with the line and circles they permit, and the four points where those objects cross. Computation

What two points can build

A compass and a straightedge are not a craft. They are two operations on a set of points, applied over and over, and writing them that way turns "can this be drawn?" into a question with an answer.

 Every rational number that could be a root of x³ − 2. A table of the candidate rational roots allowed by the rational root theorem, with the polynomial's exact value at each. Computation

The cube that will not double

Doubling a cube needs an edge in the ratio of the cube root of two. That number satisfies an equation of degree three, three does not divide any power of two, and the oldest open problem in geometry closes in a line.

 Which angles with a rational cosine can be cut in three. A dial of angles marked trisectable or not, beside the cubic whose rational roots decided each one. Computation

The angle that will not divide by three

Halving an angle costs one circle. Cutting it in three means solving a cubic, and for sixty degrees that cubic has no rational root — but plenty of angles do trisect, and which ones is a question with a countable answer.

 Which regular polygons a compass and straightedge can draw, up to 100. A grid of the integers with the constructible ones filled in, each verdict computed two independent ways. Computation

Which polygons can be drawn

Three sides yes, seven no, seventeen yes. The list of constructible regular polygons is neither everything nor almost nothing, and the pattern in it is a fact about which numbers are one less than a power of two.

 The sixteen words of the [7,4] Hamming code. A table of sixteen seven-bit codewords with their data bits, parity bits and weights. Computation

Sixteen spheres that fill a cube

A hundred and twenty-eight seven-bit words, sixteen of them chosen, and a ball of eight around each. Sixteen times eight is a hundred and twenty-eight exactly — so the balls tile the space with nothing left over, and the code wastes nothing at all.

 A schedule on 9 points where every pair meets exactly once. Points around a circle with the triples of a Steiner system drawn between them, beside the list of triples. Computation

A schedule where every pair meets once

Sort n people into groups of three so that every two of them share a group exactly once. Two divisions have to come out whole, that rules out most sizes — and at every size the divisions permit, a schedule exists.

 Transversals of the cyclic square of order 6. A cyclic Latin square with a transversal marked if it has one, beside a count of transversals at neighbouring orders. Computation

The thirty-six officers

Six regiments send six officers each, one of every rank. Arrange all thirty-six in a square so that each row and each column holds every rank once and every regiment once. Euler could not, guessed why, and was wrong about the reason.

 A majority cycle over 3 candidates, and how often 3 voters produce one. The majority tournament as a directed polygon with each arc's margin, beside one cell for every profile of the stated size, filled where no Condorcet winner exists. Applied

The majority that goes in a circle

Every voter hands in a ranking, and a ranking is transitive by construction. Compare the candidates two at a time and let the majority decide each pair, and the verdicts need not fit together into a ranking at all.

 Five rules on one profile of 27 ballots, and 5 different winners. The ballot groups as columns beside a table of five voting rules with the winner each returns and the count that decided it. Applied

Five rules and five winners

Twenty-seven ranked ballots, five entirely reasonable ways of counting them, and five different candidates declared the winner. Every count is correct, every rule is defensible, and the answer turns out to be a property of the rule rather than of the ballots.

 Every ballot one voter could submit under instant runoff. One voter's true ranking beside every ranking that voter could submit instead, with the winner each produces and the profitable misreports marked. Applied

A lie that pays

A ballot is usually read as a report of a preference. This one reads it as a move, and walks every move one voter has — all six rankings, the winner each produces, and the ones that beat honesty.

 Three people, a trimmed piece, and the nine comparisons that settle it. The four stages of the Selfridge–Conway division drawn along a cake, with the full three-by-three matrix of each person's value of each share. Applied

Three people and a trimmed piece

For two people, one cut and one choice deliver a division nobody would swap out of. For three, the same promise costs a trimming, a residue and a choosing order contrived so that an advantage once given cannot be taken back — and the verdict is not three numbers but a whole three-by-three matrix.

 Every allocation of 3 indivisible items, and not one of them envy-free. A value matrix for indivisible goods with the round-robin allocation shaded, the exhaustive counts of envy-free and EF1 allocations, and a control matrix on which envy-free allocations do exist. Applied

Envy-free, up to one item

A cake can be cut anywhere, and every guarantee about fair cutting was bought with that freedom. Take the knife away and the exhaustive search over every allocation of three objects returns nothing envy-free at all — so the subject weakened the word until taking turns was enough to reach it.

 One matching that is not stable, and all 24 counted by blocking pairs. An unstable matching with its blocking pair ringed and both members' rankings marked, above an exhaustive census of every matching of the instance by how many blocking pairs it has. Applied

Nobody has a reason to run away

A matching is stable when no two people on opposite sides would both rather have each other than what they have — a condition that names nothing to build and everything to rule out. The surprise is that something always satisfies it, however perverse the rankings are made.

 Every relabelling of a 4-gon's corners, and the 8 that are motions. All 24 permutations of the corners drawn one by one, with the 8 that preserve every distance marked; the rest deform the polygon and are not symmetries. Algebra

Eight ways to leave a square alone

A square can be picked up and put back so that nothing looks different. There are exactly eight ways to do it, and the number is not asserted here — it is what a search through all twenty-four relabellings of the corners comes back with.

 A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first. Discrete

A walk that changes one thing at a time

Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.

 One line, and both shapes halved. Two shapes and the single straight cut that divides each of them into two equal areas. The direction was found by sweeping every angle and watching the imbalance change sign. Topology

One line that halves them both

Two shapes lying anywhere on a page, of any sizes and any shapes at all. There is always a single straight line that cuts both of them into two equal halves at once — and finding it needs no cleverness, only the observation that a quantity which reverses sign has to pass through zero.

 How many colourings each knot allows. Three knots, and the number of ways their arcs can be coloured with three, five and seven colours under the crossing rule, beside the determinant computed separately from the same crossings. Topology

Colours that count more than three

Three colours prove the trefoil is knotted and say nothing at all about the figure-eight, which refuses them exactly as an unknotted loop does. The repair is to stop colouring and start counting — with five colours, or seven, and with the arithmetic done modulo the number of them.

All themes