= Euclid game
{c}
A <Euclid game> is an <impartial game> based on subtraction steps of the <Euclidean algorithm>.<A Game Based on the Euclidean Algorithm and a Winning Strategy for It by A. J. Cole and A. J. T. Davie>[Original paper introducing Euclid; terminal convention is specified explicitly below]{ref} Here use the following <normal-play convention>: a position is an ordered pair $0\le a\le b$; if $a>0$, remove a positive multiple $ka\le b$ from $b$ and reorder. A position with $a=0$ has no legal move and is losing. Thus moving to a zero coordinate wins; variants that instead stop at equal positive coordinates require a different endpoint convention.
The sum of the coordinates strictly decreases, so every play terminates. If $a$ divides $b$, subtract $b$ and win immediately. If $a<b<2a$, there is only one move, to $(b-a,a)$, so the position has the opposite winning status from that successor.
If $b=qa+r$ with $q\ge2$ and $0<r<a$, two legal choices leave $(r,a)$ or $(a,a+r)$. The latter has exactly one move, to the former, so exactly one of these two successors is losing. Choose it. For example, $(2,3)$ is losing because its only move reaches $(1,2)$, where the opponent takes the whole larger coordinate. From $(2,5)$, subtract $2$ to leave that losing position. These cases give a recursive strategy without exploring every subtraction amount.
Back to article page
