Euclid’s Game

One of the most fundamental algorithms in mathematics is the Euclidean Algorithm to compute (among other things) the greatest common divisor of two numbers. 

Euclid’s Game is a two person strategy game, invented by Cole and Davie in 1969, employing this algorithm, and, maybe not surprisingly, connected to the Golden Ratio. It is played with a pair of positive integers, like (11,27). A move consists of taking away from one number a non-zero multiple of the other number, so that the result is still non-negative.

 

So from (11,27), we can move to either (11,16) or to (11,5).
The players take turns until one number becomes zero, so that the other player is out of moves and has lost.

Here is a complete sample game:

(11,27)➔(11,5)➔(1,5)➔(1,3)➔(1,0)

Below is a way to visualize the possible moves by placing a blue pair (a,b) in a coordinate grid. If a<b, the possible yellow moves are obtained by decreasing the x-coordinate by a, until we get below the x-axis.

Euclid2 moves

We would like to find out when the first player has a winning strategy.

Here is a simple case: If one number is a multiple of the other, the first player can reduce the larger number to 0 and win in a single move. In particular, all pairs (a,a) are a win for the first player. By symmetry, we can from now on restrict our attention to the case that a<b.

How many different moves are possible for the pair (a,b)? We can list the moves (using the floor notation [x] for the largest integer less than or equal to x) as

(a,b-a), (a,b-2a), … , (a,b-[b/a] a),

so there are [b/a] possible moves. You can check this in the diagram above, too.

In many games, it is a good strategy to force the other player’s moves, and this turns out to be the case here as well. The first player should try to reach a pair (a’,b’) with 1< b’/ a’ <2, so that the second player has only one move left.

We will now prove:

Theorem: The first player has a winning strategy if and only if b/a is an integer, or b/a>𝜑, where 𝜑=(√5+1/2) ≈ 1.6180<2 is the Golden Ratio.
In the first case, the player wins by making the larger number 0, in the second case by moving to a position (a’,b’) where 1<b’/a'<2.

Below is a diagram showing all winning pairs (a,b) for the first player with a,b<30 in green. 

Euclid2 30

We first pin down the role of the Golden Ratio.

Lemma: If 1<b/a<𝜑, there is only one move from (a,b), namely to (a’,b’)=(b-a,a), and we have b’/a’>𝜑.

Proof:
We have

Frac a b = frac
so that

Frac b a > fra
In other words, if we can move the other player into the region 1<b/a<𝜑, they are forced to move us back into the claimed winning region b’/a’ >𝜑.

The next lemma tells us when that is possible:

Lemma: Let k be a positive integer.
If k<𝜑+k-1<b/a<k+1, we can move to (a’,b’) = (b-k a, a), and this pair satisfies 1<b’/a'<𝜑. In other words, we subtract the largest amount we are allowed to.

Proof:
We have
Phi 1< frac a b
Taking reciprocals proves the claim.

We will now take care of the remaining possible ratios. Here, we take away one times less than would be allowed:

Lemma: Let k be a positive integer.
If k+1<b/a<𝜑+k, we can move to (a’,b’) = (a, b-k a). From there, only one move is possible, namely to (a”,b”) = (b-(k+1)a, a), and this pair satisfies b”/a”>𝜑.

Proof:
That the chosen move to (a, b-k a) is valid is clear, because the assumptions imply that a<b-ka. Moreover,

Frac b a = fra 1
so there is only one move possible, namely to (a”,b”) = (b-(k+1)a, a). Now we have

Frac a b = f
which proves that a”<b” and that b”/a”>𝜑.

The proof of the theorem now follows by combining the three lemmas.

Euclid3 20b

Life gets more complicated in three dimensions. One can play this game also with triples, allowing to subtract multiples of one number from either of the other two. Above is the set of winning triples in the first octant, marked with small green dots, while the losing positions are big and red. One can see they form a tetrahedral cone, but the cone is not solid, meaning that it probably won’t be as easy to find a simple winning strategy. As an impartial game, Euclid is equivalent to the game of of Nim in any dimension, it’s just not so clear, what the size of the Nim pile is.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s