Principe extrémal¶
Domaine : Combinatoire · Niveau : débutant · Prérequis : aucun
L'idée¶
Pour montrer qu'un objet ayant une certaine propriété existe, on considère l'objet qui maximise ou minimise une quantité bien choisie. Puis on montre que s'il n'avait pas la propriété, une petite modification donnerait un objet encore meilleur, ce qui contredit son caractère extrémal.
L'objet extrémal existe toujours dans deux situations :
- un ensemble fini non vide a un plus grand et un plus petit élément ;
- toute partie non vide de \(\mathbb{N}\) a un plus petit élément.
Attention aux ensembles infinis de réels, qui n'ont pas forcément de maximum.
Le principe prend trois formes courantes :
- Le plus grand ou le plus petit élément : la plus grande valeur, le point le plus à gauche, le sommet de plus grand degré.
- La configuration optimale : parmi toutes les dispositions possibles, celle qui minimise une somme, une longueur, un nombre de « mauvaises » paires. Toute modification locale ne peut que l'empirer, ce qui donne des inégalités.
- Le plus petit contre-exemple : si l'énoncé est faux, on en prend un contre-exemple minimal et l'on en fabrique un plus petit. C'est la récurrence vue à l'envers, et la descente infinie en théorie des nombres.
Toute la difficulté est de choisir la quantité à optimiser.
Exemple résolu¶
Problème
Dans un tournoi, chaque joueur rencontre chaque autre joueur exactement une fois, et il n'y a pas de match nul. Montrer qu'il existe un joueur \(A\) tel que tout autre joueur a perdu soit contre \(A\), soit contre un joueur qui a perdu contre \(A\).
Étape 1 : choisir l'objet extrémal. On prend pour \(A\) un joueur qui a remporté le plus de victoires. Notons \(V\) l'ensemble des joueurs battus par \(A\), de sorte que \(A\) a \(|V|\) victoires.
Étape 2 : supposer le contraire. Soit \(B\) un joueur qui n'a perdu ni contre \(A\), ni contre aucun joueur de \(V\). Alors \(B\) a battu \(A\), et \(B\) a battu tous les joueurs de \(V\).
Étape 3 : contredire l'extrémalité. \(B\) a donc au moins \(|V| + 1\) victoires, plus que \(A\). C'est impossible, puisque \(A\) a le plus de victoires. Le joueur \(A\) convient.
Le choix « le plus de victoires » vient de la conclusion voulue : on veut que \(A\) domine beaucoup de joueurs, donc on prend celui qui en domine directement le plus.
Comment le reconnaître¶
- On doit montrer qu'il existe un objet (un point, un joueur, une case) ayant une propriété, dans une situation finie.
- L'énoncé parle de « plus grand », « plus long », « le plus proche », ou l'on peut naturellement ordonner les objets.
- Une configuration doit vérifier une condition d'équilibre (chaque nombre est la moyenne de ses voisins, chaque point est le plus proche de…) : on regarde l'élément maximal.
- Un énoncé « pour tout \(n\) » ou « pour tout ensemble » qui semble résister à une récurrence directe : on prend un contre-exemple minimal.
Choix extrémaux classiques¶
| Situation | Objet extrémal |
|---|---|
| Points du plan | Les deux points les plus éloignés, le triangle d'aire minimale, un sommet de l'enveloppe convexe |
| Graphe | Le sommet de plus grand degré, le plus long chemin (les voisins d'une extrémité sont sur le chemin), le plus petit cycle |
| Ensemble d'entiers ou de réels | Le plus grand ou le plus petit élément, le plus petit indice où une propriété échoue |
| Arrangement, permutation | Celui qui minimise une somme ; échanger deux éléments ne peut pas l'améliorer |
| Tournoi, compétition | Le joueur qui a le plus de victoires |
| Énoncé portant sur tous les entiers | Le plus petit contre-exemple |
Exercices d'échauffement¶
- Des entiers sont placés sur un cercle, et chacun est la moyenne de ses deux voisins. Montrer qu'ils sont tous égaux.
- Chaque case d'un échiquier infini contient un entier strictement positif égal à la moyenne des quatre cases voisines. Montrer que toutes les cases contiennent le même nombre.
- Dans un graphe fini, chaque sommet a au moins deux voisins. Montrer que le graphe contient un cycle. Indication : un plus long chemin.
- On donne un nombre fini de points du plan, non tous alignés. Montrer qu'on peut en choisir trois formant un triangle qui ne contient aucun autre point donné, ni à l'intérieur ni sur ses côtés.
- Montrer que \(\sqrt{2}\) est irrationnel en supposant \(\sqrt{2} = \frac{p}{q}\) avec \(q\) minimal.
Le principe extrémal dans la shortlist¶
- 2015 C1 : on considère le plus grand bulldozer, ou la ville la plus à gauche qui ne peut pas être balayée vers la droite.
- 2020 C4 : dans un cycle, l'arête la plus longue serait plus longue que la somme des autres.
- 2024 A2, solution 1 : une suite qui réalise le minimum est décroissante, sinon échanger deux termes diminue la somme.
- 2019 C5 : on prend un sous-graphe complet maximal, ou un plus petit cycle.
- 2020 N5 : le plus petit premier \(p\) avec \(f(p) \neq 0\), ou le plus petit contre-exemple.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 4 (M. Aassila), p. 5 à 7 (le principe, avec l'exemple du triangle d'aire maximale), p. 8 à 30 (méthodes pour les problèmes de maximum et de minimum : estimations d'espace, de blocs, globales, par paramètres, par double comptage), p. 31 à 36 (combinatoire et inégalités, théorème de Sperner p. 34), p. 37 à 40 (maximum et minimum en combinatoire), p. 41 à 54 (exercices de trois niveaux).
Problèmes de la shortlist¶
88 problèmes · difficulté moyenne : ★★★★★ (3,1) · dont 19 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 13 · 2 ★ : 16 · 3 ★ : 23 · 4 ★ : 22 · 5 ★ : 14
| Problème | Difficulté | Concepts |
|---|---|---|
| 2025 A2 | ★☆☆☆☆ | - |
| 2024 N1 | ★☆☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler |
| 2024 A2 | ★☆☆☆☆ | Récurrence et constructions récursives · Bijections et dénombrement |
| 2024 N2 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2022 C1 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2021 A1 | ★☆☆☆☆ | Principe des tiroirs |
| 2019 C2 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2017 N1 · OIM P1 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2016 C2 | ★☆☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs |
| 2015 C1 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2014 A1 · OIM P1 | ★☆☆☆☆ | Suites et récurrences |
| 2013 C2 · OIM P2 | ★☆☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Récurrence et constructions récursives |
| 2009 A1 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2025 A4 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe des tiroirs |
| 2024 C3 | ★★☆☆☆ | Double comptage · Invariants et monovariants · Récurrence et constructions récursives |
| 2024 A4 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Partie entière et majorations · Récurrence et constructions récursives |
| 2022 A4 | ★★☆☆☆ | - |
| 2020 N3 · OIM P5 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Valuations p-adiques et lemme LTE |
| 2020 C4 | ★★☆☆☆ | Graphes : degrés, chemins, arbres · Sommes, télescopage et transformation d'Abel |
| 2019 A3 | ★★☆☆☆ | - |
| 2017 A4 | ★★☆☆☆ | Suites et récurrences |
| 2014 N1 | ★★☆☆☆ | Récurrence et constructions récursives · Congruences, théorèmes de Fermat et d'Euler |
| 2014 A3 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2013 A2 | ★★☆☆☆ | Principe des tiroirs |
| 2013 N3 | ★★☆☆☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Divisibilité, PGCD et algorithme d'Euclide |
| 2011 C2 | ★★☆☆☆ | Invariants et monovariants |
| 2008 C1 | ★★☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2007 A1 · OIM P1 | ★★☆☆☆ | Suites et récurrences |
| 2007 C2 | ★★☆☆☆ | Coloriages et pavages |
| 2024 A5 | ★★★☆☆ | Sommes, télescopage et transformation d'Abel · AM-GM et moyennes · Suites et récurrences |
| 2023 N5 | ★★★☆☆ | Suites et récurrences · Divisibilité, PGCD et algorithme d'Euclide |
| 2022 A5 | ★★★☆☆ | Polynômes : racines, relations de Viète, factorisation |
| 2022 C5 | ★★★☆☆ | Bijections et dénombrement |
| 2020 C5 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2020 N5 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE |
| 2019 C5 · OIM P3 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Invariants et monovariants |
| 2018 C4 · OIM P3 | ★★★☆☆ | - |
| 2016 C5 | ★★★☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Récurrence et constructions récursives |
| 2016 N5 | ★★★☆☆ | Descente infinie et Vieta jumping · Équations diophantiennes : factorisation et encadrement |
| 2014 C5 · OIM P6 | ★★★☆☆ | Double comptage · Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2013 C4 | ★★★☆☆ | Principe des tiroirs · Double comptage |
| 2013 N5 | ★★★☆☆ | Jeux et stratégies gagnantes · Divisibilité, PGCD et algorithme d'Euclide |
| 2012 C4 | ★★★☆☆ | Jeux et stratégies gagnantes · Invariants et monovariants |
| 2011 A4 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Récurrence et constructions récursives |
| 2011 N5 · OIM P5 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2009 A3 · OIM P5 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2009 A6 · OIM P3 | ★★★☆☆ | Suites et récurrences · Sommes, télescopage et transformation d'Abel |
| 2008 A3 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2008 C3 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Principe des tiroirs |
| 2008 C5 | ★★★☆☆ | Double comptage |
| 2007 A2 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2006 A3 | ★★★☆☆ | Suites et récurrences |
| 2025 C6 | ★★★★☆ | Graphes : degrés, chemins, arbres · Double comptage |
| 2024 A7 · OIM P6 | ★★★★☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Partie entière et majorations |
| 2024 C7 · OIM P3 | ★★★★☆ | Principe des tiroirs |
| 2023 A6 · OIM P3 | ★★★★☆ | Polynômes : racines, relations de Viète, factorisation · Principe des tiroirs · Polynômes à coefficients entiers · Descente infinie et Vieta jumping |
| 2021 G6 | ★★★★☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2021 N7 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide · Suites et récurrences |
| 2020 A6 | ★★★★☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide |
| 2020 C6 · OIM P3 | ★★★★☆ | Graphes : degrés, chemins, arbres |
| 2017 A7 | ★★★★☆ | Suites et récurrences |
| 2017 C7 | ★★★★☆ | - |
| 2015 C6 | ★★★★☆ | Bijections et dénombrement |
| 2014 C6 | ★★★★☆ | Récurrence et constructions récursives |
| 2013 C6 | ★★★★☆ | Graphes : degrés, chemins, arbres · Principe des tiroirs |
| 2013 N6 | ★★★★☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Partie entière et majorations |
| 2012 A6 | ★★★★☆ | Suites et récurrences · Principe des tiroirs |
| 2012 A7 | ★★★★☆ | Polynômes : racines, relations de Viète, factorisation |
| 2011 C6 | ★★★★☆ | Double comptage |
| 2010 A6 | ★★★★☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2010 C6 | ★★★★☆ | Invariants et monovariants |
| 2010 A7 · OIM P6 | ★★★★☆ | Suites et récurrences · Principe des tiroirs |
| 2009 G5 | ★★★★☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · AM-GM et moyennes |
| 2006 C6 | ★★★★☆ | Coloriages et pavages · Récurrence et constructions récursives |
| 2025 C8 · OIM P6 | ★★★★★ | Coloriages et pavages · Double comptage · AM-GM et moyennes · Graphes : degrés, chemins, arbres |
| 2024 A8 | ★★★★★ | Divisibilité, PGCD et algorithme d'Euclide · Suites et récurrences |
| 2024 C8 | ★★★★★ | Récurrence et constructions récursives · Graphes : degrés, chemins, arbres · Coloriages et pavages |
| 2023 C7 | ★★★★★ | Graphes : degrés, chemins, arbres |
| 2022 N8 | ★★★★★ | Principe des tiroirs · Congruences, théorèmes de Fermat et d'Euler · Résidus quadratiques |
| 2020 G9 · OIM P6 | ★★★★★ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2019 A7 | ★★★★★ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Valuations p-adiques et lemme LTE |
| 2019 N8 | ★★★★★ | Partie entière et majorations · Équations diophantiennes : factorisation et encadrement · Descente infinie et Vieta jumping |
| 2019 C9 | ★★★★★ | Récurrence et constructions récursives |
| 2017 A8 | ★★★★★ | - |
| 2015 C7 | ★★★★★ | Graphes : degrés, chemins, arbres · Coloriages et pavages · Récurrence et constructions récursives |
| 2015 G8 | ★★★★★ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2009 C7 · OIM P6 | ★★★★★ | Récurrence et constructions récursives · Principe des tiroirs |
| 2009 C8 | ★★★★★ | Invariants et monovariants · Récurrence et constructions récursives |