SILK ROAD MATHEMATICAL COMPETITION

Answer. $a=\frac{4^n-1}{3}$ for an integer $n>1$ and $a=\frac{2p-1}{3}$, where $p$ is an odd prime number (necessarily having remainder 2 when divided by 3).

We start with describing the set of pairs $(a,b)$ for which Pete can win.

Lemma. (a) If $\gcd (2a+b+1,a-b)>1$, then Pete cannot win. (b) If $\gcd (2a+b+1,a-b)=1$, then Pete can win.

Proof. (a) Set $d=\gcd (2a+b+1,a-b)>1$. Then we have $b=a-(a-b)\equiv a(\mathrm{mod}d)$ and $-(a+b+1)=a-(2a+b+1)\equiv a(\mathrm{mod}d)$. This means that, on each move, all three numbers on the blackboard increased by $a$ modulo $d$ (or, conversely, decreased by $a$ modulo $d$). Hence, if the three numbers written by Basil are not all congruent modulo $d$, then this property will be preserved during Pete's moves, so that they will never be all equal (so they will never become all zero).

(b) Let $x,y,z$ be three numbers on the blackboard at some moment. Then Pete can perform, by several moves, any of the following operations:

1. To yield numbers $x+(a-b)$, $y-(a-b)$, and $z$. For this purpose, he can add $a$ to the first number and $b$ to the second number, and then subtract $a$ from the second number and $b$ from the first one.

2. To yield numbers $x-(2a+b+1)$, $y+(2a+b+1)$, and $z$. For that, he can subtract $a$ from the first number and add $a+b+1$ to the second one, and then subtract $a+b+1$ from the first number and add $a$ to the second one.

3. To yield numbers $x+1$, $y-1$, $z$. Indeed, since $2a+b+1$ and $a-b$ are coprime, there exist positive integers $u$ and $v$ such that $u(a-b)-v(2a+b+1)=1$. Applying operation 1 $u$ times and operation 2 $v$ times, Pete gets the desired situation.

4. Pete can, by one move, either decrease the sum of all numbers by 1 (using the first described move) or increase that sum by 1 (using the second move).

Performing operations 3 and 4, Pete can reach his goal: first, using operation 4, he gets three numbers summing up to zero; then, using operation 3, he makes one number on the blackboard zero, and then another number becomes zero. Since the sum of numbers on the blackboard does not change during these operations, the third number also vanishes at the end. $\square$

Due to the lemma, an odd number $a>1$ satisfies the requirements if and only if the following condition holds:

() For every even $b<a$, the numbers $a-b$ and $2a+b+1$ are coprime.

Notice that $$\gcd (a-b,2a+b+1)=\gcd (a-b,2a+b+1+(a-b))=\gcd (a-b,3a+1).$$ Notice also that the number $a-b$ runs over all odd positive integers smaller than $a$. Therefore, property () is equivalent to the fact that the number $3a+1$ is coprime to any odd positive integer smaller than $a$; or, in other words, that $3a+1$ has no odd divisors smaller than $a$ and greater than $1$ — let us call such divisors bad.

Notice that the number $3a+1$ is even; then $3a+1=2^k\ell$, where $k$ is a positive integer, and $\ell$ is an odd positive integer. If $k\ge 2$ and $\ell >1$, then $\ell \le \frac{3a+1}{4}<a$ is a bad divisor. If $\ell$ is composite, i.e., $\ell ={\ell }_1{\ell }_2$ with ${\ell }_1,{\ell }_2\ge 3$, then ${\ell }_1=\frac{3a+1}{2^k{\ell }_2}\le \frac{3a+1}{6}<a$ is a bad divisor.

The remaining cases are (1) $\ell =1$, and (2) $k=1$ and $\ell$ is a prime number. It is easy to see that, in both cases, $3a+1$ has no bad divisors. Therefore, the desired cases are precisely $3a+1=2^k$ and $3a+1=2p$, where $p$ is a prime. Checking modulo 3 it follows that $k$ is even in the former case, and $\ell$ has a remainder 2 when divided by 3 in the latter. The result follows.