, 2011

The answer: the sum of the numbers has to be a power of $2$, or they are all zeroes. From this moment we assume that the numbers are not all zeroes, otherwise we are done without making any step.

Let $S$ be the sum of the numbers on the blackboard and $D$ be their greatest common divisor at some moment. At the beginning $D$ is equal to $1$, at the end it has to be equal to $S$. We now prove that in each step, $D$ either stays the same or is multiplied by $2$. Indeed, let $k_1, \dots, k_n$ be the numbers on the blackboard, without losing generality let the operation be performed on $(x, y) = (k_1, k_2)$. Then we have that
$$\text{gcd}(k_1, k_2, k_3, \dots, k_n) = \text{gcd}(k_1 - k_2, k_2, k_3, \dots, k_n)$$
and $\text{gcd}(k_1 - k_2, k_2, k_3, \dots, k_n)$ is either $2 \text{gcd}(k_1 - k_2, k_2, k_3, \dots, k_n)$ or $\text{gcd}(k_1 - k_2, k_2, k_3, \dots, k_n)$ (multiplying one of the arguments by $2$ can multiply the greatest common divisor by $2$ if all the other arguments have more twos in their prime factorizations, or make it stay the same otherwise). As at the end $D$ must be equal to $S$, $S$ has to be a power of two.

Now we prove that if $S$ is a power of two, then it is possible to obtain $n-1$ zeroes. Consider binary representations of all the numbers on the blackboard and write them one over another. Let $\ell$ be the index of the rightmost column that does not consist of only zeroes, i.e., $\ell$ is the smallest number such that not for all $i$ $2^\ell \mid k_i$ holds. If $n-1$ numbers are zeroes, then we are already done.

Otherwise, observe that in the $\ell$-th column the number of ones has to be even (as $S$ is a power of $2$, larger than $2^\ell$). Take $k_i \ge k_j$ such that they are not divisible by $2^\ell$ and perform the operation on them. Observe that after doing the operation all the columns with indices lower than $\ell$ still have only zeroes, however in the $\ell$-th column the number of ones decrease by $2$. Doing such operations we can delete ones from columns one after another, obtaining at the end the situation, in which we cannot apply the described rule. This means that $n-1$ numbers on the blackboard are zeroes.