Two Piles, One Golden Ratio

What backward induction reveals about Wythoff’s Nim

Figure 1: One game, one golden ratio, zero coincidence. The image is AI generated.

Mathematics has a habit of surprising you when you least expect it. You sit down with what looks like a simple problem, you follow the logic wherever it goes, and somewhere along the way something beautiful appears that nobody told you to look for. Not because you went searching for it, but because it was already there, waiting.

I first encountered this feeling properly during my first week at AIMS. We played a game in class. Two numbers, two players, a simple rule for how to move. It looked like a toy problem. Something to warm up with but by the end of the class, the golden ratio had shown up uninvited.

The game is called Wythoff’s Nim and it works like this:

Two players start with a pair of non-negative integers, say (m, n). On each turn, a player can do one of three things: subtract any positive integer from m, subtract any positive integer from n, or subtract the same positive integer from both m and n simultaneously. The only constraint is that you cannot subtract more than the number itself, that is you cannot subtract to get a negative number.

The player who reaches (0, 0) wins.

That is the entire ruleset. No hidden complexity, no special cases. Just two numbers and three possible moves.

The natural question is: given any starting position (m, n), is there a winning strategy? And if so, what is it?

To answer that, we need to figure out which positions are winning positions, that is, positions from which, assuming optimal play, the player whose turn it is will always win.

The easiest place to start is (0, 0) itself. The player who reaches (0, 0) wins, so (0, 0) is a winning position by definition. From there, using a both trial and error together with backwards induction, we can determine some other winning positions.

Any position from which a player can move directly to (0, 0) is a losing position for the person who played it, because the next player will immediately win. It is easy to determine that those positions are (s, 0), (0, s), and (s, s) for any positive integer s since you can always subtract s from one side or both sides and land on (0, 0).

So the first winning position is (0, 0), and everything of the form (s, 0), (0, s), or (s, s) is a losing position for the player who just played.

Now we look for the next winning position. It has to be a position that cannot reach any previous winning position, in this case (0, 0), in one move. The smallest candidate, after ruling out all the losing positions above, is (1, 2).

From (1, 2), every possible move leads to a losing position for the opponent as illustrated in the table below:

Table 1: All possible moves from the position (1, 2) and their outcomes. Every move leads to a losing position for the opponent, confirming that (1, 2) is a winning position.

Continuing this way, we get the third winning position, then the fourth, and so on. The first ten winning positions turn out to be:

(0, 0), (1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18), (12, 20), (14, 23)

Look at those numbers for a moment. Do you notice anything? Can you observe any patterns?

A few things jump out immediately.

First look at the differences between the pairs of numbers.

(0, 0): 0, (1, 2): 1, (3, 5): 2, (4, 7): 3 …

Keep going and the differences climb one at a time, 0 through 9, in order, no gaps, no repeats.

Get sandoh’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Second, notice how each pair is actually built. The smaller number is simply the next nonnegative integer that has not yet been used. The larger number is that same integer plus the next difference in line. Starting from (0, 0), the next unused integer is 1, and the next difference is 1, giving (1, 2) as the next winning position. From (1, 2), the next unused integer is 3, and the next difference is 2, giving (3, 5). Following this rule generates the rest of the list.

By hand, this is manageable for ten pairs. It quickly becomes tedious for a hundred. The rule already found, take the next unused integer, then add the next difference, turns directly into the following code.

def win_pos(n):
    positions = [(0, 0)]
    used_ints = {0}
    for common_diff in range(1, n):
        m = 0
        while m in used_ints:
            m += 1
        y = m + common_diff
        used_ints.add(m)
        used_ints.add(y)
        positions.append((m, y))
    return positions

Calling win_pos(10) reproduces the same ten pairs found by hand. Calling win_pos(100) generates a hundred of them in a fraction of a second, far more than anyone would want to compute by hand, and exactly enough to see what these positions actually look like.

Figure 3: Plot of winning positions (m, n) in blue and their mirror image (n, m) in orange.

Another less obvious pattern appears in the geometry of the points. If we step back and treat each winning pair simply as a point in the plane, something subtle begins to happen: the sequence stops looking like a list of isolated points and starts behaving like it is tracing a direction, slowly aligning itself along a line.

A natural question to ask about these alignments is what their slope might be. Since these winning positions do not form a continuous line, we cannot compute a slope in the usual geometric sense from any fixed pair of points. Instead, we compare pairs of points at increasing scales and examine how the ratio between their coordinates behaves as the sequence grows.

