Let $n\ge 2$ be an integer. Ariane and Bérénice play a game on the number of the residue classes modulo $n$. At the beginning there is the residue class $1$ on each piece of paper. It is the turn of the player whose turn it is to replace the current residue class $x$ with either $x + 1$ or by $2x$. The two players take turns, with Ariane starting. Ariane wins if the residue class $0$ is reached during the game. Bérénice wins if she can prevent that permanently. Depending on $n$, determine which of the two has a winning strategy.
Problem
Source: 2019 Austrian Federal Competition For Advanced Students, Part 1 p3
Tags: number theory, game, winning strategy, combinatorics, game strategy, Austria
A-Thought-Of-God
07.10.2020 14:30
Special thanks to srijonrick for correcting possible grammatical mistakes and solution format Solution: For simplicity, let's call Ariane and Bérénice as $A$ and $B$ respectively. Claim. When $n$ is odd, $B$ wins. Proof. Let $n=2q+1$. If $B$ faces some $\ell \in \{1,2,\ldots,q-1,q+1,\ldots,2q-1,2q\}$ congruent modulo $n$ in his turn. Replace $\ell$ with $2\ell$ congruent $n$ and when $\ell=q$ replace $\ell$ with $\ell+1$. It's easy to see that this doesn't lead to either of $-1$ or $0$ congruent $n$ for $A,$ leading to $B$ preventing $A$ from wining, hence wining the game. $\quad \square$ Claim. When $n$ is even, $A$ wins iff $n \in \{2,4,8\}$.
as when $n=2,$ we have $1 \underset{A}{\mapsto} 2\equiv 0$ and when $n=4,$ we have $$1 \underset{A}{\mapsto} 2 \underset{B}{\mapsto} \{3,0\} \underset{A}{\mapsto} 0$$and when $n=8,$ we can have $$1\underset{A}{\mapsto} 2\underset{B}{\mapsto}\{3,4\} \underset{A}{\mapsto} \{6,0\} \underset{B}{\mapsto} \{7,4\} \underset{A}{\mapsto} \{0,0\}$$
. Now, let $n=2q$. We will try to deduce when $B$ loses. Let's say, at some moment, $B$ faces $x$ and will lose obviously if $x+1$ and $2x$ both of which belongs to $\mathcal{G}=\{0,q,-1\}$, since then, $A$ can do $\{0 \mapsto 0,q \mapsto 2q \equiv 0, -1 \mapsto 0\}$. Now, if $x+1 \equiv 2x \implies x\equiv1$, so $2 \in \mathcal{G}$ iff $2 \equiv \{0,q,-1\} \pmod{2q} \implies q \in \{1,2\}$, which we have already dealt with. So, from now, we will assume $x+1\not\equiv 2x$. On doing so, we get the following set of equations: $$\begin{cases} x+1\equiv 0 \pmod{2q} \\ 2x \equiv q \pmod{2q} \end{cases} \quad \begin{cases} x+1\equiv q \pmod{2q} \\ 2x \equiv 0 \pmod{2q}\end{cases}$$$$\begin{cases} x+1\equiv q \pmod{2q} \\ 2x \equiv -1 \pmod{2q} \end{cases} \quad \begin{cases} x+1\equiv -1 \pmod{2q} \\ 2x \equiv q \pmod{2q}\end{cases}$$$$\begin{cases} x+1\equiv 0 \pmod{2q} \\ 2x \equiv -1\pmod{2q} \end{cases} \quad \begin{cases} x+1\equiv -1 \pmod{2q} \\ 2x \equiv 0 \pmod{2q}\end{cases}$$Consequently, we will get $q \in \{1,2,4\}$, which again we have done. So, in rest of the cases we cannot possibly have both $x+1$ and $2x$ in $\mathcal{G}$, so, there will always be at least one way or other, such that $B$ can make a move without letting $A$ win. $\blacksquare$