Principe des tiroirs¶
Domaine : combinatoire · Niveau : débutant · Prérequis : aucun
L'idée¶
Si l'on range \(n + 1\) chaussettes dans \(n\) tiroirs, au moins un tiroir contient deux chaussettes.
Plus généralement : si l'on range \(N\) objets dans \(k\) tiroirs, un tiroir contient au moins \(\left\lceil \frac{N}{k} \right\rceil\) objets.
Le principe est évident. Toute la difficulté est de choisir les bons tiroirs.
Exemple résolu¶
Problème
On place 5 points dans un carré de côté 2. Montrer que deux d'entre eux sont à distance au plus \(\sqrt{2}\).
Étape 1 : trouver les tiroirs. On coupe le carré en 4 petits carrés de côté 1. Ce sont nos 4 tiroirs.
Étape 2 : appliquer le principe. 5 points dans 4 petits carrés : un petit carré contient au moins 2 points.
Étape 3 : conclure. Deux points d'un même carré de côté 1 sont à distance au plus sa diagonale, soit \(\sqrt{2}\).
Comment le reconnaître¶
- L'énoncé demande de prouver qu'il existe deux objets qui ont une propriété commune.
- Il y a « un objet de plus » que de cas possibles, ou le nombre d'objets est grand devant le nombre de cas.
- Les objets peuvent être classés selon un reste, une couleur, une région ou une parité.
Tiroirs classiques¶
| Situation | Tiroirs |
|---|---|
| Entiers et divisibilité | Restes modulo \(n\) |
| Points dans une figure | Petites régions de la figure |
| Sommes partielles \(a_1, a_1 + a_2, \dots\) | Restes de ces sommes modulo \(n\) |
| Sous-ensembles | Paires \(\{x, 2x\}\) ou autres groupements bien choisis |
Exercices d'échauffement¶
- Montrer que parmi 13 personnes, deux sont nées le même mois.
- Montrer que parmi \(n + 1\) entiers, deux ont une différence divisible par \(n\).
- Montrer que parmi \(n + 1\) entiers choisis dans \(\{1, 2, \dots, 2n\}\), deux sont consécutifs.
Pour aller plus loin : moyenne, tiroirs infinis, suites monotones¶
Le principe de la moyenne¶
Parmi des réels \(a_1, \ldots, a_n\) de moyenne \(A\), l'un au moins est \(\geq A\) et l'un au moins est \(\leq A\). C'est la version « continue » des tiroirs : on n'a plus besoin d'objets à ranger, seulement d'une somme connue.
Exemple
On place les nombres \(1, 2, \ldots, 10\) sur un cercle, dans un ordre quelconque. Montrer que trois nombres consécutifs ont une somme au moins égale à \(17\).
Il y a \(10\) triplets de nombres consécutifs, et chaque nombre appartient à exactement \(3\) d'entre eux. La somme des \(10\) sommes de triplets vaut donc \(3 \times (1 + \cdots + 10) = 165\), de moyenne \(16{,}5\). Un triplet a une somme \(\geq 16{,}5\), donc \(\geq 17\) puisque c'est un entier.
On reconnaît un double comptage suivi de la moyenne : c'est la combinaison la plus fréquente. En choisissant mieux les triplets (on met le nombre \(1\) à part et l'on découpe les neuf autres en trois blocs), la même idée donne même \(18\), et cette borne est optimale.
Le principe des tiroirs infini¶
Si l'on range une infinité d'objets dans un nombre fini de tiroirs, un tiroir en contient une infinité.
Application typique : une suite définie par une récurrence, dont chaque terme ne dépend que des \(k\) précédents et ne prend qu'un nombre fini de valeurs, est périodique à partir d'un certain rang. Par exemple, la suite de Fibonacci modulo \(n\) : il n'y a que \(n^2\) couples possibles de restes consécutifs \((F_i \bmod n, F_{i+1} \bmod n)\), donc un couple revient, et à partir de là tout se répète.
Le théorème d'Erdős-Szekeres¶
Toute suite de \(mn + 1\) réels distincts contient une sous-suite croissante de longueur \(m + 1\) ou une sous-suite décroissante de longueur \(n + 1\).
Pourquoi. On associe à chaque terme \(x_i\) la longueur \(\ell_i\) de la plus longue sous-suite croissante qui se termine en \(x_i\). Si toutes les \(\ell_i\) valent au plus \(m\), il y a \(mn + 1\) termes pour \(m\) valeurs possibles : \(n + 1\) termes ont la même valeur de \(\ell\). Ces termes forment une sous-suite décroissante, car si \(i < j\) et \(x_i < x_j\), on aurait \(\ell_j \geq \ell_i + 1\).
Le point clé est de fabriquer les tiroirs : ici ce sont les valeurs d'une étiquette inventée pour l'occasion.
Dans la shortlist¶
- 2025 A6 : une suite bornée vérifiant les conditions serait périodique, car un bloc de termes consécutifs détermine tous les précédents.
- 2024 C7, solution 2 : un système déterministe qui n'a qu'un nombre fini d'états est périodique à partir d'un certain rang.
- 2021 C1 : un entier n'a qu'un nombre fini de diviseurs, donc parmi une infinité de PGCD, l'un revient une infinité de fois.
- 2019 N4 : un quotient borné prend une même valeur une infinité de fois.
Pour approfondir : Objectif Olympiades de Mathématiques, tome 3 (M. Aassila), p. 163 et 164 (le principe et sa forme généralisée), p. 165 (principe des tiroirs infini), p. 165 à 170 (exemples, dont le théorème d'Erdős-Szekeres p. 169 et la suite de Fibonacci modulo \(10\)), p. 171 (principe de la valeur moyenne), p. 172 à 210 (exercices de trois niveaux).
Problèmes de la shortlist¶
Du plus accessible au plus difficile. Cette liste est mise à jour automatiquement à partir des étiquettes des problèmes.
63 problèmes · difficulté moyenne : ★★★★★ (2,9) · dont 14 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 11 · 2 ★ : 19 · 3 ★ : 10 · 4 ★ : 13 · 5 ★ : 10
| Problème | Difficulté | Concepts |
|---|---|---|
| 2025 C1 · OIM P1 | ★☆☆☆☆ | Récurrence et constructions récursives · Géométrie combinatoire : enveloppe convexe, points du réseau |
| 2025 N1 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2023 C2 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2021 A1 | ★☆☆☆☆ | Principe extrémal |
| 2021 C1 | ★☆☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2021 C2 | ★☆☆☆☆ | Récurrence et constructions récursives · Coloriages et pavages |
| 2021 N2 · OIM P1 | ★☆☆☆☆ | Graphes : degrés, chemins, arbres |
| 2020 C2 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2016 A2 | ★☆☆☆☆ | - |
| 2015 C2 · OIM P1 | ★☆☆☆☆ | Géométrie combinatoire : enveloppe convexe, points du réseau · Double comptage · Graphes : degrés, chemins, arbres |
| 2013 C1 | ★☆☆☆☆ | Récurrence et constructions récursives |
| 2025 A4 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal |
| 2023 C3 · OIM P5 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2022 C3 | ★★☆☆☆ | Coloriages et pavages · Jeux et stratégies gagnantes |
| 2020 C3 · OIM P4 | ★★☆☆☆ | - |
| 2020 G4 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2019 N3 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2019 N4 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide |
| 2017 A3 | ★★☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2017 N3 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2017 C4 · OIM P5 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2016 A3 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2014 C3 · OIM P2 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2014 N3 · OIM P5 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2013 A2 | ★★☆☆☆ | Principe extrémal |
| 2011 N2 | ★★☆☆☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Valuations p-adiques et lemme LTE |
| 2011 C4 | ★★☆☆☆ | Double comptage · Graphes : degrés, chemins, arbres |
| 2010 C3 | ★★☆☆☆ | Coloriages et pavages |
| 2009 N2 | ★★☆☆☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2007 C1 | ★★☆☆☆ | Récurrence et constructions récursives |
| 2021 C5 | ★★★☆☆ | Double comptage |
| 2015 C5 · OIM P6 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Double comptage · AM-GM et moyennes |
| 2013 C4 | ★★★☆☆ | Principe extrémal · Double comptage |
| 2013 C5 | ★★★☆☆ | Suites et récurrences |
| 2012 A4 | ★★★☆☆ | Polynômes à coefficients entiers · Polynômes : racines, relations de Viète, factorisation |
| 2010 C2 | ★★★☆☆ | Graphes : degrés, chemins, arbres · Récurrence et constructions récursives |
| 2010 N4 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois |
| 2008 C3 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal |
| 2007 N3 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler · Double comptage |
| 2007 C4 | ★★★☆☆ | Invariants et monovariants |
| 2025 A6 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide · Suites et récurrences |
| 2024 N6 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Résidus quadratiques · Double comptage |
| 2024 C7 · OIM P3 | ★★★★☆ | Principe extrémal |
| 2023 A6 · OIM P3 | ★★★★☆ | Principe extrémal · Polynômes : racines, relations de Viète, factorisation · Polynômes à coefficients entiers · Descente infinie et Vieta jumping |
| 2022 N6 | ★★★★☆ | Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs |
| 2022 C7 | ★★★★☆ | Invariants et monovariants |
| 2021 A6 · OIM P6 | ★★★★☆ | - |
| 2018 N6 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2015 N6 | ★★★★☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2013 C6 | ★★★★☆ | Graphes : degrés, chemins, arbres · Principe extrémal |
| 2012 A6 | ★★★★☆ | Suites et récurrences · Principe extrémal |
| 2010 A7 · OIM P6 | ★★★★☆ | Suites et récurrences · Principe extrémal |
| 2007 N7 | ★★★★☆ | Valuations p-adiques et lemme LTE |
| 2022 A8 | ★★★★★ | Suites et récurrences · Bijections et dénombrement |
| 2022 N8 | ★★★★★ | Principe extrémal · Congruences, théorèmes de Fermat et d'Euler · Résidus quadratiques |
| 2021 C8 | ★★★★★ | Récurrence et constructions récursives |
| 2020 N7 | ★★★★★ | Récurrence et constructions récursives |
| 2019 G8 | ★★★★★ | Chasse aux angles et quadrilatères cycliques · Outils projectifs : birapport, division harmonique, pôles et polaires |
| 2016 C8 | ★★★★★ | Coloriages et pavages · Graphes : degrés, chemins, arbres |
| 2016 N8 | ★★★★★ | Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler · Polynômes : racines, relations de Viète, factorisation · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme |
| 2015 N8 | ★★★★★ | Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler |
| 2012 C7 | ★★★★★ | Graphes : degrés, chemins, arbres · Récurrence et constructions récursives |
| 2009 C7 · OIM P6 | ★★★★★ | Récurrence et constructions récursives · Principe extrémal |