Shortlist 2017, N2

Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : Morocco

Concepts : Jeux et stratégies gagnantes · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 76 (page 78 du PDF)

Énoncé

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, \ldots, p-1\}\) that was not chosen before by either of the two players and then chooses an element \(a_i\) of the set \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\). Eduardo has the first move. The game ends after all the indices \(i \in \{0, 1, \ldots, p-1\}\) have been chosen. Then the following number is computed:

\[M = a_0 + 10 \cdot a_1 + \cdots + 10^{p-1} \cdot a_{p-1} = \sum_{j=0}^{p-1} a_j \cdot 10^j.\]

The goal of Eduardo is to make the number \(M\) divisible by \(p\), and the goal of Fernando is to prevent this.

Prove that Eduardo has a winning strategy.

Indices : les idées clés

• Jeux et stratégies gagnantes : stratégie d'appariement ; Eduardo répond à chaque coup de Fernando sur l'indice « jumeau ».
• Congruences, théorèmes de Fermat et d'Euler : par le petit théorème de Fermat, \(10^{(p-1)/2} \equiv \pm 1 \pmod p\).
• Neutraliser un indice au premier coup : Eduardo joue \(a_{p-1} = 0\), il reste alors un nombre pair d'indices, regroupés en paires \(\{r, r + \frac{p-1}{2}\}\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2017 (une solution).

Solution

On dit qu'un joueur joue le coup \((i, a_i)\) s'il choisit l'indice \(i\) puis le chiffre \(a_i\).

Cas \(p = 2\) ou \(p = 5\). Eduardo joue \((0, 0)\) au premier coup et gagne : quels que soient les coups suivants, \(M\) est un multiple de \(10\).

Cas \(p \notin \{2, 5\}\). Eduardo joue \((p-1, 0)\) au premier coup. Par le petit théorème de Fermat,

\[\left(10^{(p-1)/2}\right)^2 = 10^{p-1} \equiv 1 \pmod p,\]

donc \(p\) divise \(\left(10^{(p-1)/2}\right)^2 - 1 = \left(10^{(p-1)/2} + 1\right)\left(10^{(p-1)/2} - 1\right)\). Comme \(p\) est premier, \(p \mid 10^{(p-1)/2} + 1\) ou \(p \mid 10^{(p-1)/2} - 1\). Les indices restants \(0, 1, \ldots, p-2\) se regroupent en les paires \(\{r, r + \frac{p-1}{2}\}\), \(0 \leq r \leq \frac{p-3}{2}\).

Cas a : \(10^{(p-1)/2} \equiv -1 \pmod p\). À chaque coup \((i, a_i)\) de Fernando, Eduardo répond immédiatement par le coup

\[(j, a_j) = \left(i + \tfrac{p-1}{2},\ a_i\right) \text{ si } 0 \leq i \leq \tfrac{p-3}{2}, \qquad (j, a_j) = \left(i - \tfrac{p-1}{2},\ a_i\right) \text{ si } \tfrac{p-1}{2} \leq i \leq p-2.\]

On a alors \(10^j \equiv -10^i \pmod p\), donc \(a_j \cdot 10^j = a_i \cdot 10^j \equiv -a_i \cdot 10^i \pmod p\).

Ce coup est toujours possible : juste avant chaque coup de Fernando, pour chaque paire \(\{r, r + \frac{p-1}{2}\}\), soit aucun des deux indices n'a été choisi, soit les deux l'ont été. Ainsi, après chacun de ses coups, Eduardo rend divisible par \(p\) la somme des \(a_k \cdot 10^k\) pour les couples \((k, a_k)\) déjà joués ; il gagne donc la partie.

Cas b : \(10^{(p-1)/2} \equiv 1 \pmod p\). À chaque coup \((i, a_i)\) de Fernando, Eduardo répond par

\[(j, a_j) = \left(i + \tfrac{p-1}{2},\ 9 - a_i\right) \text{ si } 0 \leq i \leq \tfrac{p-3}{2}, \qquad (j, a_j) = \left(i - \tfrac{p-1}{2},\ 9 - a_i\right) \text{ si } \tfrac{p-1}{2} \leq i \leq p-2.\]

Le même argument montre que ce coup est toujours possible. On a \(10^j \equiv 10^i \pmod p\), donc

\[a_j \cdot 10^j + a_i \cdot 10^i \equiv (a_i + a_j) \cdot 10^i = 9 \cdot 10^i \pmod p.\]

À la fin de la partie, chaque paire contribuant \(9 \cdot 10^r\) avec \(0 \le r \le \frac{p-3}{2}\), on obtient

\[M \equiv \sum_{i=0}^{(p-3)/2} 9 \cdot 10^i = 10^{(p-1)/2} - 1 \equiv 0 \pmod p,\]

et Eduardo gagne. \(\blacksquare\)