Stars of Mathematics Competition

We prove that we can obtain two 0-s on the board if and only if $n$ is a power of 3.

As the sum of the numbers written on the board stays the same, we must obtain on the board the numbers $(0,0,3n)$. If $p\ne 3$ is a prime divisor of $n$, then, in the final configuration, all the numbers are divisible by $p$. But if $p\mid 2a-b$, $p\mid 2b-a$ then $p\mid (2(2a-b)+(2b-a))$, i.e., $p\mid 3a$. As $(p,3)=1$, it follows that $p\mid a$ and then $p\mid b$. From the above, we deduce that if in the end all the numbers are divisible by a prime $p\ne 3$, then they were always divisible by that prime. Since \text{g.c.d.}$(n-1,n,n+1)=1$, it follows that one cannot obtain two 0-s on the board if $n$ has prime divisors other than 3.

We are left with the case when $n=3^k$, $k\in \mathbb{N}\cup \{0\}$. For $k=0$, starting from $(0,1,2)$, it is easy to get to $(0,0,3)$. Assume $k\ge 1$. Choosing at the first move $a=n-1$, $b=n+1$, we obtain on the board numbers $n-3$, $n$, $n+3$, all multiples of 3. They can be written as $3(m-1)$, $3m$, $3(m+1)$ and the subsequent moves function as if the numbers written on the board were $m-1$, $m$, $m+1$. (After $j\le k$ moves, on the board will be the numbers $3^k-3^j$, $3^k$, $3^k+3^j$. After move no. $k$ we get $0,3^k,2\cdot 3^k$. Choosing $a=3^k$ and $b=2\cdot 3^k$ we obtain on the board $0,0,3^{k+1}$.

Let us first prove that if $n=3^m$, $m\in \mathbb{N}\cup \{0\}$, then the triple $(n-1,n,n+1)$ is solvable. We prove the statement by induction after $m\ge 0$.

For $m=0$: the triple $(0,1,2)$ is solvable by a single move, choosing $a=1,b=2$.

Assuming the statement to be true for $m$, let us prove it for $m+1$. Having on the board the triple $(3^{m+1}-1,3^{m+1},3^{m+1}+1)$, we choose $a=3^{m+1}-1$ and $b=3^{m+1}+1$ and we get to the triple $(3^{m+1}-3,3^{m+1},3^{m+1}+3)$. According to the remark (*), this triple is solvable because the inductive hypothesis tells us that the triple $(3^m-1,3^m,3^m+1)$ is solvable.

Let us notice that the sum of the numbers written on the board does not change while performing a move. It remains $3n$, which is a multiple of 3. After the first move, all the numbers become equal modulo 3 because $2a-b\equiv -a-b\equiv 2b-a(\mathrm{mod}3)$. If, after the first move, they became all congruent to 1 or 2 mod 3, they will remain that way, so they can not become 0. Thus, it is mandatory that the first move makes all the numbers on the board multiples of 3. Also, if $(a,b,c)$ is solvable, i.e. can be transformed into $(0,0,a+b+c)$ through a succession of moves, then, before the last move, the numbers written on the board have to be 0, $\frac{a+b+c}{3}$ and $\frac{2(a+b+c)}{3}$, which shows that it is necessary to have $3\mid a+b+c$.

If $n=3k+1$, then the last move must be $(3k,3k+1,3k+2)\mapsto (3k,3k,3k+3)$. If $k=0$, we are done ($n=1$ is a power of 3); otherwise, this triple is solvable if and only if $(k,k,k+1)$ is solvable. But this triple is not solvable because the sum $k+k+(k+1)$ is not divisible by 3.

If $n=3k+2$ then the first move must be $(3k+1,3k+2,3k+3)\mapsto (3k,3k+3,3k+3)$. This triple is solvable if and only if $(k,k+1,k+1)$ is solvable. But this triple is not solvable because the sum $k+(k+1)+(k+1)$ is not divisible by 3.

If $n=3k$, the first move must be $(3k-1,3k,3k+1)\mapsto (3k-3,3k,3k+3)$. This second position is solvable if and only if $(k-1,k,k+1)$ is solvable. As $n\ne 0$, there exist $u,v\in \mathbb{N}$ such that $n=3^u\cdot v$, $(v,3)=1$. Repeating this reasoning, after $u$ moves we get to the triple $(v-1,v,v+1)$. We have seen that the only triple of this form that is solvable is $(0,1,2)$, therefore it is necessary for $n$ to be a power of 3.