Récurrence et constructions récursives¶
Domaine : Combinatoire · Niveau : débutant · Prérequis : aucun
L'idée¶
En combinatoire, un objet de taille \(n\) contient presque toujours des objets plus petits du même type : un graphe privé d'un sommet, un tableau privé d'une ligne, un groupe privé d'une personne. On en tire deux méthodes.
- Prouver par récurrence. Pour établir une propriété au rang \(n\), on retire un objet bien choisi, on applique l'hypothèse de récurrence à ce qui reste, puis on remet l'objet retiré. Le choix de l'objet à retirer est souvent toute la difficulté : un objet extrême (le plus grand, une extrémité, un sommet de petit degré), pour que le remettre ne casse rien.
- Construire récursivement. Pour fabriquer un objet de taille \(n\), on assemble des objets plus petits déjà construits : on ajoute un élément, on recolle deux morceaux, ou l'on double la taille avec des copies.
Une troisième variante sert à compter : on exprime le nombre \(P_n\) d'objets de taille \(n\) en fonction de \(P_{n-1}, P_{n-2}, \ldots\), en distinguant les cas selon le premier ou le dernier élément. Voir aussi Suites et récurrences.
Rappels : la récurrence forte suppose la propriété vraie pour tous les rangs inférieurs, et un énoncé renforcé est parfois plus facile à prouver, car l'hypothèse de récurrence devient plus forte.
Exemple résolu¶
Problème
On retire une case quelconque d'un échiquier \(2^n \times 2^n\). Montrer que les cases restantes peuvent être pavées par des triminos en forme de L (trois cases formant un coin \(2 \times 2\) privé d'une case).
Étape 1 : initialiser. Pour \(n = 1\), un carré \(2 \times 2\) privé d'une case est un trimino en L.
Étape 2 : découper en copies plus petites. Supposons le résultat vrai pour \(2^{n-1} \times 2^{n-1}\). On coupe l'échiquier \(2^n \times 2^n\) en quatre quarts de taille \(2^{n-1} \times 2^{n-1}\). La case retirée se trouve dans l'un d'eux ; les trois autres sont complets.
Étape 3 : se ramener à l'hypothèse. On place un trimino au centre de l'échiquier, sur les trois cases centrales qui appartiennent aux trois quarts complets (une case dans chacun). Maintenant, chacun des quatre quarts a exactement une case indisponible : la case retirée pour l'un, une case du trimino central pour les trois autres.
Étape 4 : conclure. Par hypothèse de récurrence, chaque quart privé d'une case se pave par des triminos. Avec le trimino central, on obtient un pavage de tout l'échiquier privé de la case retirée.
Le trimino central a été placé pour que chaque morceau soit une copie exacte du problème de départ, en plus petit. C'est le cœur de toute construction récursive.
Comment le reconnaître¶
- L'énoncé porte sur tout entier \(n\), et les objets de taille \(n\) contiennent naturellement des objets de taille \(n - 1\).
- On demande de construire un objet ou de montrer qu'il existe une configuration pour tout \(n\).
- Les tailles sont des puissances de \(2\) : penser à couper en deux ou à doubler.
- Un dénombrement dont les premières valeurs ressemblent à Fibonacci, à \(2^n\) ou à \(n!\).
- On doit faire des choix successifs (des signes, des couleurs, des places) : les faire un par un en maintenant une propriété (méthode gloutonne).
Techniques classiques¶
| Situation | Technique |
|---|---|
| Propriété d'une configuration de \(n\) objets | Retirer un objet extrême, appliquer l'hypothèse, le remettre |
| Taille \(2^k\) | Couper en deux ou en quatre ; ou construire à partir de copies décalées |
| Compter des suites ou des pavages | Distinguer selon le premier élément : \(P_n = P_{n-1} + P_{n-2}\), etc. |
| Construction pour tout \(n\) | Passer de \(n\) à \(n + 1\), \(n + 2\) ou \(2n\) ; traiter les petits cas et les parités à part |
| Choix successifs | Glouton : chaque choix préserve un invariant (par exemple des sommes partielles bornées) |
| La récurrence ne passe pas | Renforcer l'énoncé, ou passer à la récurrence forte |
Exercices d'échauffement¶
- Tours de Hanoï : montrer qu'il faut au moins \(2^n - 1\) mouvements pour déplacer \(n\) disques, et que c'est possible.
- Montrer que \(n\) droites en position générale (deux à deux non parallèles, trois jamais concourantes) découpent le plan en \(1 + \frac{n(n+1)}{2}\) régions.
- Combien y a-t-il de façons de paver un rectangle \(2 \times n\) avec des dominos \(1 \times 2\) ?
- Montrer que tout entier \(n \geq 8\) s'écrit \(3a + 5b\) avec \(a, b\) entiers positifs ou nuls. Indication : récurrence forte à partir de \(8, 9, 10\).
- Dans un tournoi (chacun rencontre chacun, sans match nul), montrer qu'on peut ranger les joueurs en une file \(J_1, J_2, \ldots, J_n\) où chacun a battu le suivant. Indication : insérer le nouveau joueur.
Récurrence dans la shortlist¶
- 2024 C2 : à partir d'un bon remplissage du tableau \(2^k \times 2^k\), on en recopie quatre exemplaires décalés, comme dans l'exemple résolu.
- 2020 C1, solution 1 : le nombre de permutations valables vérifie \(P_n = P_{n-1} + P_{n-2}\).
- 2020 C2 : on retire quatre sommets consécutifs bien choisis et l'on applique l'hypothèse au polygone restant.
- 2023 C2 : on choisit les signes un par un pour garder les sommes partielles dans un intervalle fixé.
- 2015 C1, solution 1 : une récurrence forte où le plus grand bulldozer permet de supprimer tout un côté.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 3 (M. Aassila), p. 273 (récurrence simple, double et forte), p. 274 et 275 (exemples, dont le principe des tiroirs prouvé par récurrence), p. 276 à 281 (suites récurrentes en combinatoire), p. 282 à 287 (récursivité : découper en sous-problèmes du même type, avec exemples), p. 288 à 336 (exercices de trois niveaux) ; tome 4, p. 143 à 146 (méthodes de construction).
Problèmes de la shortlist¶
97 problèmes · difficulté moyenne : ★★★★★ (2,7) · dont 19 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 22 · 2 ★ : 28 · 3 ★ : 16 · 4 ★ : 17 · 5 ★ : 14
| Problème | Difficulté | Concepts |
|---|---|---|
| 2025 C1 · OIM P1 | ★☆☆☆☆ | Principe des tiroirs · Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2024 A1 · OIM P1 | ★☆☆☆☆ | Partie entière et majorations · Congruences, théorèmes de Fermat et d'Euler |
| 2024 A2 | ★☆☆☆☆ | Principe extrémal · Bijections et dénombrement |
| 2024 C2 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2023 N1 · OIM P1 | ★☆☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Valuations p-adiques et lemme LTE |
| 2023 C2 | ★☆☆☆☆ | Principe des tiroirs |
| 2022 C1 | ★☆☆☆☆ | Principe extrémal |
| 2022 A2 | ★☆☆☆☆ | - |
| 2021 C2 | ★☆☆☆☆ | Principe des tiroirs · Coloriages et pavages |
| 2020 C1 | ★☆☆☆☆ | Bijections et dénombrement |
| 2020 C2 | ★☆☆☆☆ | Principe des tiroirs |
| 2019 C1 | ★☆☆☆☆ | Bijections et dénombrement |
| 2019 C2 | ★☆☆☆☆ | Principe extrémal |
| 2018 C1 | ★☆☆☆☆ | - |
| 2015 C1 | ★☆☆☆☆ | Principe extrémal |
| 2014 C1 | ★☆☆☆☆ | Double comptage |
| 2013 C1 | ★☆☆☆☆ | Principe des tiroirs |
| 2013 C2 · OIM P2 | ★☆☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Principe extrémal |
| 2013 N2 · OIM P1 | ★☆☆☆☆ | Sommes, télescopage et transformation d'Abel · Congruences, théorèmes de Fermat et d'Euler |
| 2012 C2 | ★☆☆☆☆ | Double comptage |
| 2011 C1 · OIM P4 | ★☆☆☆☆ | Bijections et dénombrement |
| 2009 A1 | ★☆☆☆☆ | Principe extrémal |
| 2025 C3 | ★★☆☆☆ | - |
| 2024 C3 | ★★☆☆☆ | Double comptage · Invariants et monovariants · Principe extrémal |
| 2024 A4 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Partie entière et majorations · Principe extrémal |
| 2023 C3 · OIM P5 | ★★☆☆☆ | Principe des tiroirs |
| 2022 C4 | ★★☆☆☆ | Invariants et monovariants · Congruences, théorèmes de Fermat et d'Euler · Polynômes à coefficients entiers |
| 2021 A3 | ★★☆☆☆ | Partie entière et majorations · Sommes, télescopage et transformation d'Abel |
| 2020 G4 | ★★☆☆☆ | Principe des tiroirs |
| 2019 C3 · OIM P5 | ★★☆☆☆ | Invariants et monovariants · Bijections et dénombrement |
| 2019 C4 | ★★☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Graphes : degrés, chemins, arbres · Invariants et monovariants |
| 2018 G3 | ★★☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2018 N3 | ★★☆☆☆ | - |
| 2017 C3 | ★★☆☆☆ | Suites et récurrences · Invariants et monovariants · Bijections et dénombrement |
| 2017 C4 · OIM P5 | ★★☆☆☆ | Principe des tiroirs |
| 2016 A3 | ★★☆☆☆ | Principe des tiroirs |
| 2014 N1 | ★★☆☆☆ | Principe extrémal · Congruences, théorèmes de Fermat et d'Euler |
| 2014 A3 | ★★☆☆☆ | Principe extrémal |
| 2014 C3 · OIM P2 | ★★☆☆☆ | Principe des tiroirs |
| 2014 N3 · OIM P5 | ★★☆☆☆ | Principe des tiroirs |
| 2013 C3 | ★★☆☆☆ | Graphes : degrés, chemins, arbres · Coloriages et pavages |
| 2012 A1 · OIM P4 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2010 C1 | ★★☆☆☆ | Bijections et dénombrement |
| 2010 A4 | ★★☆☆☆ | Suites et récurrences |
| 2009 C2 | ★★☆☆☆ | Double comptage |
| 2008 C2 | ★★☆☆☆ | Bijections et dénombrement |
| 2007 C1 | ★★☆☆☆ | Principe des tiroirs |
| 2006 C1 | ★★☆☆☆ | Invariants et monovariants |
| 2006 A2 | ★★☆☆☆ | Suites et récurrences |
| 2006 C2 · OIM P2 | ★★☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2024 C5 | ★★★☆☆ | Jeux et stratégies gagnantes |
| 2023 C4 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Invariants et monovariants |
| 2022 C6 | ★★★☆☆ | Invariants et monovariants · Divisibilité, PGCD et algorithme d'Euclide |
| 2019 C6 | ★★★☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Invariants et monovariants |
| 2016 C5 | ★★★☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Principe extrémal |
| 2014 A4 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Congruences, théorèmes de Fermat et d'Euler |
| 2013 A4 | ★★★☆☆ | Double comptage · Graphes : degrés, chemins, arbres |
| 2011 A4 | ★★★☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal |
| 2011 A5 | ★★★☆☆ | - |
| 2010 C2 | ★★★☆☆ | Principe des tiroirs · Graphes : degrés, chemins, arbres |
| 2010 C4 · OIM P5 | ★★★☆☆ | Invariants et monovariants |
| 2009 C3 | ★★★☆☆ | Suites et récurrences |
| 2008 N3 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2008 G5 | ★★★☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2006 C4 | ★★★☆☆ | Invariants et monovariants |
| 2006 C5 | ★★★☆☆ | Graphes : degrés, chemins, arbres |
| 2025 N6 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide · Théorème des restes chinois |
| 2025 A7 | ★★★★☆ | Partie entière et majorations |
| 2024 C6 | ★★★★☆ | Invariants et monovariants |
| 2023 C6 | ★★★★☆ | Coloriages et pavages |
| 2022 N7 · OIM P3 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Polynômes : racines, relations de Viète, factorisation |
| 2021 N6 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler |
| 2020 C7 | ★★★★☆ | - |
| 2017 C6 | ★★★★☆ | Double comptage |
| 2015 N7 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois |
| 2014 C6 | ★★★★☆ | Principe extrémal |
| 2012 N7 · OIM P6 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2009 C6 | ★★★★☆ | Coloriages et pavages |
| 2008 C6 | ★★★★☆ | Double comptage |
| 2007 A7 · OIM P6 | ★★★★☆ | Polynômes : racines, relations de Viète, factorisation |
| 2007 C7 | ★★★★☆ | Bijections et dénombrement |
| 2006 C6 | ★★★★☆ | Coloriages et pavages · Principe extrémal |
| 2006 N7 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois |
| 2024 C8 | ★★★★★ | Graphes : degrés, chemins, arbres · Coloriages et pavages · Principe extrémal |
| 2023 A7 | ★★★★★ | Partie entière et majorations |
| 2021 C8 | ★★★★★ | Principe des tiroirs |
| 2020 N7 | ★★★★★ | Principe des tiroirs |
| 2019 C9 | ★★★★★ | Principe extrémal |
| 2015 C7 | ★★★★★ | Graphes : degrés, chemins, arbres · Coloriages et pavages · Principe extrémal |
| 2013 C7 · OIM P6 | ★★★★★ | Bijections et dénombrement · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs |
| 2013 N7 | ★★★★★ | Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · Partie entière et majorations · Bijections et dénombrement |
| 2013 C8 | ★★★★★ | Jeux et stratégies gagnantes · Invariants et monovariants |
| 2012 C7 | ★★★★★ | Graphes : degrés, chemins, arbres · Principe des tiroirs |
| 2011 C7 | ★★★★★ | Double comptage · Coloriages et pavages |
| 2010 C7 | ★★★★★ | Graphes : degrés, chemins, arbres · Théorème des restes chinois |
| 2009 C7 · OIM P6 | ★★★★★ | Principe extrémal · Principe des tiroirs |
| 2009 C8 | ★★★★★ | Invariants et monovariants · Principe extrémal |