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

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 \geq 1$ is an integer and $x-ty \geq 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 $\Phi$. Define nonnegative integers m and r such that x=my+r, with $m \geq 1$ and $0 \leq r < y$.

Lemma 1   Either $\frac{y}{r} < \Phi$ or $\frac{y+r}{y} < \Phi$.

Proof:    If $\frac{y}{r} > \Phi$ then

$$\frac{y+r}{y} = 1+ \frac{r}{y} < 1 + \frac{1}{\Phi} = \Phi.$$

$\fbox{ }$

Lemma 2   If $1 < \frac{x}{y} < \Phi$ then the only possible move is to replace x by x-y. For the resulting pair, $\frac{y}{x-y} > \Phi$.

Proof:    Follows from Lemma 1: we have x=y+r so $\frac{y}{x-y}=\frac{y}{r}>\Phi$ since $\frac{y+r}{y} < \Phi$. $\fbox{ }$

Lemma 3   If $\frac{x}{y}>\Phi$ then the player has a move where the ratio of the resulting numbers is smaller than $\Phi$.

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. $\fbox{ }$

Theorem 1   If r=0 then Player 1 wins. If $\frac{x}{y}>\Phi$ then Player 1 wins. If $1 < \frac{x}{y} < \Phi$ then Player 2 wins.

This material is adapted from Variations on a theme of Euclid by David Collins, in volume 5 of INTEGERS: Electronic Journal of Combinatorial Number Theory, 2005.