Aller au contenu

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é

Soit \(p \geq 2\) un nombre premier. Eduardo et Fernando jouent au jeu suivant en jouant à tour de rôle : à chaque coup, le joueur choisit un indice \(i\) de l'ensemble \(\{0, 1, \ldots, p-1\}\) qui n'a encore été choisi par aucun des deux joueurs, puis un élément \(a_i\) de l'ensemble \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\). Eduardo joue le premier. La partie se termine quand tous les indices \(i \in \{0, 1, \ldots, p-1\}\) ont été choisis. On calcule alors le nombre

\[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.\]

Le but d'Eduardo est que \(M\) soit divisible par \(p\), et celui de Fernando est de l'en empêcher.

Montrer qu'Eduardo a une stratégie gagnante.

Énoncé original (anglais)

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\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2009 C1 ★☆☆☆☆ : On retourne des blocs de \(50\) cartes dont la plus à gauche est dorée : la partie finit-elle, et qui gagne ?
  • 2025 A3 ★★☆☆☆ · OIM P5 : Un jeu où l'un contrôle la somme des nombres choisis et l'autre la somme de leurs carrés : qui gagne selon la valeur de \(\lambda\) ?
  • 2024 C4 ★★☆☆☆ · OIM P5 : Turbo traverse une grille où se cachent des monstres, un par ligne intermédiaire : combien de tentatives lui faut-il ?
  • 2024 C5 ★★★☆☆ : On efface des classes de congruence modulo \(2^k\) ; qui efface le dernier perd : pour quels \(N\) le premier gagne-t-il ?