Matpic
mathematics, in pictures
Concept

Strategy

A rule telling a player what to do at every position that can arise, rather than a single good move. A winning strategy is one that leads to a win against every opposing play, so exhibiting one settles a game outright.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

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.

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.

logic · Ehrenfeucht–Fraïssé games Three properties that leave the middle, and one that cannot. Four measured curves of the share of random graphs having a property, plotted against the number of points: three first-order properties running to zero or one, and the parity of the edge count sitting on a half throughout.

Nearly always, or nearly never

Toss a coin for every pair of points and ask whether the graph that results has some property. For a property a first-order sentence can state, the answer in the limit is never a genuine probability — it is zero or it is one, and the game is what proves it.

logic · Ehrenfeucht–Fraïssé games What a sentence of depth 2 can reach. Two rings of points, of 14 and 19 points, each with a run of 9 consecutive points marked as the neighbourhood a sentence of depth 2 can inspect.

The distance a sentence can see

A first-order sentence with three quantifiers cannot notice anything about a graph beyond a fixed distance from the points it names. That single limitation is why it cannot say connected, and why the failure survives every attempt to add more quantifiers.

logic · Ehrenfeucht–Fraïssé games Euclid's game on 34 and 21. A 34 by 21 rectangle tiled by the squares of Euclid's algorithm, each run of equal squares shaded by the player who faces it, with the deciding run outlined.

The player who meets the first long run

Turn Euclid's algorithm into a game: two players take turns cutting squares off the rectangle, any number from the current run, and whoever cuts the last one wins. The whole game is decided before it starts — by whether the ratio of the sides is more or less than the golden ratio, which is the same thing as how many runs of length one come first.

geometry · Euclidean algorithm

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchElementary equivalenceExpressive powerQuantifierAsymptoticBackward inductionConnectivityContinued fractionsDecision procedureEuclidean algorithmFibonacciGolden ratio

All concepts