The player who meets the first long run

The oldest algorithm, drawn as a tiling showed Euclid’s algorithm as a rectangle eaten by squares: cut off the largest square that fits, then the largest that fits in what is left, and keep going. The squares come in runs — several equal ones in a row before the size changes — and a fraction that never closes showed that the list of run lengths is the continued fraction of the rectangle’s ratio.

In 1969 A. J. Cole and A. J. T. Davie made the tiling into a game. Two players take turns. On each turn a player cuts off one or more squares from the current run — never from a later one, and never none — and the player who cuts off the last square of the whole rectangle wins. Equivalently, start with two whole numbers; a move subtracts any positive multiple of the smaller from the larger, provided the result is not negative; and the player who produces a zero wins.

The game looks as though it might require cleverness at every step. It does not. It is decided by the first run whose length is more than one — and the ratio of the rectangle’s sides says in advance who will meet it.

A run of one is a forced move #

Start with the simplest kind of position. If the current run has length 1 — the smaller side fits into the larger only once — then the player to move has exactly one choice: cut off that single square. There is nothing to decide, and the turn passes with the next run.

The 34 × 21 rectangle is made entirely of such runs until the very end. $34 = 21 + 13$, $21 = 13 + 8$, and so on down the Fibonacci numbers, until the last rectangle, 2 × 1, which holds a run of two squares. Every move before that is forced. The first player cuts the 21-square, the second the 13-square, the first the 8, the second the 5, the first the 3, the second the 2, and the first player arrives at the final 2 × 1 rectangle — and cuts off both squares, winning.

So on this rectangle the game is a count of runs. Seven runs, the players alternating, the odd-numbered runs falling to the first player, and the seventh being the last. Nobody chose anything. Remove one Fibonacci step — play on 21 × 13 — and there are six runs, the last falls to the second player, and the verdict flips.

That already says something unexpected: the winner of 34 × 21 and the winner of 21 × 13 are different people, although the rectangles look almost identical. Their ratios are $1.6190$ and $1.6154$, and the golden ratio $\varphi = 1.6180\ldots$ sits between them.

A long run is a choice of parity #

The interesting positions are the ones with a run of two or more squares that is not the last run. Facing such a run, a player can cut off all of it, handing the opponent the next run, or all but one, forcing the opponent to cut off the last square of this run and then face the next run themselves. Those two options differ in exactly one thing: who faces the rest of the rectangle.

That is a complete strategy. Whatever the rest of the rectangle holds, it is a win for whoever faces it or a win for whoever does not, and the player at a long run can choose which of those to be. The player who first meets a run longer than one wins, by choosing the parity that suits them, and every later run is merely played out.

The game tree from (7, 3) shows the choice in miniature. The first run holds two 3-squares. Cutting off both leaves (1, 3), a rectangle of three 1-squares in a single final run, which the opponent clears at once. Cutting off one leaves (4, 3), where the opponent faces a run of length 1, must cut the 3-square, and hands back (3, 1) — the final run, cleared by the first player. The tree has eighteen positions in it, counting the eight finishes, and the whole of the reasoning is the choice at the root.

This is backward induction in its plainest form: solve the end first, then the positions one move before it, and so on up to the start. When to stop looking uses the same reasoning to find the best time to accept an offer, working back from the last candidate to the first. Here there is no chance at all, and Zermelo’s observation applies in its strongest form: a finite game with perfect information and no chance has every position decided in advance — won by the player to move or lost by them — and the only question is how to find out which.

On 55 × 21 the first run has two 21-squares, so the decision comes on the very first move. Cutting off both leaves 21 × 13, the six-run Fibonacci rectangle, which is a loss for whoever faces it — so that is the right move, and the second player spends the rest of the game making forced moves towards defeat. The whole game is visible from the tiling: find the first long run, see who meets it, and that player has won.

Where the golden ratio comes in #

The run rule is complete, but it does not look like a rule about sizes. The surprise is that it is one. The player to move wins exactly when the larger number is more than $\varphi$ times the smaller, or the two are equal.

The reason is the continued fraction of $\varphi$ itself. The golden rectangle is the rectangle whose runs all have length one, forever — $\varphi = [1; 1, 1, 1, \ldots]$, the expansion the rectangle that eats itself computes by cutting off one square and finding the same shape left over. A rectangle whose ratio is close to $\varphi$ agrees with it for a while — a run of one, then another, then another — and the first place it disagrees is its first long run.

