Jeux et stratégies gagnantes¶
Domaine : Combinatoire · Niveau : intermédiaire · Prérequis : Invariants et monovariants
L'idée¶
Dans un jeu à deux joueurs qui jouent à tour de rôle, avec une information complète, sans hasard et qui se termine toujours, l'un des deux joueurs a une stratégie gagnante. La question est : lequel, et comment joue-t-il ?
Positions gagnantes et perdantes. On classe chaque position du point de vue du joueur qui doit jouer :
- une position est perdante si tous les coups mènent à une position gagnante (pour l'adversaire) ; en particulier, une position sans coup possible est perdante quand « celui qui ne peut plus jouer a perdu » ;
- une position est gagnante s'il existe au moins un coup vers une position perdante.
Pour prouver qu'un ensemble \(P\) de positions est exactement l'ensemble des positions perdantes, il suffit de vérifier deux choses : depuis une position de \(P\), tout coup sort de \(P\) ; depuis une position hors de \(P\), un coup mène dans \(P\). La stratégie gagnante consiste alors à toujours rejouer dans \(P\).
Les grandes stratégies.
- Calculer à rebours les petites positions, deviner la règle, puis la prouver.
- Symétrie et appariement : répondre à chaque coup de l'adversaire par le coup « jumeau ». Exemple : deux joueurs posent tour à tour une pièce sur une table ronde, sans chevauchement, et celui qui ne peut plus jouer perd. Le premier joueur gagne : il pose sa première pièce au centre, puis joue toujours le symétrique, par rapport au centre, du coup de l'adversaire.
- Maintenir un invariant : se ramener toujours à une position où une quantité a une valeur donnée (un multiple de \(k\), une somme nulle).
- Vol de stratégie : si le second joueur avait une stratégie gagnante, le premier pourrait la « voler » en jouant un coup inoffensif d'abord. Cela prouve que le premier joueur gagne, sans dire comment.
Pour les problèmes du type « quel score \(A\) peut-il garantir », il faut deux stratégies : une pour \(A\) qui assure le score \(M\), et une pour \(B\) qui empêche \(A\) d'obtenir plus.
Deux jeux classiques¶
- Jeu de Bachet. Il y a \(n\) allumettes ; chaque joueur en retire entre \(1\) et \(k\) ; celui qui prend la dernière gagne. Les positions perdantes sont les multiples de \(k + 1\).
- Jeu de Nim. Plusieurs tas ; chaque joueur retire autant d'objets qu'il veut dans un seul tas ; celui qui prend le dernier objet gagne. On écrit les tailles en base \(2\) et l'on fait leur somme sans retenue (le « ou exclusif ») : la position est perdante si et seulement si cette somme est nulle.
Exemple résolu¶
Problème
On écrit un entier \(n \geq 1\) au tableau. À tour de rôle, chaque joueur remplace le nombre \(m\) écrit par \(m - d\), où \(d\) est un diviseur de \(m\) avec \(d < m\). Le joueur qui ne peut plus jouer (quand le tableau affiche \(1\)) a perdu. Pour quels \(n\) le premier joueur gagne-t-il ?
Étape 1 : calculer les petits cas. \(1\) est perdante (aucun coup). \(2\) : on joue \(2 - 1 = 1\), gagnante. \(3\) : le seul coup mène à \(2\), gagnante pour l'adversaire, donc \(3\) est perdante. \(4\) : on peut jouer \(4 - 1 = 3\), perdante, donc \(4\) est gagnante. On devine : \(n\) est perdante si et seulement si \(n\) est impair.
Étape 2 : depuis un impair, tout coup mène à un pair. Si \(m\) est impair, tous ses diviseurs \(d\) sont impairs, donc \(m - d\) est pair.
Étape 3 : depuis un pair, un coup mène à un impair. Si \(m\) est pair, alors \(d = 1\) est un diviseur avec \(d < m\), et \(m - 1\) est impair.
Conclusion. Les positions perdantes sont exactement les impairs. Le premier joueur gagne si et seulement si \(n\) est pair, en retirant toujours \(1\).
Le réflexe : calculer à rebours une dizaine de positions, repérer la règle, puis vérifier les deux propriétés qui la caractérisent.
Comment le reconnaître¶
- L'énoncé demande quel joueur a une stratégie gagnante.
- On demande ce qu'un joueur peut garantir (un score, un nombre de cases, un nombre de cailloux) quoi que fasse l'adversaire.
- Un joueur doit trouver ou deviner un objet caché, face à un adversaire qui peut s'adapter.
- Le plateau ou la situation a une symétrie évidente.
Techniques classiques¶
| Situation | Technique |
|---|---|
| Petit jeu fini | Tableau des positions gagnantes et perdantes, calculé à rebours |
| Plateau symétrique | Jouer le coup symétrique, ou apparier les coups |
| Tas d'objets | Restes modulo \(k + 1\) (Bachet), somme sans retenue (Nim) |
| Montrer que le premier joueur gagne, sans stratégie explicite | Vol de stratégie |
| « \(A\) peut garantir au moins \(M\) » | Une stratégie pour \(A\) et une stratégie pour \(B\) |
| Adversaire qui choisit au fur et à mesure | Faire jouer à l'adversaire le pire cas : il répond de façon à garder le plus d'options possible |
Exercices d'échauffement¶
- Jeu de Bachet : avec \(n\) allumettes et des retraits de \(1\) à \(k\), qui gagne ? Comment ?
- Deux joueurs annoncent à tour de rôle un entier de \(1\) à \(10\), qui s'ajoute au total. Celui qui fait atteindre exactement \(100\) gagne. Qui gagne ?
- Jeu de Nim avec trois tas de \(3\), \(4\) et \(5\) objets : qui gagne, et quel est le bon premier coup ?
- Une tablette de chocolat \(m \times n\) a son carré en bas à gauche empoisonné. À tour de rôle, chaque joueur choisit un carré restant et mange tous les carrés situés au-dessus et à droite de lui (lui compris). Celui qui mange le carré empoisonné perd. Montrer que le premier joueur a une stratégie gagnante si \(mn > 1\). Indication : vol de stratégie avec le carré en haut à droite.
- Deux joueurs placent à tour de rôle un jeton sur une case libre d'un échiquier \(8 \times 8\), sans jamais placer deux jetons sur des cases voisines par un côté. Celui qui ne peut plus jouer perd. Montrer que le second joueur gagne. Indication : la symétrie centrale.
Jeux dans la shortlist¶
- 2017 N2 : stratégie d'appariement ; Eduardo répond à chaque coup sur l'indice « jumeau ».
- 2018 C2 : Queenie joue la case opposée dans le cycle où Horst vient de jouer.
- 2024 C5 : on classe les positions en gagnantes et perdantes pour le joueur qui doit jouer.
- 2019 C7 : il faut une stratégie pour Alice avec \(M\) cailloux, et une stratégie pour Bob contre toute configuration d'au plus \(M - 1\) cailloux.
- 2025 A3 : des stratégies gloutonnes simples pour chacun des deux joueurs.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 4 (M. Aassila), p. 341 et 342 (généralités, positions gagnantes et perdantes), p. 343 à 345 (jeux de type Nim, méthode de résolution, jeu de Bachet p. 344), p. 345 et 346 (jeu de Wythoff), p. 346 à 348 (exemples), p. 348 et 349 (jeux à un joueur), p. 350 à 362 (exercices de trois niveaux).
Problèmes de la shortlist¶
20 problèmes · difficulté moyenne : ★★★★★ (3,0) · dont 5 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 3 · 2 ★ : 3 · 3 ★ : 7 · 4 ★ : 4 · 5 ★ : 3
| Problème | Difficulté | Concepts |
|---|---|---|
| 2018 C2 · OIM P4 | ★☆☆☆☆ | Coloriages et pavages · Graphes : degrés, chemins, arbres |
| 2017 N2 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2009 C1 | ★☆☆☆☆ | Invariants et monovariants |
| 2025 A3 · OIM P5 | ★★☆☆☆ | Cauchy-Schwarz et lemme de Titu |
| 2024 C4 · OIM P5 | ★★☆☆☆ | - |
| 2022 C3 | ★★☆☆☆ | Coloriages et pavages · Principe des tiroirs |
| 2024 C5 | ★★★☆☆ | Récurrence et constructions récursives |
| 2023 C5 | ★★★☆☆ | Invariants et monovariants |
| 2017 C5 · OIM P3 | ★★★☆☆ | Invariants et monovariants |
| 2015 C4 | ★★★☆☆ | - |
| 2013 N5 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal |
| 2012 C4 | ★★★☆☆ | Invariants et monovariants · Principe extrémal |
| 2009 C5 | ★★★☆☆ | Invariants et monovariants |
| 2021 C6 | ★★★★☆ | Coloriages et pavages |
| 2019 C7 | ★★★★☆ | - |
| 2014 C8 | ★★★★☆ | Bijections et dénombrement · Invariants et monovariants |
| 2012 C6 · OIM P3 | ★★★★☆ | Invariants et monovariants · Bijections et dénombrement |
| 2025 A8 | ★★★★★ | Polynômes : racines, relations de Viète, factorisation · AM-GM et moyennes |
| 2020 C8 | ★★★★★ | Invariants et monovariants · Valuations p-adiques et lemme LTE |
| 2013 C8 | ★★★★★ | Invariants et monovariants · Récurrence et constructions récursives |