Invariants et monovariants¶
Domaine : Combinatoire · Niveau : débutant · Prérequis : aucun
L'idée¶
Quand un énoncé décrit une opération répétée (on efface des nombres, on déplace des jetons, on échange des éléments), on cherche une quantité qui se comporte simplement à chaque étape.
- Un invariant est une quantité qui ne change jamais. Il répond aux questions « peut-on atteindre telle position ? » : si l'invariant n'a pas la même valeur au départ et à l'arrivée, c'est impossible.
- Un monovariant est une quantité qui évolue toujours dans le même sens. Il répond aux questions « le processus s'arrête-t-il ? » : un entier positif qui décroît strictement ne peut pas décroître indéfiniment. Si la quantité change d'exactement \(1\) à chaque étape, elle compte aussi le nombre d'étapes.
Toute la difficulté est de trouver la bonne quantité. On l'invente en testant de petits cas et en se demandant ce que l'opération préserve.
Un monovariant en action
Dans un parlement, chaque député a au plus \(3\) ennemis. Montrer qu'on peut répartir les députés en deux chambres de sorte que chacun ait au plus \(1\) ennemi dans sa chambre.
On part d'une répartition quelconque et l'on regarde \(E\), le nombre de paires d'ennemis dans une même chambre. Si un député a au moins \(2\) ennemis dans sa chambre, il en a au plus \(1\) dans l'autre : en le changeant de chambre, \(E\) diminue d'au moins \(1\). Comme \(E\) est un entier positif, on ne peut pas recommencer indéfiniment : on s'arrête sur une répartition où chacun a au plus \(1\) ennemi dans sa chambre.
Exemple résolu¶
Problème
On écrit au tableau les nombres \(1, 2, \ldots, 10\). À chaque étape, on efface deux nombres \(a\) et \(b\) et l'on écrit à leur place \(a + b + ab\). Après \(9\) étapes, il reste un seul nombre. Lequel ?
Étape 1 : tester de petits cas. Avec \(1, 2\) : on obtient \(1 + 2 + 2 = 5\). Avec \(1, 2, 3\) : en combinant d'abord \(1\) et \(2\), on obtient \(5\), puis \(5 + 3 + 15 = 23\) ; en combinant d'abord \(2\) et \(3\), on obtient \(11\), puis \(1 + 11 + 11 = 23\). Le résultat semble ne pas dépendre de l'ordre. Et \(5 = 6 - 1 = 2 \cdot 3 - 1\), \(23 = 24 - 1 = 2 \cdot 3 \cdot 4 - 1\).
Étape 2 : trouver l'invariant. L'opération se factorise :
Donc le produit des \((1 + x)\) pour \(x\) au tableau ne change pas : on remplace les deux facteurs \((1 + a)(1 + b)\) par un seul facteur égal.
Étape 3 : conclure. Au départ, ce produit vaut \(2 \cdot 3 \cdots 11 = 11!\). À la fin, il ne reste qu'un nombre \(N\), et le produit vaut \(1 + N\). Donc \(N = 11! - 1 = 39\,916\,799\), quel que soit l'ordre des opérations.
Le réflexe : calculer de petits cas pour deviner ce qui ne bouge pas, puis chercher une écriture de l'opération (ici une factorisation) qui le rend évident.
Comment le reconnaître¶
- L'énoncé décrit des étapes, des coups ou des opérations répétées.
- On demande s'il est possible d'atteindre une configuration : souvent la réponse est non, et un invariant le prouve.
- On demande de montrer que le processus s'arrête, ou de compter le nombre minimal d'étapes.
- On demande de montrer que le résultat final ne dépend pas de l'ordre des opérations.
Invariants classiques¶
| Opération | Quantité à essayer |
|---|---|
| Remplacer des nombres par leur somme ou leur différence | La somme, ou sa parité |
| Remplacer \(a, b\) par \(a + b + ab\) | Le produit des \((1 + x)\) |
| Remplacer \(a, b\) par \(a - b\) | Le PGCD de tous les nombres |
| Déplacements sur une grille, pavages | Un coloriage (en damier ou en bandes), le nombre de cases de chaque couleur |
| Échanges dans une permutation | Le nombre d'inversions, ou sa parité |
| Jetons qui se déplacent | Une somme pondérée \(\sum w(\text{position})\), par exemple avec des puissances de \(2\) |
| Processus censé s'arrêter | Un entier positif qui décroît : somme des carrés, nombre de paires « mauvaises », nombre d'inversions |
| Valeurs entières modifiées | Les mêmes quantités modulo un nombre bien choisi (\(2\), \(3\), \(n\)) |
Exercices d'échauffement¶
- On écrit \(1, 2, \ldots, 20\) au tableau. À chaque étape, on remplace deux nombres \(a\) et \(b\) par \(a + b - 1\). Quel nombre reste-t-il à la fin ?
- On retire deux coins opposés d'un échiquier \(8 \times 8\). Peut-on paver les \(62\) cases restantes avec des dominos \(1 \times 2\) ?
- On part du triplet \((3, 4, 5)\). À chaque étape, on peut remplacer deux nombres \(a, b\) du triplet par \(\frac{a + b}{\sqrt{2}}\) et \(\frac{a - b}{\sqrt{2}}\). Peut-on atteindre \((4, 4, 4)\) ?
- On peut échanger deux nombres voisins d'une liste. Combien d'échanges faut-il, au minimum, pour passer de \(n, n - 1, \ldots, 1\) à \(1, 2, \ldots, n\) ?
- Sur un cercle, on place \(n\) entiers positifs ou nuls. À chaque étape, on remplace chacun par la valeur absolue de la différence avec son voisin de droite. Montrer que le maximum ne peut jamais augmenter.
Invariants dans la shortlist¶
- 2023 C1 : les parités de deux différences ne changent pas, ce qui impose \(3 \mid mn\).
- 2022 C2 : le nombre de blocs ne peut pas augmenter, et diminue dès qu'on déplace un bloc intérieur.
- 2017 C2 : une quantité qui varie d'exactement \(1\) à chaque échange donne une borne sur le nombre d'échanges.
- 2022 C6 : si toutes les piles sont divisibles par un entier impair \(d\) après un coup, elles l'étaient avant ; on remonte jusqu'au départ.
- 2018 C6, solution 2 : le résultat final ne dépend pas de l'ordre des coups, ce qui permet de les choisir à sa guise.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 3 (M. Aassila), p. 337 (le principe et une liste d'invariants à essayer : coloriages, expressions algébriques, inversions, symétries), p. 338 à 342 (exemples), p. 343 à 364 (exercices de trois niveaux) ; tome 4, p. 140 (méthode d'ajustement local, qui repose sur un monovariant).
Problèmes de la shortlist¶
55 problèmes · difficulté moyenne : ★★★★★ (2,8) · dont 10 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 10 · 2 ★ : 14 · 3 ★ : 15 · 4 ★ : 10 · 5 ★ : 6
| Problème | Difficulté | Concepts |
|---|---|---|
| 2025 A1 | ★☆☆☆☆ | Polynômes : racines, relations de Viète, factorisation |
| 2025 C2 | ★☆☆☆☆ | Valuations p-adiques et lemme LTE |
| 2024 C1 | ★☆☆☆☆ | Double comptage |
| 2023 C1 | ★☆☆☆☆ | Coloriages et pavages |
| 2022 C2 · OIM P1 | ★☆☆☆☆ | - |
| 2017 C1 | ★☆☆☆☆ | Coloriages et pavages |
| 2017 C2 | ★☆☆☆☆ | Double comptage |
| 2014 C2 | ★☆☆☆☆ | AM-GM et moyennes |
| 2012 C1 | ★☆☆☆☆ | - |
| 2009 C1 | ★☆☆☆☆ | Jeux et stratégies gagnantes |
| 2025 N3 · OIM P4 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE · Descente infinie et Vieta jumping |
| 2025 C4 | ★★☆☆☆ | Double comptage |
| 2024 C3 | ★★☆☆☆ | Double comptage · Principe extrémal · Récurrence et constructions récursives |
| 2022 C4 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler · Récurrence et constructions récursives · Polynômes à coefficients entiers |
| 2021 C3 · OIM P5 | ★★☆☆☆ | Coloriages et pavages |
| 2019 C3 · OIM P5 | ★★☆☆☆ | Récurrence et constructions récursives · Bijections et dénombrement |
| 2019 C4 | ★★☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Graphes : degrés, chemins, arbres · Récurrence et constructions récursives |
| 2017 C3 | ★★☆☆☆ | Récurrence et constructions récursives · Suites et récurrences · Bijections et dénombrement |
| 2015 N4 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Suites et récurrences |
| 2014 A2 | ★★☆☆☆ | Suites et récurrences |
| 2014 C4 | ★★☆☆☆ | Coloriages et pavages |
| 2012 A2 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2011 C2 | ★★☆☆☆ | Principe extrémal |
| 2006 C1 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2025 N5 | ★★★☆☆ | Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide |
| 2023 C4 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Récurrence et constructions récursives |
| 2023 C5 | ★★★☆☆ | Jeux et stratégies gagnantes |
| 2022 C6 | ★★★☆☆ | Récurrence et constructions récursives · Divisibilité, PGCD et algorithme d'Euclide |
| 2019 C5 · OIM P3 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Principe extrémal |
| 2019 C6 | ★★★☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Récurrence et constructions récursives |
| 2018 C5 | ★★★☆☆ | Double comptage |
| 2017 C5 · OIM P3 | ★★★☆☆ | Jeux et stratégies gagnantes |
| 2012 C4 | ★★★☆☆ | Jeux et stratégies gagnantes · Principe extrémal |
| 2011 C3 · OIM P2 | ★★★☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2011 C5 | ★★★☆☆ | Bijections et dénombrement |
| 2010 C4 · OIM P5 | ★★★☆☆ | Récurrence et constructions récursives |
| 2009 C5 | ★★★☆☆ | Jeux et stratégies gagnantes |
| 2007 C4 | ★★★☆☆ | Principe des tiroirs |
| 2006 C4 | ★★★☆☆ | Récurrence et constructions récursives |
| 2024 A6 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2024 C6 | ★★★★☆ | Récurrence et constructions récursives |
| 2022 C7 | ★★★★☆ | Principe des tiroirs |
| 2018 C6 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2016 C6 | ★★★★☆ | Graphes : degrés, chemins, arbres |
| 2014 C7 | ★★★★☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Double comptage |
| 2014 C8 | ★★★★☆ | Jeux et stratégies gagnantes · Bijections et dénombrement |
| 2012 C6 · OIM P3 | ★★★★☆ | Jeux et stratégies gagnantes · Bijections et dénombrement |
| 2010 C6 | ★★★★☆ | Principe extrémal |
| 2007 C6 · OIM P3 | ★★★★☆ | Graphes : degrés, chemins, arbres |
| 2020 C8 | ★★★★★ | Jeux et stratégies gagnantes · Valuations p-adiques et lemme LTE |
| 2017 C8 | ★★★★★ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2017 G8 | ★★★★★ | Graphes : degrés, chemins, arbres · Double comptage |
| 2014 C9 | ★★★★★ | Graphes : degrés, chemins, arbres · Double comptage |
| 2013 C8 | ★★★★★ | Jeux et stratégies gagnantes · Récurrence et constructions récursives |
| 2009 C8 | ★★★★★ | Récurrence et constructions récursives · Principe extrémal |