41st Balkan Mathematical Olympiad

Solution. We will show that Bob wins if and only if $4|n$ and $n\ne 4$. We will often say that Anna and Bob are at a distance $d$ if we can move one token $d$ positions clockwise or anticlockwise to reach the other token. Note that the value of this distance is not unique. We first treat the case $4\nmid n$. Given a positive integer $r$, we define $$m_r=\frac{r^2+r+2}{2}\text{and}{D}_r=\{d\in \{1,2,\dots ,m_r\}:d\equiv m_r\mathrm{mod}2\}$$ Lemma 1. If it is Anna's turn on round $n-1-r\ge 1$ or round $2n-1-r\ge 1$, and she is at a distance $d$ from Bob, for some $d\in D_r$, then she has a winning strategy. Before proving the Lemma, we show why this implies that Anna has a winning strategy in the case $4\nmid n$. Note that $$m_{n-2}=\frac{n^2-3n+4}{2}\ge n$$ In particular, $D_{n-2}$ consists of all odd or of all even numbers in $\{1,2,\dots ,n-1\}$. If $n$ is odd, the clockwise and the anti-clockwise distance of Anna from Bob have opposite parities so Anna is at a distance $d$ from Bob for some $d\in D_{n-2}$. Applying the Lemma for $r=1$ we see that Anna has a winning strategy. If $n\equiv 2(\mathrm{mod}4)$, then $n^2-3n+4\equiv 2(\mathrm{mod}4)$, so $m_{n-2}$ is odd. A same argument as above shows that Anna has a winning strategy if $d$ is also odd. If $d$ is even then we apply the Lemma in the same way with $r=2n-2$ and Anna has a winning strategy since $m_{2n-2}=2n^2-3n+2$ is even (and $m_{2n-2}\ge n$). Proof. (of Lemma 1) We proceed by induction on $r$. For $r=1$ we have $m_1=2$ and $D_1=\{2\}$ and since we are in round $n-2$ or $2n-2$ she has a winning strategy.

---

Assume the result is true for $r=k$. For the inductive step suppose it is now Anna's turn on round $n-1-(k+1)=n-(k+2)$ or round $2n-1-(k+1)=2n-(k+2)$ and she is at a distance $d$ from Bob, for some $d\in D_{k+1}$. By moving her token $n-(k+2)$, or $2n-(k+2)$ positions in the opposite direction, she is now at a distance of $|d-(k+2)|$ positions from Bob. After Bob's move they will have a distance of $d^{\prime }$ for some $d^{\prime }\in \{d-k-3,d-k-1,k+3-d,k+1-d\}$. Note that all of these numbers have the same parity as $d-(k+1)\equiv m_{k+1}-(k+1)\equiv m_k(\mathrm{mod}2)$. Furthermore, $$d-k-3\le d-k-1\le m_{k+1}-(k+1)=m_k$$ and $$k+1-d\le k+3-d\le k+2\le m_k+1.$$ (Here we assumed that $d\ge 1$ as otherwise Anna already won.) Since in all cases $d^{\prime }\le m_k+1$ and $d^{\prime }\equiv m_k(\mathrm{mod}2)$, then $d^{\prime }\le m_k$. Therefore Anna wins by the induction hypothesis. $\square$ We now treat the case $4|n$, say $n=4r$. If $r=1$ it is easy to see that Anna wins in at most two rounds so assume $r>1$. Bob places his token so that $d=3$. Note that Anna cannot win on her first move. Let $d_{2k-1}$ denote the distance after Anna's move on the $k$-th round and $d_{2k}$ the distance after Bob's move on the $k$-th round. Then modulo 2 the sequence is $0,1,1,0,1,0,0,1,\dots$ which then repeats periodically with period 8. Bob's strategy consists of two parts. The first part is that he never places his token on Anna's token and also he never moves his token on a position where he will immediately lose on Anna's next step unless he is really forced to do this. Before explaining the second part of Bob's strategy let us assume for contradiction that Anna has a winning strategy and look at Bob's last move. Due to the first part of his strategy he could perhaps lose only in the following two cases: (a) Before his last move $d=1$ so he is forced to make it $d=2$ and then Anna wins. (b) Before his last move $d=2r$ so he is forced to make it $d=2r-1$ ($d=2r+1$ is the same) and then Anna wins. In case (a) Anna wins on a round of the form $2(\mathrm{mod}4)$ which is impossible as on those rounds $d$ is odd after Anna's move In case (b) Anna wins on rounds of the form $(2r-1)(\mathrm{mod}4r)$ or $(2r+1)(\mathrm{mod}4r)$. Actually rounds of the form $(2r+1)(\mathrm{mod}4r)$ are rejected since in that case we would have $d=2r$ when Bob was playing on round $2r(\mathrm{mod}4k)$ but that could only be possible if $d=0$ when Anna was playing on round $2r(\mathrm{mod}4r)$. This is rejected as it means that Anna won on an earlier round.

So in case (b) Anna wins on rounds of the form $(2r-1)\mathrm{mod}4r$. If $r$ is even, say $r=2s$, this is impossible as on round $(2r-1)\equiv 3\mathrm{mod}4$ we have that $d$ is odd after Anna's move. So we need to show how Bob can avoid case (b) if $r$ is odd, say $r=2s+1$. He needs to avoid $d=2r$ when it's his turn to play on rounds of the form $(2r-2)\mathrm{mod}4r$. This can only occur if $d=2$ when it's Anna's turn to play on rounds of the form $(2r-2)\mathrm{mod}4r$. Bob can avoid this unless $d=1$ when it's his turn to play on rounds of the form $(2r-3)\mathrm{mod}4r$. This can only occur if $d=2r-2$ or $d=2r-4$ when it's Anna's turn to play on rounds of the form $(2r-3)\mathrm{mod}4r$. Bob can avoid both of these cases unless $d=(2r-3)$ when it's his turn to play on rounds of the form $(2r-4)\mathrm{mod}4r$. This can only occur if $d=1$ or $d=7$ when it's Anna's turn to play on rounds of the form $(2r-4)\mathrm{mod}4r$. But Bob can avoid both of these on his move (on rounds of the form $(2r-5)\mathrm{mod}4r$). The only potential issue would be if $n=10$ which is not the case here. $\square$