THE ART AND SCIENCE OF MATHEMATICS Wednesday, November 30, 2011

Winning the Euclidean Game

The Game of Euclid:

This is a game played by two people. Beginning with two positive integers, the players alternate turns making moves of the following type:

A player can move from the pair of positive integers {x,y} to any of the pairs {x-ty,y} where t ≥ 1 is an integer and x-ty ≥ 0. Thus, you can subtract any multiple of the smaller number from the larger number, provided you still have two nonnegative numbers.

The winner is the one that first makes one element zero.

The question of who wins depends on the ratio x∕y and the golden ratio Φ. Define nonnegative integers m and r such that x = my + r, with m ≥ 1 and 0 ≤ r < y.

Lemma 1 Either y r < Φ or y+r y < Φ, but not both.

Proof: If y r > Φ then

y +-r-= 1 + r-< 1 + 1-= Φ. y y Φ

Similarly, if y r < Φ then

y +-r-= 1 + r-> 1 + 1-= Φ. y y Φ


Lemma 2 If 1 < x y < Φ then the only possible move is to replace x by x - y. For the resulting pair, -y-- x-y > Φ.

Proof: Follows from Lemma 1: we have x = y + r so -y-- x- y = y r > Φ since y+r y < Φ.

Lemma 3 If xy > Φ and r > 0 then the player has a move where the ratio of the resulting numbers is smaller than Φ and greater than one.

Proof: If m = 1 then leaving y and x - y = r satisfies the conclusion.

If m > 1 then leaving y and r or leaving y and y + r are both valid moves. The conclusion follows from Lemma 1.

Theorem 1 If r = 0 then Player 1 wins. If xy > Φ then Player 1 wins. If 1 < xy < Φ then Player 2 wins.