Croatian Mathematical Olympiad

Let $\phi =\frac{1+\sqrt{5}}{2}$ be the positive root of the quadratic polynomial $t^2-t-1$. The first player can win if the ratio of the starting numbers is in the set $$⟨0,\frac{1}{\phi }⟩\cup \{1\}\cup ⟨\phi ,+\infty ⟩.$$ Let $M$ and $m$ be positive integers such that $M\ge m$. We claim that the player who is next on the turn when $M$ and $m$ are on the board wins if and only if $m=M$ or $M>\phi m$. The claim is clear for $m=M$, so let us assume that $m\ne M$. If $M<\phi m$, then the player who plays next must pass on the pair of numbers $(m,M-m)\ne (m,0)$ and $m>\phi (M-m)$. Hence it is enough to show that the player who plays with a pair such that $M>\phi m$ can either win or pass on a pair $(m^{\prime },M^{\prime })$ with $m^{\prime }<M^{\prime }<\phi m^{\prime }$. The player wins if he plays with the numbers such that $m\mid M$. Let us assume that $M>\phi m$ and $M=qm+r,0<r<m$. If $q\ge 2$, then player may pass on $(m,r)$, as well as on $(m,m+r)$. He will pass on $(m,r)$ if $r<m<\phi r$. Otherwise, if $m>\phi r$, he will pass on $(m,m+r)$, so the other player will pass on $(m,r)$ and we know that with these numbers the player on the turn wins. If $q=1$, the player passes on $(m,r)$. We claim that $r\ne m<\phi r$. Indeed, since $m+r>\phi m$, we have $(\phi -1)m<r$, i.e. $m<\phi r$. Hence, the first player can in each move either win or pass on a pair $(m^{\prime },M^{\prime })$ such that $m^{\prime }<M^{\prime }<\phi m^{\prime }$.