A golden ratio thirty years early

Willem Abraham Wythoff published his game in 1907. A queen sits on a quarter-infinite chessboard and may move any distance left, any distance down, or any distance diagonally toward the corner. Whoever cannot move — because the queen has reached the corner — loses.

He also published the losing positions, exactly, in closed form. They are the pairs

$$(\lfloor n\varphi \rfloor,\ \lfloor n\varphi^2 \rfloor), \qquad n = 1, 2, 3, \ldots$$

where $\varphi = (1+\sqrt5)/2$ is the golden ratio.

Nothing in the rules of the game contains a continuous quantity, an irrational number, or any geometry beyond a square lattice. The golden ratio has no business being there, and it is.

The older argument, which is about counting #

Wythoff’s derivation does not compute anything about the game position by position. It works like this.

The losing positions, whatever they are, must have a property: no move connects two of them, and from every other position some move reaches one. Suppose they can be listed as pairs $(a_n, b_n)$ with $a_n < b_n$ and $a_n$ increasing. Then two things must hold.

Each $a_n$ is the smallest number not yet used, because if some number $k$ were missing from every pair, the position $(k, k)$ would have a diagonal move to the corner and could not be a loss, so $k$ must appear — and if it appeared as some $b_m$ with $a_m < k$ then… the argument continues in this vein and pins down the pairs completely.

The difference $b_n - a_n$ is exactly $n$. From $(a_n, b_n)$ a diagonal move subtracts the same amount from both, so it preserves the difference; the losing positions must therefore have all differences distinct, and being greedy about it forces $b_n - a_n = n$.

Those two conditions determine the pairs, and Beatty’s theorem turns them into the formula: the two sequences $\lfloor n\alpha \rfloor$ and $\lfloor n\beta \rfloor$ partition the positive integers exactly when $\alpha$ and $\beta$ are irrational with $1/\alpha + 1/\beta = 1$. Requiring $\beta = \alpha + 1$ to make the differences come out right gives $\alpha^2 = \alpha + 1$, which is the defining equation of $\varphi$.

That is where the golden ratio enters: as the solution of a quadratic that a partition condition produced. Not from a spiral, not from a rectangle, not from anything with a shape. The identity $\varphi^2 = \varphi + 1$ is doing all the work, and it arrives here as a constraint the game imposed rather than as a property anybody went looking for.

The partition, checked #

The Beatty claim is a statement about every positive integer, and it is the load-bearing step, so it is checked here rather than cited.

Taking the first ten pairs generates the numbers 1, 3, 4, 6, 8, 9, 11, 12, 14, 16 from the first sequence and 2, 5, 7, 10, 13, 15, 18, 20, 23, 26 from the second. Every integer from 1 to 16 appears exactly once across the two; nothing is duplicated and nothing is missing.

The bound matters and is worth saying why. Coverage is complete only up to the largest member of the slower sequence, which is 16, not up to the largest number generated at all, which is 26 — the partners of 17, 19, 21 and the rest have not been generated yet. Checking to the wrong bound reports a true theorem as broken, which is what happened the first time this check was written.

Why the greedy construction is forced #

The two conditions above look like choices and they are not, and it is worth being precise about that, because “the losing positions are whatever this greedy procedure produces” is unsatisfying until it is clear no other set could have worked.

The set of losing positions of any finite impartial game is determined — it is the set of positions from which every move leads to a win, computed bottom-up — so there is nothing to choose. What the greedy construction does is describe that set, and the description is forced by two facts about the moves.

Every integer must appear as a coordinate of some losing pair. If some $k$ appeared in none, consider the position $(k, k)$: it is a losing position or it is not. It has a diagonal move to the corner, so it is a win; fine. But now consider the smallest such missing $k$ and the position $(k, m)$ for large $m$ — a horizontal move from it can only change $m$, and no choice of $m$ reaches a losing pair with first coordinate $k$, since there is none. So $(k, m)$ is a loss for every large $m$, which contradicts the fact that losing positions have distinct differences.

And the differences must be distinct. Two losing pairs with the same difference lie on one diagonal, and the diagonal move connects them — but no move may connect two losing positions, because then the player facing one could move to the other and hand the loss back.

Those two together leave exactly one candidate set, and the greedy listing produces it. The formula is then a description of that listing rather than an independent claim.

The newer argument, which is about the position #

The Sprague–Grundy machinery answers a different and larger question. It assigns every position a value, not merely a label, and the value says which Nim heap the position is equivalent to inside any sum.

