Selection Examinations for the IMO, 2015

In each step average value of chosen three numbers will be integer if and only if their sum will be divisible by 3. Therefore it is enough to know only residues of numbers modulo 3. Let us denote with $x_0, x_1$ and $x_2$ how many numbers on board give residue 0, 1 or 2 modulo 3, respectively.
We can present current state on the board with triple of these nonnegative integers $(x_0, x_1, x_2)$. Possible moves in this state are
$$\begin{array}{lcl} (x_0, x_1, x_2) & \rightarrow & (x_0 - 1, x_1 - 1, x_2 - 1), \quad \text{if } x_0, x_1, x_2 \ge 1, \\ (x_0, x_1, x_2) & \rightarrow & (x_0 - 3, x_1, x_2), \quad \text{if } x_0 \ge 3, \\ (x_0, x_1, x_2) & \rightarrow & (x_0, x_1 - 3, x_2), \quad \text{if } x_1 \ge 3, \\ (x_0, x_1, x_2) & \rightarrow & (x_0, x_1, x_2 - 3), \quad \text{if } x_2 \ge 3. \end{array}$$

Because of symmetry of these moves order of integers in triple is not important. Therefore we will present each state rather with ordered triple $(y_0, y_1, y_2)$, where $(y_0, y_1, y_2)$ is a permutation of $(x_0, x_1, x_2)$ with $y_0 \ge y_1 \ge y_2$.
The sum $y_0 + y_1 + y_2$ modulo 3 is invariant after each move. We denote $(\hat{y}_0, \hat{y}_1, \hat{y}_2)$ to be final state of the game where no moves are possible anymore. Because $\hat{y}_0 \ge \hat{y}_1 \ge \hat{y}_2$ it must hold $\hat{y}_2 = 0$ and $2 \ge \hat{y}_0 \ge \hat{y}_1 \ge 0$. With respect to $n$ we have following possibilities:

* $n \equiv 2 \pmod{3}$
Final state $(\hat{y}_0, \hat{y}_1, \hat{y}_2)$ is (2,0,0) or (1,1,0). In either case players had to make $\frac{n-2}{3}$ moves together to reach this state. If this number is even Bine wins else Ana wins. Therefore if $n \equiv 2 \pmod{6}$ Bine wins and if $n \equiv 5 \pmod{6}$ Ana wins.

* $n \equiv 0 \pmod{3}$
At the beginning of game we have $y_0 = y_1 = y_2$ and after each move property $y_0 \equiv y_1 \equiv y_2 \pmod{3}$ is invariant. Therefore final state will be $(\hat{y}_0, \hat{y}_1, \hat{y}_2) = (0,0,0)$. To reach it $\frac{n}{3}$ will have to be played. So if $n \equiv 0 \pmod{6}$ Bine wins and if $n \equiv 3 \pmod{6}$ Ana wins.

• $n \equiv 1 \pmod{6}$
In this case final states are (2,2,0) and (1,0,0). State (2,2,0) can be reached after odd number of moves and therefore is winning for Ana. State (1,0,0) can be reached after even number of moves and therefore is winning for Bine. For $n = 7$ Ana can make first move (3, 2, 2) $\rightarrow$ (2, 2, 0) and wins.
For $n > 7$ we will prove that Bine has winning strategy. There exist two numbers in the triplet such that in each turn they are congruent modulo 3. Bine's strategy is to decrease of these two numbers below 2. If he succeeds it will be also possible to decrease the other number below 2 and therefore final state will be (1,0,0). Starting triple is $(\frac{n-1}{3} + 1, \frac{n-1}{3}, \frac{n-1}{3})$. Bine chooses one of the numbers $\frac{n-1}{3}$ and tries to decrease it below 2 in as few turns as possible. Ana can prevent him to do so only if at the end Bine gets number 2 and Ana in the meantime decreases number $\frac{n-1}{3} + 1$ on 0. Because Bine is decreasing his number in each turn by 3 that can happen only if $\frac{n-1}{3} \equiv 2 \pmod{3}$. That can happen because then $\frac{n-1}{3} + 1 \equiv 0 \pmod{3}$ holds and Ana needs less turns to reach 0 with decreasing by 3. In this case Bine has to adjust his strategy in his penultimate move. For $n > 7$ the state before that move is $(3, 5, \frac{n-1}{3})$. Then Bine must not decrease 5 by 3 but rather decrease all three numbers by 1 to reach state $(2, 4, \frac{n-1}{3} - 1)$. In the next move Ana cannot decrease number 2 to 0 therefore Bine will be able to decrease number 4 below number 2. So Bine can definitely reach state (1,0,0) and win.

• $n \equiv 4 \pmod{6}$
For $n = 4$ Ana makes move (2, 1, 1) $\rightarrow$ (1, 0, 0) and wins. For $n = 10$ Ana makes move (4, 3, 3) $\rightarrow$ (4, 3, 0). Then regardless of the move Bine makes Ana can make another move and again wins by reaching state (1, 0, 0).
For $n > 10$ Ana can in the first move erase biggest three numbers from the board. By that the game transforms into the previous case with $n \equiv 1 \pmod{6}$ and $n > 7$. Now Ana is a second player and she has a winning strategy.

We conclude that Ana wins if $n \equiv 3, 4, 5 \pmod{6}$ and if $n = 7$. Otherwise Bine wins.