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 $$(\ast )x_0=x_n=0\text{and}{a}_k=x_{k-1}+x_k\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^{\prime }=x_{k-1}+x_k^{\prime }$ and $a_{k+1}^{\prime }=x_k^{\prime }+x_{k+1}$ with $x_k^{\prime }=x_k-1$, and $x_k^{\prime }\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\text{and}{x}_k=a_k-x_{k-1}\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 $(\ast )$ 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 $(\ast )$ 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(\mathrm{mod}4)$ where $1+2+\cdots +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,3=1+2,5=2+3,\dots ,4k-1=(2k-1)+2k,$$ $$4k=2k+2k,4k-2=2k+(2k-2),\dots ,4=2+2,2=2+0.$$

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