Iranian Mathematical Olympiad

We claim that the second player has a winning strategy for $(m,n)=(p^{\alpha },p^{\beta })$ where $p$ is a prime number and $\alpha ,\beta \in {\mathbb{Z}}^{\ge 0}$. We call a pair $(m,n)$ a good pair if the second player has a winning strategy.

Lemma 1. If $(m,n)$ is a good pair and $d\mid m$ then $(d,n)$ is also a good pair.

Proof. Assume that the game starts with the sequence $a_1,a_2,...,a_d$. Mohammad considers a second game that starts with the sequence $({\tilde{a}}_1,{\tilde{a}}_2,...,{\tilde{a}}_m)$ where ${\tilde{a}}_{\frac{mi}{d}}=a_i$ and ${\tilde{a}}_j=0$, for $\frac{m}{d}\nmid j$. Now if Ali chooses $s$ in the first game, Mohammad assumes that Ali chooses $\frac{m}{d}s$ in the second game and follows his strategy and wins the second game. But the first game is just a restriction of the second game to the components $\frac{m}{d}i$ so he can also win the first game.

Lemma 2. $(m,nk)$ is a good pair if and only if $(m,n)$ and $(m,k)$ are also good pairs.

Proof. If $(m,nk)$ is a good pair then it is clear that $(m,n)$ and $(m,k)$ are good pairs. Now if $(m,n)$ and $(m,k)$ are good pairs, starting with a sequence $a_1,...,a_m$ then using the aforementioned strategy for $(m,n)$, making all the components divisible by $n$. Considering the sequence $(\frac{a_i}{n})$, applying the preceding strategy for $(m,k)$ to ensure that $k\mid \frac{a_i}{n}$, by the very end all the terms are divisible by $nk$ and hence $nk$ is a good pair.

By these lemmas we see that if $(m,n)$ is a good pair and $p\mid m$, $q\mid n$ then $(p,q)$ is also a good pair. Now by the next lemma we would obtain $p=q$. Hence $(m,n)$ should be of the form $(p^{\alpha },p^{\beta })$.

Lemma 3. If $(m,n)$ is a good pair and $m,n>1$ then $\gcd (m,n)>1$.

Proof. Assume that $\gcd (m,n)=1$. Consider one step before the end of the game. The sequence $(a_i)$ must be constant; otherwise for each sequence $(b_i)$ there is some $j$ such that $a_i+b_j\not\equiv 0(\mathrm{mod}n)$ and the first player can choose $j-i$. In the second step before the last step, we should have $$a_0-a_m\equiv a_1-a_0=a_2-a_1\equiv \cdots \equiv a_m-a_{m-1}(\mathrm{mod}n),$$ otherwise Ali could choose a shift $s$ such that $(a_i+b_{i+s})$ is not constant. So we must have $m(a_1-a_0)\equiv 0(\mathrm{mod}n)$, implying that $a_1-a_0\equiv 0(\mathrm{mod}n)$. So the sequence is constant. We then use induction to deduce that the sequence should be constant from the starting point. So, for a non-constant sequence the first player has a winning strategy.

It remains to prove that $(p^{\alpha },p^{\beta })$ is a good pair. By the second lemma it suffices to prove that $(p^{\alpha },p)$ is a good pair. We claim that if the second player chooses $b_i=-a_i$ at each step, he shall win. There are two ways to do this:

First proof. Let $T:(\mathbb{Z}/p\mathbb{Z}{)}^m\to (\mathbb{Z}/p\mathbb{Z}{)}^m$ denote a shift by 1. Then at each step the sequence changes to $(T^s-\text{id})(a_1,\dots ,a_{p^{\alpha }})$. It suffices to prove that $$\prod _{j=1}^{p^{\alpha }}(T^{s_j}-\text{id})\equiv 0(\mathrm{mod}p)$$ but $T-\text{id}\mid T^{s_j}-\text{id}$. So it is enough to prove $(T-\text{id}{)}^{p^{\alpha }}\equiv 0(\mathrm{mod}p)$ but $$(T-\text{id}{)}^{p^{\alpha }}\equiv T^{p^{\alpha }}-\text{id}\equiv 0(\mathrm{mod}p).$$

Second proof.

Lemma 4. There is an integer-valued polynomial $Q(x)$ such that $Q(i)\equiv a_i(\mathrm{mod}p)$ for all $1\le i\le p^{\alpha }$.

Proof. Consider the polynomial $P_i(x)=\left(\genfrac{}{}{0ex}{}{x-i-1}{p^{\alpha }-1}\right)$. One can see that $P_i(i)\equiv 1(\mathrm{mod}p)$ and for $j\ne i(\mathrm{mod}{p}^{\alpha })$, we have $P_i(j)\equiv 0(\mathrm{mod}p)$. Then we can choose $$Q(x)=\sum _{i=1}^{p^{\alpha }}{a}_i{P}_i(x).$$ Now, in the next step we have $a_i\equiv Q(i)-Q(i+s)(\mathrm{mod}p)$ but the degree of $Q(x)-Q(x+s)$ is less than $\mathrm{deg}(Q)$ so after $p^{\alpha }$ steps the second player wins.