Mathematical Olympiad Rioplatense

Player $A$ has a winning strategy if $n$ is $0$ or $-1$ modulo $4$, otherwise $B$ has one.

Putting the stone on a number can be viewed as subtracting $1$ from it. We may assume that $B$ chooses a number in $A$'s arrangement and subtracts $1$ from it; then $A$ must subtract $1$ from an adjacent number etc. Operating on a number (subtracting $1$) is allowed only if the number is positive. Note that each player always moves at positions with the same parity.

Let $a_1, \dots, a_n$ be an arrangement of $n$ nonnegative integers, not necessarily distinct. We call it balanced if there exist nonnegative integers $x_0, x_1, \dots, x_n$ such that
$$(*) \quad x_0 = x_n = 0 \quad \text{and} \quad a_k = x_{k-1} + x_k \quad \text{for } k = 1, \dots, n.$$

We show that $A$ can win if and only if his initial arrangement is balanced. This applies not only to $1, \dots, n$ but to any given collection of nonnegative integers (zeros and repetitions are allowed).

Suppose that $B$ has a move in a balanced arrangement $a_1, \dots, a_n$, subtracting $1$ from $a_k = x_{k-1} + x_k$. Then $x_{k-1} > 0$ or $x_k > 0$ as the move is possible, say $x_k > 0$. So $A$ is able to respond: he can subtract $1$ from $a_{k+1}$ since $a_{k+1} = x_k + x_{k+1} \ge x_k > 0$. Moreover the resulting arrangement is balanced. Only $a_k$ and $a_{k+1}$ have changed, replaced by $a'_k = x_{k-1} + x'_k$ and $a'_{k+1} = x'_k + x_{k+1}$ with $x'_k = x_k - 1$, and $x'_k \ge 0$ due to $x_k > 0$. Hence if $B$ has a move in a balanced arrangement then $A$ has an answering move leading to a balanced arrangement again. Since the game always terminates, it will be therefore $B$ to end up without a legal move.

Suppose next that $A$'s initial arrangement $a_1, \dots, a_n$ is not balanced. Then $B$ can win by reducing the game to a balanced case like above where he plays the winning rôle. Define
$$x_0 = 0 \quad \text{and} \quad x_k = a_k - x_{k-1} \quad \text{for } k = 1, \dots, n.$$
Set $a_{n+1} = 0$ and observe that $x_k > a_{k+1}$ for some $k = 1, \dots, n$. Indeed let $x_j \le a_{j+1}$ for all $1 \le j \le n-1$. Then $x_1, x_2, \dots, x_n \ge 0$ by the definition of the $x_j$. Now notice that $x_n \ne 0$. Otherwise the equalities $(*)$ would hold with nonnegative $x_j$'s and the arrangement would be balanced. In conclusion $x_n > 0 = a_{n+1}$.

Let $B$ start at the first position $k$ such that $x_k > a_{k+1}$, that is, $a_k > x_{k-1} + a_{k+1}$. Note that $x_j \ge 0$ for $j < k$ by the minimum choice of $k$. Since $a_k \ge x_{k-1} + a_{k+1}$ holds after the opening move, $B$ can play at position $k$ at least $x_{k-1} + a_{k+1}$ more times, regardless of $A$'s moves on $a_{k-1} = x_{k-2} + x_{k-1}$ or $a_{k+1}$. (For $k=1$ assume $a_{k-1} = x_{k-1} = x_{k-2} = 0$.) So let $B$ keep moving at $k$ until $A$ has to move at $k-1$ for the $(x_{k-1} + 1)$st time. Call such a move of $A$ move M. It is forced since $A$ has at most $a_{k+1}$ moves at $k+1$.

Right before move M the first $k-1$ positions are occupied by $a_1, \dots, a_{k-2}, x_{k-2}$ as $a_{k-1} = x_{k-2} + x_{k-1}$ was decreased $x_{k-1}$ times and no moves at previous positions were made. Observe now that $a_1, \dots, a_{k-2}, x_{k-2}$ is a balanced arrangement. Indeed it was noted that $x_j \ge 0$ for all $j = 0, \dots, k-2$. So we see that conditions $(*)$ hold for the numbers at the first $k-1$ positions: it is enough to redefine $a_{k-1}$ and $x_{k-1}$ as $a_{k-1} = x_{k-2}$ and $x_{k-1} = 0$.

Consequently $A$'s move M, if possible, can be regarded as the opening move in a balanced arrangement. So $B$ can apply the winning strategy of the first player for the balanced case. The only further remark needed is that $A$ has no escape from positions $1, \dots, k-1$. Wherever $B$ plays at these positions (following the strategy mentioned), it will be at a position $j$ with the parity of $k$, hence $j \le k-2$. Thus the game is confined to the first $k-1$ positions and the strategy does apply; so $B$ wins.

A collection of integers has a balanced arrangement $a_1, \dots, a_n$ only if its total sum is even. Indeed $\sum_{j=1}^{n} a_j = 2 \sum_{j=0}^{n+1} x_j$ by the definition. Therefore there is no balanced arrangement of $1, \dots, n$ for $n \equiv 1, 2 \pmod 4$ where $1+2+\dots+n$ is odd. So $B$ has a winning strategy if $n$ is $1$ or $2$ modulo $4$. On the other hand a balanced arrangement of $1, \dots, n$ exists if $n = 4k$ or $n = 4k-1$, $k \ge 1$. Write the odd numbers in $[1, n]$ in ascending order, then the even numbers in descending order. For $n = 4k$ the arrangement is
$$1 = 0+1, \quad 3 = 1+2, \quad 5 = 2+3, \quad \dots, \quad 4k-1 = (2k-1)+2k,$$
$$4k = 2k+2k, \quad 4k-2 = 2k+(2k-2), \quad \dots, \quad 4 = 2+2, \quad 2 = 2+0.$$

For $n = 4k - 1$ just ignore $4k$. Thus $A$ has a winning strategy if $n$ is $0$ or $-1$ modulo $4$.