Shortlist 2024, C5¶
Domaine : Combinatoire · Difficulté : ★★★☆☆ · Proposé par : Indonesia
Concepts : Jeux et stratégies gagnantes · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2024 (avec solutions), section C5 (livret PDF)
Figures reprises du livret officiel de la Shortlist.
Énoncé¶
Let \(N\) be a positive integer. Geoff and Ceri play a game in which they start by writing the numbers \(1, 2, \ldots, N\) on a board. They then take turns to make a move, starting with Geoff. Each move consists of choosing a pair of integers \((k, n)\), where \(k \geq 0\) and \(n\) is one of the integers on the board, and then erasing every integer \(s\) on the board such that \(2^k \mid n - s\). The game continues until the board is empty. The player who erases the last integer on the board loses.
Determine all values of \(N\) for which Geoff can ensure that he wins, no matter how Ceri plays.
Indices : les idées clés
- Jeux et positions gagnantes : classer les ensembles en gagnants et perdants pour le joueur qui doit jouer.
- Découper selon la parité : écrire tout ensemble comme \(J(S, T) = (2S - 1) \cup (2T)\) ; un coup sur \(S\) correspond à un coup sur \(J(S, \varnothing)\), ce qui donne une bijection entre les parties.
- Stratégie miroir (lemme 3) : sur \(J(S, S)\), l'adversaire recopie sur les pairs ce qui a été joué sur les impairs.
- Récurrence : \([2n]\) gagne si et seulement si \([n]\) perd, et \([2n+1]\) gagne toujours ; on conclut par récurrence sur l'exposant de \(2\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (une solution et deux remarques).
Réponse. Geoff peut s'assurer la victoire si et seulement si \(N = 2^n\) avec \(n\) impair, ou \(N = t \cdot 2^n\) avec \(n\) pair et \(t > 1\) impair.
Notations communes. On dit qu'un ensemble \(S\) gagne si le joueur qui doit jouer gagne lorsque \(S\) est l'ensemble des entiers écrits au tableau, et qu'il perd sinon. On pose \(J(S, T) = (2S - 1) \cup (2T)\), où \(2S - 1 = \{2s - 1 \mid s \in S\}\) et \(2T = \{2t \mid t \in T\}\) ; toute partie de \(\mathbb{Z}\) s'écrit de manière unique sous la forme \(J(S, T)\). Enfin, \([n] = \{1, 2, \ldots, n\}\).
Solution¶
Lemme 1. Pour tout ensemble \(S\), \(S\) gagne si et seulement si \(J(S, \varnothing)\) gagne. De même, \(S\) gagne si et seulement si \(J(\varnothing, S)\) gagne.
Preuve. Soit \((k, m)\) un coup sur \(S\), qui donne l'ensemble \(T\). Alors le coup \((k + 1, 2m - 1)\) transforme \(J(S, \varnothing)\) en \(J(T, \varnothing)\). Réciproquement, soit \((k, m)\) un coup sur \(J(S, \varnothing)\) ; son résultat s'écrit \(J(T, \varnothing)\) pour un certain \(T\), et le coup \(\big(\max(k - 1, 0), \frac{m+1}{2}\big)\) transforme \(S\) en \(T\). On obtient ainsi une bijection naturelle entre les parties issues de \(S\) et celles issues de \(J(S, \varnothing)\), d'où la première assertion. La seconde se prouve de même. \(\square\)
Lemme 2. Si \(S\) et \(T\) sont non vides et que l'un d'eux au moins perd, alors \(J(S, T)\) gagne.
Preuve. Si \(S\) perd, le coup \((1, t)\) avec \(t \in J(\varnothing, T)\) efface \(J(\varnothing, T)\) (tous les pairs) et laisse l'ensemble perdant \(J(S, \varnothing)\) (lemme 1). De même, si \(T\) perd, le coup \((1, s)\) avec \(s \in J(S, \varnothing)\) efface tous les impairs et laisse l'ensemble perdant \(J(\varnothing, T)\). \(\square\)
Lemme 3. Si \(S\) est non vide et gagne, alors \(J(S, S)\) perd.
Preuve. Dans cette position, on peut transformer toute suite de coups valide en une autre en remplaçant \((k, 2n - 1)\) par \((k, 2n)\) et inversement ; on peut donc supposer que le premier coup \((k, m)\) a \(m\) impair. Montrons qu'un tel coup donne une position gagnante pour l'autre joueur. Le coup \((0, m)\) efface tout et perd immédiatement. Sinon, le coup donne un ensemble \(J(T, S)\), et il y a trois cas.
- Si \(T\) est vide, l'adversaire reçoit l'ensemble gagnant \(J(\varnothing, S)\) (lemme 1).
- Si \(T\) perd, l'adversaire joue \((1, s)\) avec \(s \in J(\varnothing, S)\), ce qui laisse l'ensemble perdant \(J(T, \varnothing)\).
- Si \(T\) est non vide et gagne, l'adversaire joue le coup « miroir » \((k, m + 1)\), ce qui donne \(J(T, T)\). Comme \(|T| < |S|\), on montre par récurrence sur \(|S|\) que cet ensemble perd. \(\square\)
Lemme 4. \([2n]\) gagne si et seulement si \([n]\) perd.
Preuve. On a \([2n] = J([n], [n])\) ; le résultat découle directement des lemmes 2 et 3. \(\square\)
Lemme 5. Pour tout entier \(n \geq 1\), \([2n + 1]\) gagne.
Preuve. D'après le lemme 4, \([n]\) ou \([2n]\) perd. Si \([n]\) perd, alors \([2n + 1] = J([n + 1], [n])\) gagne par le lemme 2. Sinon, \([2n]\) perd, et \([2n + 1]\) gagne en jouant le coup \((k, 2n + 1)\) avec \(k\) assez grand pour n'effacer que \(2n + 1\). \(\square\)
Conclusion. Il reste à vérifier la réponse ; deux cas se présentent.
- Si \(N = 2^n\) : pour \(N = 1\), tout coup de Geoff le fait perdre immédiatement. D'après le lemme 4, Geoff gagne pour \(N = 2^n\) si et seulement s'il perd pour \(N = 2^{n-1}\) ; par récurrence, Geoff gagne pour \(N = 2^n\) si et seulement si \(n\) est impair.
- Sinon, \(N = t \cdot 2^n\) avec \(t > 1\) impair. D'après le lemme 5, Geoff gagne pour \(n = 0\). D'après le lemme 4, Geoff gagne pour \(N = t \cdot 2^n\) si et seulement s'il perd pour \(N = t \cdot 2^{n-1}\) ; par récurrence sur \(n\), Geoff gagne si et seulement si \(n\) est pair. \(\blacksquare\)
Remarques¶
Remarque 1 (arbres binaires). On peut représenter le jeu sur des arbres binaires partiels, ce qui facilite l'exploration des petits cas. Pour chaque entier \(n \geq 1\), on lit l'écriture binaire de \(n - 1\) en commençant par le bit de poids faible (suivie d'une infinité de zéros), et l'on en fait un chemin depuis la racine d'un arbre binaire infini : fils gauche pour un \(0\), fils droit pour un \(1\). On tronque chaque chemin dès qu'il est assez profond pour se distinguer des autres. Un coup consiste alors à choisir un nœud qui a deux fils et à supprimer l'un des deux fils (avec ses descendants) ; supprimer tout l'arbre est aussi permis (et perd aussitôt). Deux arbres topologiquement identiques donnent des jeux équivalents : on peut échanger les fils gauche et droit d'un nœud, ou supprimer un nœud n'ayant qu'un fils en fusionnant les arêtes au-dessus et au-dessous. Ces équivalences réduisent beaucoup le nombre de cas à examiner pour \(N\) petit.
Remarque 2 (valeurs de Grundy). On peut aussi analyser le jeu avec les valeurs de Grundy (nimbers), en modifiant légèrement la règle : tout coup qui effacerait tous les entiers est interdit, et le premier joueur qui ne peut plus jouer perd (c'est clairement équivalent). Notons \(g(S)\) la valeur de Grundy de l'ensemble \(S\) ; la bijection du lemme 1 montre que \(g(S) = g(J(S, \varnothing)) = g(J(\varnothing, S))\). Pour un ensemble \(V\) d'entiers positifs ou nuls, \(\operatorname{mex}(V)\) désigne le plus petit entier positif ou nul qui n'est pas dans \(V\). On définit par récurrence
Ses premières valeurs (ligne \(y\), colonne \(x\)) sont :
| \(y \backslash x\) | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 5 | 6 | 7 | 8 | 9 | 1 | 0 |
| 4 | 5 | 3 | 6 | 2 | 0 | 1 |
| 3 | 4 | 5 | 1 | 0 | 2 | 9 |
| 2 | 3 | 4 | 0 | 1 | 6 | 8 |
| 1 | 2 | 0 | 4 | 5 | 3 | 7 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
On peut montrer que \(g(J(S, T)) = j(g(S), g(T))\) pour tous ensembles \(S, T\) non vides ; la suite de la preuve suit la même structure que la solution ci-dessus.