Comparing a number with $\varphi$ is therefore the same as finding where its continued fraction first stops being all ones, and continued fractions compare in a simple alternating way. Making the first term larger makes the number larger; making the second term larger makes it smaller, because the second term sits in a denominator; the third is in a denominator of a denominator, and makes it larger again. So a ratio whose first long run is the first, third or fifth run is above $\varphi$, and one whose first long run is the second, fourth or sixth is below it.

And the players alternate in exactly the same way. The first run falls to the first player, the second run to the second, the third to the first. The parity that decides whether the ratio is above $\varphi$ is the parity that decides who meets the first long run. Two alternations, one in the arithmetic of continued fractions and one in the turn order of a game, turn out to be the same alternation.

The argument can also be run directly, without continued fractions. If the ratio $x = a/b$ is below $\varphi$ but above 1, the only move is to $(b, a - b)$, whose ratio is $1/(x - 1)$ — and $x < \varphi$ forces $1/(x - 1) > 1/(\varphi - 1) = \varphi$. So a position below $\varphi$ can only move to a position above it. And a position above $\varphi$ can always move below: its two options, taking all of the run or all but one, land on ratios on opposite sides of $\varphi$, since one is the other’s image under $x \mapsto 1/(x - 1)$. The positions below $\varphi$ are the losing ones, and the golden ratio is where the map $x \mapsto 1/(x-1)$ has its fixed point.

Every position up to forty, by exhaustion #

The two arguments above are proofs, but the claim they prove is sharp enough to be worth checking on every case in a range. The grid solves all 1,600 starting positions with both numbers from 1 to 40, each by searching its game tree to the end — a position is a win if some move reaches zero or reaches a position already known to be a loss — and colours the losses.

The losses form a wedge through the origin, bounded by two straight lines of slope $\varphi$ and $1/\varphi$, with the diagonal cut out of the middle: on the diagonal $a = b$ the player to move subtracts once and reaches zero. Every one of the 1,600 verdicts agrees with the golden-ratio rule, and every one agrees with the run rule too. Three computations — search, ratio and runs — and one answer, with nothing in the search that knows about $\varphi$ at all.

The wedge’s edges are straight because the rule is homogeneous: doubling both numbers doubles every position in the game and changes nobody’s fortunes, so the verdict depends only on the ratio. Its edges are at $\varphi$ because of the fixed point above. And the boundary is sharp to the last square, which a search could only confirm and could never have suggested.

The grid also answers a question the rule leaves implicit — how often the first player wins. A position chosen at random in a large square lands in the wedge with probability close to the wedge’s share of the right angle — $36.6°$ of $90°$, about 0.41 — and for pairs up to 40 there are 586 losses among 1,600 starts, a little over a third, the edges of the square pulling the share down. The first player wins most games, but not overwhelmingly, and the losses concentrate where the two numbers are close.

Fibonacci positions alternate #

The most delicate positions are those made of consecutive Fibonacci numbers, and the figure lines them up against $\varphi$. Their ratios are the convergents of $\varphi$ — 3/2, 5/3, 8/5, 13/8, … — and convergents of any number alternate from one side of it to the other, closing in. The game’s verdicts alternate with them. From (8, 5) the second player wins; from (13, 8) the first; from (21, 13) the second; from (34, 21) the first.

These are the positions where the game is longest and where nobody has any choice. Every run has length one until the final run of two, the game is a pure count, and the count’s parity is exactly which side of $\varphi$ the ratio falls. They are also the worst case of Euclid’s algorithm itself: Lamé’s theorem says the Fibonacci pairs take the most steps for their size, and a game on them lasts as many turns as the algorithm has steps.

The alternation is a version of the fact how close a fraction can get turns into a theorem: $\varphi$ is the number hardest to approximate by fractions, because its continued fraction never has a large term to make a convergent unusually good. In the game, the same absence of large terms is the absence of choices. A position with a big run is easy to win; a position that tracks $\varphi$ for a long time is a long sequence of forced moves ending in a coin already tossed.

Making the last square a loss changes almost nothing #

A natural variation reverses the goal: whoever cuts off the last square loses. In many games that reversal — the misère version — changes the analysis completely, and in Nim it famously changes the endgame. In Euclid’s game it changes the verdict of exactly one kind of position.

The reason is the run rule again. The player who meets the first long run can still choose the parity of what follows, and that choice does not care what the last square is worth. If the first long run is the final one, of length $q \ge 2$, the normal-play winner clears it and the misère winner cuts off all but one square, forcing the opponent to take the last — the same player wins, by a different move. Only a position with no long run at all is different, and the only such positions are the squares, $a = b$, where the single run has length one: the player to move must cut it off, and wins under the normal rule and loses under the misère one.