Running it on Wythoff’s game is mechanical: the value of a position is the mex of the values of everything reachable from it. Nothing about φ is involved and nothing about φ comes out. The zeros land where Wythoff said they would — the hero figure checks that they do, over the whole table drawn — and the rest of the table is the extra information the newer method provides.

And here the older method wins #

The interesting comparison is not that both find the zeros. It is what each can say about everything else.

Wythoff’s argument gives a closed form for the losing positions and says nothing about any other position. Ask it whether the position (4, 9) is equivalent to a Nim heap of 3 or of 7 and it has no opinion; it was never about that.

The Grundy table gives a value for every position and has no closed form for any of them. No formula for its entries is known, and no row of it is periodic — which is a claim worth drawing rather than asserting, since periodicity is the one property that would make a table as good as a formula.

The table being unperiodic puts it in the same position as the Grundy sequences that have never settled, and for what may be the same reason.

So there is a question the 1907 argument answers exactly and the 1935 machinery does not answer at all: what are the losing positions, in closed form? And there is a question the newer machinery answers and the older does not: what is this position worth in a sum?

The lesson generalises past this game, and it is the reason this field exists. A more powerful method is more powerful at the question it was built for. It does not inherit the answers of the methods it replaced, and the older answer can outlive the framework that produced it.

The surprise: the game is a sum in disguise, and that is why φ appears #

Here is a way of seeing the golden ratio that makes it slightly less arbitrary, and it is worth the paragraph.

Wythoff’s game is Nim with two heaps, plus one extra move: take the same amount from both. Without the extra move the losing positions are the pairs $(k, k)$ — Bouton’s criterion, or just mirroring. The extra move destroys exactly those, because from $(k,k)$ the diagonal reaches the corner.

So the losing positions have to be re-chosen so that no diagonal connects two of them, which means all their differences must be distinct, which means the $n$-th pair has difference $n$, which is a growth condition. A set of pairs whose differences grow linearly and whose first coordinates take every unused integer is forced to have a density, and the density is forced to be irrational — because a rational one would repeat and produce a coincidence in the differences.

The golden ratio is what an irrational density that is forced to be as far from rational as possible looks like. That is not a proof, and the proof is the Beatty argument above, but it is the reason a reader should not feel the answer came from nowhere.

What the picture cannot show #

The board figures here are finite windows on a quarter-infinite board, and there is one thing no window can convey.

The two rays never fall into step. They leave the corner at slopes $\varphi$ and $\varphi^2$, and because those are irrational the pattern of cold squares never repeats in any direction — not along a row, not along a column, not along a diagonal. A finite picture looks like it might be about to settle into a pattern, and it never will.

That is not a limitation of the drawing so much as the fact the drawing is about, and it is why every claim in this essay about the table is bounded by the range computed while the claim about the formula is not.

There is a second thing the picture hides, and it is more practical. The cells drawn here are small values — 0, 1, 2, 3 — and the table’s values grow without bound as the board does. A reader looking at a 14 × 14 window would reasonably guess the values stay small. They do not, and no window of any size would show otherwise.

A larger window makes the point by not making any: at sixteen squares on a side the picture is the same picture, and two irrational slopes look, at every scale, like they are about to become rational. That is why the section above runs the construction against other constants instead — a wrong constant is caught by one pair landing off a cold square, and no amount of looking at a bigger board catches anything at all.

Where the model stops #

Two limits, and both are about the table rather than the formula.

The table is computed, so it is finite. Every claim made here about the Grundy values holds over the range drawn and is not a claim about the game. That the values have no period is a statement about a search finding none, not about none existing — the same distinction the octal survey is built on.

And the formula’s exactness has a floating-point caveat. $\lfloor n\varphi \rfloor$ for large $n$ is a floor of an irrational multiple, and a double eventually gets one wrong. The values here are small enough that it does not arise, and the agreement check would catch it if it did, because a mis-floored pair would land on a non-zero cell.

Who found it, and when #

There is one more comparison worth making, because it puts the two methods’ costs side by side rather than only their answers.

Deciding whether a given position is cold takes, by the formula, one multiplication and one floor: work independent of the size of the numbers, once the arithmetic is done. Deciding the same thing from the table takes the whole table below that position, which is quadratic in the coordinates. For a position at (10⁶, 1.6 × 10⁶) the formula answers immediately and the table is not going to be built.

Wythoff was a Dutch mathematician; the game appeared in Nieuw Archief voor Wiskunde in 1907. The game is older than his paper — a version of it was played in China as tsyanshidzi, picking stones — and what he contributed is the solution rather than the rules.

