## Task 2.

Two natural numbers are written on the board. Two players play a game, taking turns to change the numbers on the board.

If at some point the numbers on the board are $A$ and $B (A \geqslant B)$, the player whose turn it is chooses a natural number $k$ such that $A - kB \geqslant 0$, erases the number $A$, and writes the number $A - kB$ in its place. The player who writes the number 0 on the board wins.

For which values of the ratio of the two initial numbers on the board can the first player always win, regardless of the second player's moves?
## Solution.

Let $\varphi=\frac{1+\sqrt{5}}{2}$, the positive root of $t^{2}-t-1$. The first player can win regardless of the second player's moves if the ratio of the initial numbers in the set is

$$
\left\langle 0, \frac{1}{\varphi}\right\rangle \cup\{1\} \cup\langle\varphi,+\infty\rangle
$$

Let $M$ and $m$ be natural numbers such that $M \geqslant m$. We claim that the player whose turn it is to move wins regardless of the second player's moves if and only if $m=M$ or $M>\varphi m$. The claim is obvious for $m=M$, so assume $m \neq M$.

If $M\varphi(M-m)$. Therefore, it is sufficient to show that a player who receives a pair such that $M>\varphi m$ can win or pass a pair $\left(m^{\prime}, M^{\prime}\right)$ with $m^{\prime}\varphi m$ and $M=q m+r, 0\varphi r$, then he passes $(m, m+r)$, and the other player must return $(m, r)$, which is a winning position. Now assume $q=1$ and he passes $(m, r)$. We claim that $r \neq m\varphi m$, then $(\varphi-1) m<r$, i.e., $m<\varphi r$.

Thus, the first player can either win or pass a pair $\left(m^{\prime}, M^{\prime}\right)$ such that $m^{\prime}<M^{\prime}<\varphi m^{\prime}$ in each move.