Matpic
mathematics, in pictures
Theme

Decided by exhaustion — page 5

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 signal both can see, and neither wants to disobey. A two-by-two game with a distribution over its four cells, drawn as the weight on each. Obeying the recommendation is a best reply for both choosers, and the pair collects 21/2 between them. Applied

A signal both can see

Two choosers who randomise privately can reach a set of outcomes that is smaller, and worse, than the set they reach when a device draws one cell and whispers each of them their half of it. Nothing is enforced and nobody is bound, and the arrangement is stable anyway.

 A landscape nobody is looking at, and every move goes downhill on it. The 8 states of a congestion game with 3 participants and two resources, ordered by Rosenthal's potential, with every improving unilateral move drawn as an arrow. Every arrow points downward. Applied

The landscape nobody is looking at

Letting participants move one at a time to whatever is currently better can cycle forever, and on a network of congestible roads it cannot. The reason is a single number attached to each state that falls by exactly what the mover saves.

 What the chain costs on a 6-gon: 39 pieces. A regular 6-gon fanned into 4 triangles, each with the three cuts that turn it into a rectangle, beside the running count of the pieces the whole chain produces — 39 of them. Computation

Finitely many, and nobody says how many

The theorem promises a dissection exists and the proof produces one. Running the proof on a hexagon produces thirty-nine pieces, ingenuity produces five, and there is no method for proving that five cannot be four.

 One sign decides which curve it is. 3 conics drawn from the general quadratic, each labelled with its discriminant B² − 4AC and the curve that sign names, checked against how many times the curve meets a large circle. Geometry

One sign decides which curve

The general quadratic in two variables has six coefficients and draws a conic. Which of the four it draws is settled by a single combination of three of them, and the other three cannot change the answer however they are chosen.

 58.6% at 46 candidates, against 37% without the values. The chance of ending with the best candidate when the values are shown, against the number of candidates, for 10 sizes. It falls towards 0.5802 rather than towards 1/e. Probability

When the numbers are shown

The secretary rule wins a third of the time and cannot do better, because it is told only who is ahead. Show the actual values and say where they came from, and the same problem is won three times in five — by a standard that falls as the end approaches.

 An online rule taking nine tenths of what an oracle takes. The share of the oracle's expected maximum secured by the best single threshold, and by the threshold at the median of the maximum, for 8 field sizes of independent uniform values. Probability

Half of what an oracle takes

Compare an online rule not against the best it could have done but against a rule that has seen every value in advance. One fixed threshold secures half of what the oracle collects, whatever the distributions are — and there is an example on which half is all there is.

 6 vertices folded to 4, and a graph that decides. The graph built from 3 generator words, folded until no vertex has two edges of one label leaving it. Reading a word from the base vertex decides membership, and 6 words are tested. Topology

Folding a graph until it decides

A subgroup of a free group usually arrives as a list of words, and almost nothing about it is readable from the list. Draw the words as loops, merge every pair of edges with the same label leaving one point, and what is left is a machine that decides membership by reading.

All themes