The 36th KOREAN MATHEMATICAL OLYMPIAD Final Round

The answer is $\lceil \frac{2n+2}{3}\rceil$.

For $i=0,1,\dots ,n$, let $y_i=x_i-x_{i+1}$ where $x_0=x_{n+1}=0$. Note that $y_0+y_1+\cdots +y_n=0$. The move in the problem is equivalent to the following. Choose non-negative integers $i$ and $j$ with $0\le i<j\le n$, and replace $y_i$ and $y_j$ by $y_i-1$ and $y_j+1$, respectively. We call this move the $(i,j)$-move. Our goal is to make each $y_i$ a multiple of $3$. Now we prove that for every sequence of integers $y_0,y_1,\dots ,y_n$ with $y_0+y_1+\cdots +y_n=0$, we can make each of $y_i$'s a multiple of $3$ by performing at most $\lceil \frac{2n+2}{3}\rceil$ moves.

We use induction on $n$. One can easily check that it is possible when $n=1,2$. Suppose $n>2$. If $3|y_i$ for some $i$, then we can ignore $y_i$, and so we need at most $\lceil \frac{2n}{3}\rceil$ moves to make all $y_i$'s multiples of $3$. Hence, we may assume that $y_i\ne 0$ for each $i$. We consider the following four cases.

Case 1. There exist $0\le i<j\le n$ such that $y_i\equiv 1(\mathrm{mod}3)$ and $y_j\equiv 2(\mathrm{mod}3)$. Then, we perform the $(i,j)$-move then $y_i$ and $y_j$ become multiples of $3$. So, in this case, we need at most $1+\lceil \frac{2n-2}{3}\rceil \le \lceil \frac{2n+2}{3}\rceil$ moves.

Case 2. There exist $0\le i<j<k\le n$ such that $y_i\equiv y_j\equiv y_k\equiv 1(\mathrm{mod}3)$. Then, we perform the $(i,k)$-move and the $(j,k)$-move. Then, $y_i,y_j$ and $y_k$ become multiples of $3$. So, we need at most $2+\lceil \frac{2n-4}{3}\rceil =\lceil \frac{2n+2}{3}\rceil$ moves.

Case 3. There exist $0\le i<j<k\le n$ such that $y_i\equiv y_j\equiv y_k\equiv 2(\mathrm{mod}3)$. Then, we perform the $(i,j)$-move and the $(i,k)$-move. Then, $y_i,y_j$ and $y_k$ become multiples of $3$. So, we need at most $2+\lceil \frac{2n-4}{3}\rceil =\lceil \frac{2n+2}{3}\rceil$ moves.

Case 4. Neither case 1, case 2 nor case 3 occurs. Since $n\ge 3$, the only possible case is that $n=3$ and $(y_0,y_1,y_2,y_3)\equiv (2,2,1,1)(\mathrm{mod}3)$. In this case, we perform the (0, 1)-move, the (0, 3)-move and the (2, 3)-move. Then, each $y_i$ becomes a multiple of $3$.

Therefore, by the induction, we can make each $y_i$ a multiple of $3$ by performing at most $\lceil \frac{2n+2}{3}\rceil$ moves.

Finally, for the following cases, we need at least $\lceil \frac{2n+2}{3}\rceil$ moves, which implies that the answer is $\lceil \frac{2n+2}{3}\rceil$.

$$(y_0,y_1,\dots ,y_n)=\{\begin{array}{ll}(2,2,\dots ,2,2,2),& \text{if }n\equiv 2(\mathrm{mod}3)\\ (2,2,\dots ,2,2,1),(2,2,\dots ,2,1,2)& \text{if }n\equiv 1(\mathrm{mod}3)\\ (2,2,\dots ,2,1,1),& \text{if }n\equiv 0(\mathrm{mod}3)\end{array}$$