Plotting the ratio n/m for each winning position, and skipping (0, 0) to avoid dividing by zero, we notice something almost immediately. (1, 2) gives a ratio of 2. (3, 5) gives 1.667. (4, 7) gives 1.75. (6, 10) gives 1.667 again. (8, 13) gives 1.625. (11, 18) gives 1.636. (12, 20) gives 1.667. (14, 23) gives 1.643.

At first glance, these numbers look almost arbitrary, jumping up, dropping back down, never quite settling. But look again, and they are all hovering in a tight band, never straying far from something close to 1.618. That is not an accident of these particular ten points. It is a consequence of a fact we have already established in Figure 3, which is that the winning positions themselves lie on a straight line. And since a line is completely determined by its slope, we can find that slope directly using a linear fit:

slope, intercept = np.polyfit(x, y, 1)

This returns 1.6180499523215728, matching φ = (1 + √v 5)/2 to the first several digits.

This is the piece that ties the wobbling ratios back together. The quantity n/m for any individual winning position is just the slope of the line connecting that single point to the origin. Because all the winning positions sit on (or extremely close to) one common line through the origin, the slope from the origin to any of them should, in principle, agree with the slope of the line itself. The small differences we saw in the early ratios, 2, then 1.667, then 1.75, are simply the effect of measuring the slope to individual points before the pattern has had enough room to settle down; the underlying line, fit across all 100 points at once, is unambiguous, and its slope is φ.

So the wobble in the pointwise ratios was never really randomness. It was a handful of individual measurements of the slope of a line whose true value, computed properly across the whole dataset, is the golden ratio itself.

Now that we know where the winning positions actually sit, we can describe a genuine winning strategy for any position on the board, not just recognize a winning position when we see one, but know exactly what to do with a losing one.

Take any position (m, n), with m ≤ n without loss of generality (if m > n, just swap them mentally, since the game treats both piles symmetrically). Compute the ratio n/m and compare it to the golden ratio, φ. There are exactly three possibilities:

If n/m > φ, the position sits above the winning line. There are too many tokens on the right relative to the left.

If n/m < 1/φ, the position sits below the winning line. There are too many tokens on the left relative to the right.

If 1/φ < n/m < φ, the position sits between the two lines, neither pile is far enough out of balance to fix with a single-sided move.

Each of these three cases points to a different kind of move, and this is really the heart of the strategy. If you’re above the line (too much on the right), subtract from the right side only, moving straight down until you land on a winning position. If you’re below the line (too much on the left), subtract from the left side only, moving straight across until you land on a winning position. And if you’re caught in between, no single-sided subtraction will do it, you subtract the same amount from both piles at once, moving diagonally toward the winning line until you land exactly on it.

In every one of these three cases, a winning position is always reachable in one move. That is precisely what makes the losing positions losing, whatever position your opponent leaves you in, if it isn’t already a winning position itself, one of these three moves gets you to one. And once you’re on a winning position, the roles reverse: any move your opponent makes will necessarily knock them off the line, back into one of the three categories, handing the advantage straight back to you.

So the entire game, for all its apparent freedom (subtract anything, from either pile, or both), collapses into a single geometric fact. There is one line through the origin with slope φ, one with slope 1/φ, and everything about how to play well is just a question of which side of those two lines you’re standing on.

I first sat with this problem as a warm-up exercise, something to loosen up the room before the real content of the course began. It did not stay a warm-up for long. What started as trial and error on paper, checking which small pairs of numbers led where, turned out to have a straight line hiding underneath it, and that line turned out to have a slope that shows up in sunflower heads and nautilus shells and Renaissance paintings. Nobody built the golden ratio into the rules of Wythoff’s Nim. It was already there, in the only number that could make the bookkeeping of the game consistent with itself, waiting for anyone patient enough to subtract their way toward it.

That, I think, is the real lesson of that first week at AIMS. Mathematics doesn’t always announce when something beautiful is about to happen. Sometimes you just follow a simple rule as far as it goes, and it’s already there, waiting.

Before working through this on my own, I first came across Wythoff’s Nim through a video by Mostly Mental on YouTube, which walks through the same game and its connection to the golden ratio. It’s worth watching alongside this piece, especially if you’d like to see the pattern discovered a second way, watching someone else follow the same rabbit hole is often more illuminating than reading about it after the fact.