USAMO

If two of the $a_i$ vanish, say $a_2$ and $a_3$, then $r_1$ must be zero and we are done. Assume at most one $a_i$ vanishes. If any one $a_i$ vanishes, say $a_3$, then $r_2/r_1 = -a_1/a_2$ is a nonnegative rational number. Write this number in lowest terms as $p/q$, and put $r = r_2/p = r_1/q$. We can then write $r_1 = q r$ and $r_2 = p r$. Performing the Euclidean algorithm on $r_1$ and $r_2$ will ultimately leave $r$ and $0$ on the blackboard. Thus we are done again.

Thus it suffices to consider the case where none of the $a_i$ vanishes. We may also assume none of the $r_i$ vanishes, as otherwise there is nothing to check. In this case we will show that we can perform an operation to obtain $r'_1$, $r'_2$, $r'_3$ for which either one of $r'_1$, $r'_2$, $r'_3$ vanishes, or there exist integers $a'_1$, $a'_2$, $a'_3$, not all zero, with $a'_1 r'_1 + a'_2 r'_2 + a'_3 r'_3 = 0$ and
$$|a'_1| + |a'_2| + |a'_3| < |a_1| + |a_2| + |a_3|.$$
After finitely many steps we must arrive at a case where one of the $a_i$ vanishes, in which case we finish as above.

If two of the $r_i$ are equal, then we are immediately done by choosing them as $x$ and $y$. Hence we may suppose $0 < r_1, r_2 < r_3$. Since we are free to negate all the $a_i$, we may assume $a_3 > 0$. Then either $a_1 < -\frac{1}{2} a_3$ or $a_2 < -\frac{1}{2} a_3$ (otherwise $a_1 r_1 + a_2 r_2 + a_3 r_3 > (a_1 + \frac{1}{2} a_3) r_1 + (a_2 + \frac{1}{2} a_3) r_2 > 0$). Without loss of generality, we may assume $a_1 < -\frac{1}{2} a_3$. Then choosing $x = r_1$ and $y = r_3$ gives the triple $(r'_1, r'_2, r'_3) = (r_1, r_2, r_3 - r_1)$ and $(a'_1, a'_2, a'_3) = (a_1 + a_3, a_2, a_3)$. Since $a_1 < a_1 + a_3 < \frac{1}{2} a_3 < -a_1$, we have $|a'_1| = |a_1 + a_3| < |a_1|$ and hence this operation has the desired effect.