2017 IMO SL #N2

Let $ p \geq 2$ be a prime number. Eduardo and Fernando play the following game making moves alternately: in each move, the current player chooses an index $i$ in the set $\{0,1,2,\ldots, p-1 \}$ that was not chosen before by either of the two players and then chooses an element $a_i$ from the set $\{0,1,2,3,4,5,6,7,8,9\}$. Eduardo has the first move. The game ends after all the indices have been chosen .Then the following number is computed: $$M=a_0+a_110+a_210^2+\cdots+a_{p-1}10^{p-1}= \sum_{i=0}^{p-1}a_i \cdot 10^i$$. The goal of Eduardo is to make $M$ divisible by $p$, and the goal of Fernando is to prevent this. Prove that Eduardo has a winning strategy. 

A player makes the move $(i,a_i)$ if he chooses the index $i$ and the element $a_i$ from the set $\{0,1,2,3,4,5,6,7,8,9\}$.  

If we have $p \in \{2,5\}$, then Eduardo can simply do $(0, 0)$ for the first move, and then he wins, since independently of the next moves, we will have $10 \mid M$. 

So, assume that $p$ is not $2$ or $5$. We now define Eduardo's winning strategy for these $p$. 

Eduardo chooses $(p-1,0)$ in the first move. Using Fermat's Little Theorem, we have $$\left(10^{\frac{p-1}{2}}\right)^2=10^{p-1} \equiv 1 \pmod{p}$$ $$\implies 10^{\frac{p-1}{2}} \equiv \pm 1 \mod p.$$

We divide this condition into cases. 

In the first case, we have $10^{\frac{p-1}{2}}\equiv -1\pmod{p}$. Eduardo starts with $(0,0)$. Then, for any index $i$ and number $a_i$ that Fernando chooses, if $i\leq \frac{p-1}{2}$, then Eduardo chooses index $j=i+\frac{p-1}{2}$ and lets $a_j=9-a_i$. If $i>\frac{p-1}{2}$, then Eduardo chooses index $j=i-\frac{p-1}{2}$, and lets $a_j=9-a_i$.

Note that since $p-1$ is even, Eduardo will make the last move. Also note that each index is chosen only once. Now our strategy works since for each choice of $i,j,a_i,a_j$ as in the above algorithm, we have $a_i=a_j=a$ (say) and $$a_i10^i+a_j10^j\equiv a(10^i+10^{i\pm \frac{p-1}{2}})\equiv a10^i(1+10^{\pm\frac{p-1}{2}})\equiv 0\pmod p.$$ Hence, $M\equiv 0\pmod p$ and thus Eduardo wins. 

In the second case, we have $10^{\frac{p-1}{2}}\equiv 1\pmod{p}$. Eduardo similarly starts with $(0,0)$. Then, for any index $i$ and number $a_i$ that Fernando chooses, if $i\leq \frac{p-1}{2}$, then Eduardo chooses index $j=i+\frac{p-1}{2}$ and lets $a_j=9-a_i$. If $i>\frac{p-1}{2}$, then Eduardo chooses index $j=i-\frac{p-1}{2}$, and lets $a_j=9-a_i$.

So for each choice of $i,j,a_i,a_j$ in the above strategy, we have $a_i10^i+a_j10^j\equiv a_i(10^i-10^j)+9\cdot 10^j\equiv a_i10^i(1-10^{\pm\frac{p-1}{2}})+9\cdot 10^j\equiv 9\cdot 10^j\pmod p $. Now let $i_1,i_2,\dots, i_{\frac{p-1}{2}}$ be the indices chosen by Eduardo in that order apart from $0$, and let $j_1,j_2,\dots, j_{\frac{p-1}{2}}$ be the indices chosen by Fernando in that order. Note that $i_k=j_k\pm \frac{p-1}{2}$. Thus we have $$M\equiv 9(10^{i_1}+\dots+10^{i_\frac{p-1}{2}})\equiv 9(10^{j_1}+\dots+10^{j_\frac{p-1}{2}})\equiv \frac{9(10+10^2+\dots+10^{p-1})}{2}\equiv 5(10^{p-1}-1)\equiv 0\pmod p.$$ Hence, Eduardo wins in this case as well. 

We are done. $\square$