SELECTION TESTS FOR THE 2019 BMO AND IMO

Alice has a winning strategy if and only if $n$ is congruent to $0$ or $-1$ modulo $4$.

Looking upon placing the token on a number as a one unit drop of that number, a move is possible if and only if the current position of the token is not flanked by two zeroes. Notice that each player places the token on positions of like parity rank.

An arrangement $a_1,\dots ,a_n$ of an $n$-element collection of non-negative integers is suitable if there exist non-negative integers $x_0,x_1,\dots ,x_n$ such that $$x_0=x_n=0,\text{and}{a}_k=x_{k-1}+x_k,k=1,\dots ,n.$$

Notice that, in a suitable arrangement, the $a_k$ add up to twice the sum of the $x_k$, to infer that, for a collection of non-negative integers to have a suitable arrangement, it is necessary that the numbers in the collection add up to an even number. Otherwise, the collection has no suitable arrangement. In particular, if $n$ is congruent to $1$ or $2$ modulo $4$, there is no suitable arrangement of the collection $1,2,\dots ,n$. If $n=4m$, then $$\begin{array}{l}1=0+1,3=1+2,5=2+3,\dots ,4m-1=(2m-1)+2m,\\ 4m=2m+2m,\\ 4m-2=2m+(2m-2),\dots ,6=4+2,4=2+2,2=2+0\end{array}$$ is a suitable arrangement of the collection $1,2,\dots ,n$. Clearly, removal of $4m$ provides a suitable arrangement in case $n=4m-1$.

We first prove that, if the initial arrangement is suitable, then Alice wins. The idea is that Alice can counter any legal move of Bob, in a suitable arrangement, so as to make the new arrangement again suitable. Since the initial arrangement is suitable, and the game eventually comes to an end, Bob ultimately gets stuck and loses.

Let $a_1,\dots ,a_n$ be a suitable arrangement, and let Bob place the token on the $k$-th position. Since Bob's move is legal, $x_{k-1}+x_k=a_k>0$. Without loss of generality, we may and will assume that $x_k>0$, so $a_{k+1}=x_k+x_{k+1}\ge x_k>0$, showing that the $(k+1)$-st position is available for Alice to place the token on. After having done so, the new arrangement is again suitable, since $a_k$ changed to $a_k^{\prime }=x_{k-1}+(x_k-1)$, $a_{k+1}$ changed to $a_{k+1}^{\prime }=(x_k-1)+x_{k+1}$, and the other numbers are left unchanged. This establishes one implication.

Next, we show that, if the initial arrangement is not suitable, then Bob has a winning strategy. The idea is that this time Bob can achieve a suitable subarrangement just before one of Alice's moves, reset the whole game with this suitable subarrangement as initial arrangement, and then set on to win by using the strategy described in the previous paragraph.

Let $a_1,\dots ,a_n$ be the initial arrangement; by assumption, it is not suitable. Let further $x_0=0$, and let $x_k=a_k-x_{k-1}$, $k=1,\dots ,n$. Setting $a_{n+1}=0$, it follows that $x_k>a_{k+1}$ for some positive integer $k\le n$: Indeed, if $x_k\le a_{k+1}$ for all indices $k\le n$, then $x_1,x_2,\dots ,x_n$ are all non-negative; since the arrangement $a_1,\dots ,a_n$ is not suitable, $x_n>0=a_{n+1}$. Let $m$ be the least index such that $x_m>a_{m+1}$, so $x_k\ge 0$ for all indices $k<m$.

Bob's first move consists in placing the token on the $m$-th position. After Bob's first move, $a_m$ changes to $a_m-1=(x_{m-1}+x_m)-1=x_{m-1}+(x_m-1)\ge x_{m-1}+a_{m+1}$. He may therefore place the token on the $m$-th position at least another $x_{m-1}+a_{m+1}$ times, regardless of Alice's placing the token on one of the neighbouring positions — at most $a_{m+1}$ times on the $(m+1)$-st position, and at most $a_{m-1}$ times on the $(m-1)$-st position (set $a_0=0$ if need be). Since $x_{m-1}+a_{m+1}\ge a_{m+1}$ (recall that $x_k\ge 0$ for all indices $k<m$), Bob is able to exhaust Alice's $a_{m+1}$ allowed choices of the $(m+1)$-st position by keeping on placing the token on the $m$-th position. Thus, if still legal, her $(x_{m-1}+1)$-st move — call it move $(\ast )$ — consists in placing the token on the $(m-1)$-st position.

Just before move $(\ast )$, the first $m-1$ positions in the arrangement are $a_1,\dots ,a_{m-2},x_{m-2}$, since $a_{m-1}=x_{m-2}+x_{m-1}$ dropped by $x_{m-1}$, and no move has been made on one of the first $m-2$ positions. At this stage, Bob can reset the whole game within the first $m-1$ positions: The $(m-1)$-element arrangement $a_1,\dots ,a_{m-2},x_{m-2}$ is suitable, since $x_{m-2}\ge 0$, and he may reset $x_{m-1}=0$ to fulfil the conditions in the definition. If still legal, move $(\ast )$ can now be looked upon as the first move in this suitable arrangement. Finally, by keeping on placing the token on one of these positions, Bob forces Alice to do so: Indeed, recall that just before resetting the game, his last move was on position $m$; if he now places the token on position $k\le m-1$, then $k\le m-2$, since $k$ and $m$ must share parity. This completes the argument and concludes the proof.