Solving every position up to 60 both ways confirms it: the two games give the same verdict everywhere except on the 60 diagonal positions. The goal barely matters; the long run is everything. It is the same lesson as the golden-ratio rule, arrived at from the other end — who wins depends on who controls the parity, and the control is decided by the shape of the rectangle before either player moves.

The walk the game takes also has a second picture. Every fraction, exactly once builds the Stern–Brocot tree, in which every positive fraction has a unique path from the root, a string of lefts and rights. The lengths of the runs of equal turns in that path are the continued fraction terms of the fraction, the last one shortened by one — the same run lengths as the tiling — so a game of Euclid is a walk back up the tree towards $1/1$, and a player facing a long run is standing on a long straight stretch of the path, choosing where to leave it.

A second golden game, for a different reason #

The golden ratio turns up in another classical subtraction game, and the resemblance is worth one warning. In Wythoff’s game, published in 1907, there are two piles of counters, and a move removes any number from one pile or the same number from both. The losing positions are the pairs $(\lfloor n\varphi \rfloor, \lfloor n\varphi^2 \rfloor)$ — $(1, 2)$, $(3, 5)$, $(4, 7)$, $(6, 10)$, $(8, 13)$ and so on — and their ratios tend to $\varphi$ as well.

The two games are different and so are the reasons. Wythoff’s losing positions are sparse, one for each $n$, and they come from a partition of the whole numbers into two complementary sequences whose densities add to one — Beatty’s theorem, with $1/\varphi + 1/\varphi^2 = 1$. Euclid’s losing positions fill a wedge of positive angle. In Euclid’s game $\varphi$ enters through its continued fraction and the fixed point of a map; in Wythoff’s it enters through a density equation. The same constant, reached by two unrelated routes, is a reason to check a second argument before trusting a resemblance — which is also what the rectangle that eats itself ends up saying about the golden ratio’s many other appearances.

What the tiling and the grid cannot show #

The grid stops at 40. The rule is proved for every position, and the grid is a check on the proof over 1,600 cases. It is not evidence for anything the proof does not already say, and a claim that looked true on a grid of 40 and failed at 41 would not be caught by it.

The tiling shows one line of play. The figures for 34 × 21 and 55 × 21 colour the runs by who faces them when the winner plays correctly; the loser’s alternatives are not drawn. The game tree draws every alternative, and does it only for a start as small as (7, 3), where it already has twelve positions and eight lines of play. For a start like (55, 21), with a long first run, the tree is too large to be worth drawing, and the rule makes it unnecessary.

And a win is not a margin. The rule says who wins; it says nothing about how many turns the winner needs, nor about which of several winning moves is quickest. Those are separate questions, with separate answers, and a player who knows only the rule can win slowly.

Still open: the cousin with no formula #

For Euclid’s game even the finer structure is known. Every position of a game like this has a Grundy value, a whole number that says how the position behaves when several games are played side by side and a move is made in any one of them. The losing positions are exactly those with value 0, so the golden-ratio rule is the first layer of the Grundy function. Gabriel Nivasch found the whole function for Euclid’s game in 2006, so every position’s behaviour in a sum of games is known, not only who wins it alone.

For Wythoff’s game nothing like it is known. Its losing positions have had an explicit formula since 1907, but its Grundy function has no known formula. Its rows are known to become periodic after a while, with a period that shifts the values upward, and computations of millions of values show patterns without explaining them. Two games, one constant, and for one of them a complete theory and for the other an open problem, which is a good measure of how far the shared constant is from being a shared reason.

A game that is an algorithm with the choices made visible #

Euclid’s algorithm makes no choices. Its game version lets a player take any part of a run, and the only choices that matter are made at runs longer than one. Where the algorithm peels a run in one division, the game asks who peels its last square, and that question has an answer the algorithm computes without being asked: the first long run, found by the first term of the continued fraction that is not 1.

When a game is built on a deterministic process, look for the places where the process could have gone either way. Here there is only one kind of place — a run longer than one — and whoever reaches it first owns the game. The golden ratio is simply the name for the number with no such places at all.

That also explains why the golden ratio keeps being the extreme case elsewhere. A turn by $\varphi$ of a circle spreads its points the most evenly of any angle, the property behind three gaps and no more; its convergents approximate it the worst; its rectangle takes Euclid’s algorithm the longest. Each of those is a statement that the continued fraction has no large term anywhere, and in the game the same statement reads: nobody ever gets a choice, so the outcome is fixed by counting. A number whose expansion is all ones is a number with no decisions in it.