Let $n \geq 2$ be an integer. Ariane and Bérénice are playing a game on the set of residue classes modulo $n$. At the beginning, the residue class 1 is written on a piece of paper. In each turn, the player whose turn it is replaces the current residue class $x$ either by $x+1$ or by $2x$. The two players take turns, with Ariane starting.

Ariane wins if the residue class 0 is reached at any point during the game. Bérénice wins if she can prevent this indefinitely.

Determine, depending on $n$, which of the two has a winning strategy.

(Theresia Eisenkölbl)

Answer. Ariane wins for $n=2, 4$, and 8, and Bérénice wins for all other $n \geq 2$.
We first consider the cases $n=2,3,4,6$ and 8 individually and then show that Bérénice wins for all other $n$. All congruences in this solution are to be understood modulo $n$.

- For $n=2$, Ariane moves to 0 in the first step and wins.
- For $n=3$, Ariane is forced to move to $1+1=2 \cdot 1=2$ in the first step. Bérénice can then move to $2 \cdot 2 \equiv 1$, thus Bérénice can enforce that the game alternates between 1 and 2 and never reaches 0. Therefore, Bérénice wins.
- For $n=4$, Ariane moves to 2 in the first step again. Bérénice must then choose between $2+1=3$ and $2 \cdot 2=4$. If she chooses $4 \equiv 0$, she immediately loses. If she chooses 3, Ariane can win in the next step by choosing $3+1=4 \equiv 0$. Thus, Ariane has a winning strategy.
- For $n=6$, Bérénice wins with optimal play, as she can avoid the number ever being divisible by 3 using the strategy for $n=3$.
- For $n=8$, Ariane moves to 2 in the first step again. If Bérénice chooses 4, Ariane can immediately win by choosing $8 \equiv 0$. If Bérénice chooses 3, Ariane can choose 6. If Bérénice then chooses 7, Ariane wins with $7+1=8 \equiv 0$. If Bérénice chooses $2 \cdot 6=12 \equiv 4$, Ariane wins with $2 \cdot 4=8 \equiv 0$. Thus, Ariane wins with optimal play.

Now let $n \geq 2$ with $n \neq 2,3,4,6$ or 8. Ariane certainly does not win in the first step, as $2 \not \equiv 0$. If Bérénice can permanently avoid choosing $n, n-1$, or $n / 2$ (if $n$ is even), then Ariane can never win. We need to check for which number $x$ on the paper Bérénice is forced to choose one of these numbers in the next step because both of her options are on this list.

If $x+1$ is congruent to one of the numbers $n, n-1$, or $n / 2$, then $4x$ is congruent to -4 or -8. If $2x$ is congruent to one of the numbers $n, n-1$, or $n / 2$, then $4x$ is congruent to 0 or -2. Therefore, both options can only be unfavorable if $n$ divides one of the differences 2, 4, 6, or 8 between the described values for $4x$. However, we have already handled all these divisors separately.

Thus, Bérénice is never forced to choose 0 or to give Ariane the opportunity to choose 0 for $n \neq 2,3,4,6$ or 8. Therefore, Ariane can never win for these numbers. Bérénice's winning strategy is simply to avoid the numbers $n, n-1$, and $n / 2$ and otherwise play arbitrarily.

(Theresia Eisenkölbl)