Sam Beatty’s theorem, which supplies the partition, dates from 1926: nineteen years after Wythoff used the fact it states. Wythoff proved what he needed directly.

It is also worth noting what Wythoff did not claim. He described the losing positions and did not claim the game was interesting for any other reason, did not connect it to Nim in the modern sense, and had no framework in which “this game is equivalent to that one” would have been a statement. The connection to Nim as a sum — Wythoff’s game being two heaps with a coupling move — is a modern reading of it.

That ordering is a small pleasure and a real point. The tools this argument is now taught with arrived after the argument, and a modern account that presents Wythoff’s result as an application of Beatty’s theorem has the history precisely backwards — which is the sort of inversion this field exists to catch.

What an irrational constant in a finite game means #

A game with finitely many positions at every size cannot have an irrational answer, and it is worth being exact about how one turns up anyway, because the resolution says what the constant is doing.

Every question about a fixed Wythoff position has a finite answer: the position is cold or it is not, and a search settles it. Nothing irrational can appear in any individual verdict. What $\phi$ describes is the asymptotic distribution of the cold positions — where the $n$-th one sits as $n$ grows — and an asymptotic density is exactly the kind of quantity that can be irrational while every term of the sequence is an integer.

That is the general shape and it is worth recognising, because it recurs. A constant appearing in a game’s analysis is nearly always a statement about a sequence of positions rather than about any position, and the sequence is usually generated by a linear recurrence. Linear recurrences have irrational growth rates for algebraic reasons that have nothing to do with games, and the constant is inherited rather than discovered.

So the right reading of “the golden ratio appears in Wythoff’s game” is that the cold positions are generated by a Fibonacci-like recurrence, and $\phi$ is that recurrence’s growth rate. The mystery is entirely in why the recurrence is the one it is, and that question has a combinatorial answer with no irrational number in it.

The habit worth carrying is to ask, of any constant in this subject, what sequence it is the growth rate of. If the answer is the losing positions in size order, the constant is describing them and not explaining them — and the explanation, when it arrives, is usually about digits.

The same shape, elsewhere in the subject #

Wythoff is the clearest case of an older description outliving the framework that replaced it, and it is not the only one.

Bouton’s criterion for Nim is a closed form for the losing positions of a game, found before there were values, and it is still how anybody actually decides a Nim position — nobody computes Grundy values to play Nim. The Sprague–Grundy theorem explains why Bouton’s criterion works and does not improve on it.

Green Hackenbush is the reverse case and is worth the contrast: there the structural principles — fusion, and the colon principle — genuinely replace the search, and the older way of getting the answer was to play it out. Sometimes the newer machinery does inherit and improve the old answers.

What separates the two is whether the question the old method answered is the question the new method was built for. Sprague and Grundy were building a theory of sums, and the losing positions of one game are a by-product of it. Wythoff was building a description of one game’s losing positions, and there is no reason a theory of sums should improve on it.

One number that is worth stating #

The two sequences have densities $1/\varphi \approx 0.618$ and $1/\varphi^2 \approx 0.382$, and those add to exactly 1 — which is the Beatty condition and is what makes them a partition rather than a pair of sequences that happen not to collide in the range anybody checked.

That the condition is an equality rather than an inequality is the reason the result is exact. A pair of sequences whose densities summed to slightly less than one would leave gaps at unpredictable places, and there would be no closed form for the cold positions at all.

Where the ladder goes next #

The wythoff anchor has two rungs to here: the game, and the constant that turns up in its cold positions thirty years before anybody was looking for it.

The rung above changes what the answer is written in, and the change is worth more than a restatement. The digits say which move wins drops the golden-ratio formulas entirely and writes the cold positions in Fibonacci base: the smaller heap ends in an even number of zeros, and the larger is the same numeral shifted up one place.

Two things follow that the closed form does not give. The first is that the condition becomes checkable by inspection rather than by arithmetic on an irrational number — no floating point, no rounding, no question about which side of a boundary a large heap falls on. A rule about digits answers a question about a heap of a trillion, and a rule about $\phi$ answers it only as accurately as the arithmetic is carried out.

The second is that the digits say which move wins, which the formulas do not. A pair of Beatty sequences tells a player whether a position is cold; it does not name the move that reaches the nearest cold position, and the numeral does, because the operation on the digits is visible.

That is the same trade this site keeps finding and it is worth naming here. The golden ratio is the description and the numeral is the mechanism, and a constant that appears in a description is evidence about the description rather than about the game. The reason $\phi$ turns up in Wythoff’s game is that Fibonacci numerals are what the move rule is doing — which is a much less mysterious statement than the one the constant invites.