Problem 1602

If the numbers chosen from the blackboard are $x$ and $y$, then the number $x+y+\gcd(x,y)$ will be on the blackboard on the next step. If $x$ is chosen together with itself, the number $x+x+\gcd(x,x) = 3x$ will be on the blackboard on the next step. We show that there will be two equal numbers on the blackboard after the second step at latest. Assume that the initial numbers are $n$ and $m$ and the numbers $n+m+\gcd(n,m)$, $3n$ and $3m$ appearing on the first step are all distinct. Choosing number $n+m+\gcd(n,m)$ together with itself, we obtain $3(n+m+\gcd(n,m)) = 3n+3m+3\gcd(n,m)$. Choosing $3n$ and $3m$, we obtain $3n+3m+\gcd(3n,3m)$. As $\gcd(3n,3m) = 3\gcd(n,m)$, the same number will appear twice after the second step.

Let the largest number on the blackboard after step $s$ and the number of numbers on the blackboard after step $s$ be $m(s)$ and $n(s)$, respectively. Obviously $m(s+1) = m(s)+m(s)+\gcd(m(s),m(s)) = 3m(s)$, as $x \le m(s)$ and $y \le m(s)$ imply $\gcd(x,y) \le m(s)$. Thus $m(s) = 3^s m(0)$ for all $s$. Suppose that there will never be equal numbers on the blackboard. Then $n(s+1) = \frac{n(s)(n(s)+1)}{2} > \frac{n(s)^2}{2}$ for every $s$. Since $n(0) = 2$, we get $n(1) = 3$ and $n(2) = 6$. An easy induction shows that $n(s) > 2 \cdot 3^{2^{s-2}}$ for every $s \ge 2$. Thus $\frac{n(s)}{m(s)} > \frac{2}{m(0)} \cdot 3^{2^{s-2}-s}$. If $s \to \infty$, the number $3^{2^{s-2}-s}$ becomes larger than $\frac{m(0)}{2}$, so $n(s) > m(s)$. On the other hand, $n(s) \le m(s)$ since the numbers are positive, a contradiction.