S’il y a plus de pigeons que de pigeonniers, au moins un pigeonnier contient plus d’un pigeon.
1. L’idée fondamentale
Le principe des tiroirs, appelé aussi principe des pigeonniers ou principe de Dirichlet, découle d’une observation très simple : si l’on répartit plus d’objets que de récipients, au moins un récipient recevra plus d’un objet. Sa force apparaît lorsque les « pigeons » et les « pigeonniers » sont cachés : personnes et mois, nombres et restes, points et régions géométriques, sous-ensembles et sommes, nombres et parties impaires.
- Pigeons = les objets que nous répartissons.
- Pigeonniers = les catégories dans lesquelles nous les classons.
2. Forme générale
Si N objets sont répartis dans k récipients, au moins un récipient contient au moins ⌈N / k⌉, où ⌈x⌉ désigne le plus petit entier supérieur ou égal à x. Par exemple, en répartissant 25 personnes entre les 12 mois de l’année, au moins un mois compte au moins 3 personnes, car 25/12 est supérieur à 2.
3. Formule inverse
Combien d’objets faut-il pour être certain qu’au moins un pigeonnier en contienne r ? Nous pouvons placer au maximum r − 1 objets dans chacun des k pigeonniers sans atteindre r. Le maximum est k(r − 1) ; l’objet suivant impose le résultat : k(r − 1) + 1.
4. La méthode du pire cas
De nombreux problèmes se résolvent en imaginant la répartition la plus défavorable : on évite le résultat demandé aussi longtemps que possible, puis on ajoute un dernier objet. En résumé : maximum possible sans atteindre l’objectif + 1.
5. Vingt-cinq problèmes résolus
Problème 1 - Les mois
Une classe compte 13 élèves. Montrer qu’au moins deux sont nés le même mois.
Solution
Les 13 personnes sont les pigeons et les 12 mois les pigeonniers. Puisque 13 > 12, au moins un mois contient au moins deux anniversaires.
Problème 2 - Trois personnes nées le même mois
Combien de personnes faut-il pour être certain qu’au moins 3 sont nées le même mois ?
Solution
On peut placer au maximum 2 personnes dans chacun des 12 mois : 12 × 2 = 24. La vingt-cinquième oblige un mois à en contenir 3. Réponse : 25.
Problème 3 - Des chaussettes dans le noir
Un tiroir contient des chaussettes de 5 couleurs différentes. Combien faut-il en prendre dans le noir pour être certain d’en avoir au moins deux de la même couleur ?
Solution
Dans le pire des cas, les 5 premières chaussettes ont toutes une couleur différente. La sixième répète nécessairement l’une de ces 5 couleurs. Réponse : 6.
Problème 4 - Quatre chaussettes de la même couleur
Il y a des chaussettes de 6 couleurs. Combien faut-il en tirer pour être certain d’en avoir au moins 4 de la même couleur ?
Solution
On peut en tirer 3 de chaque couleur sans en avoir 4 identiques : 6 × 3 = 18. La suivante impose une quatrième chaussette d’une couleur. Réponse : 19.
Problème 5 - Restes modulo 5
On choisit 6 entiers quelconques. Montrer qu’au moins deux ont le même reste dans la division par 5.
Solution
Les restes possibles sont 0, 1, 2, 3, 4 : seulement 5 pigeonniers. Avec 6 entiers, deux ont nécessairement le même reste.
Problème 6 - Une différence multiple de 5
Montrer que parmi 6 entiers il en existe toujours deux dont la différence est divisible par 5.
Solution
D’après le problème précédent, deux entiers ont le même reste modulo 5. Si a = 5q + r et b = 5p + r, alors a − b = 5(q − p) : leur différence est multiple de 5.
Problème 7 - Les jours de la semaine
Dans un groupe de 15 personnes, montrer qu’au moins 3 sont nées le même jour de la semaine.
Solution
Si chacun des 7 jours comptait au plus 2 personnes, il y aurait au plus 7 × 2 = 14 personnes. La quinzième impose au moins 3 personnes pour un jour.
Problème 8 - Dernier chiffre
On choisit 11 nombres naturels. Montrer qu’au moins deux se terminent par le même chiffre.
Solution
Les derniers chiffres possibles sont 0, 1, 2, …, 9 : dix possibilités. Avec 11 nombres, au moins deux ont le même dernier chiffre.
Problème 9 - Une différence multiple de 10
On choisit 11 entiers. Montrer que deux ont une différence multiple de 10.
Solution
Classons les nombres selon leur reste modulo 10. Il y a 10 classes ; avec 11 nombres, deux appartiennent à la même classe, donc leur différence est divisible par 10.
Problème 10 - Au moins cinq
Une école compte 101 élèves répartis dans 25 classes. Montrer qu’au moins une classe contient au moins 5 élèves.
Solution
Si chaque classe avait au plus 4 élèves, le total serait au plus 25 × 4 = 100. Comme il y a 101 élèves, au moins une classe en contient au moins 5.
Problème 11 - Deux nombres consécutifs
On choisit 6 nombres distincts dans {1,2,…,10}. Montrer qu’au moins deux sont consécutifs.
Solution
Regroupons les nombres en 5 paires (1,2), (3,4), (5,6), (7,8), (9,10). En choisissant 6 nombres, deux appartiennent au moins à la même paire et sont donc consécutifs.
Problème 12 - Pourquoi 5 ne suffisent-ils pas ?
Dans le problème précédent, 5 nombres suffiraient-ils ?
Solution
Non. Le contre-exemple {1,3,5,7,9} contient 5 nombres sans aucune paire de consécutifs. Le seuil minimal est donc 6.
Problème 13 - Deux nombres dont la somme vaut 11
On choisit 6 nombres distincts entre 1 et 10. Montrer que deux ont pour somme 11.
Solution
Formons les 5 paires (1,10), (2,9), (3,8), (4,7), (5,6). Chaque paire a pour somme 11. En choisissant 6 nombres, on sélectionne entièrement au moins une paire. Somme = 11.
Problème 14 - Une petite différence
On choisit 6 nombres distincts entre 1 et 10. Montrer qu’au moins deux diffèrent d’au plus 1.
Solution
Utilisons les paires (1,2), (3,4), (5,6), (7,8), (9,10). Avec 6 nombres, deux sont dans la même paire ; puisqu’ils sont distincts, leur différence vaut exactement 1.
Problème 15 - Nombres de 1 à 100
On choisit 51 nombres distincts entre 1 et 100. Montrer qu’au moins deux sont consécutifs.
Solution
Répartissons les 100 nombres en 50 paires (1,2), (3,4), …, (99,100). Parmi 51 choix, au moins une paire est entièrement choisie.
Problème 16 - Une différence divisible par 7
On choisit 8 entiers quelconques. Montrer que deux diffèrent d’un multiple de 7.
Solution
Chaque entier a l’un des 7 restes 0,1,2,3,4,5,6 modulo 7. Parmi 8 entiers, deux ont le même reste ; leur différence est divisible par 7.
Problème 17 - Cent un nombres de 1 à 200
On prend 101 entiers distincts compris entre 1 et 200. Montrer qu’au moins deux diffèrent de moins de 2.
Solution
Pour des entiers distincts, différer de moins de 2 signifie différer exactement de 1. Formons les 100 paires (1,2), (3,4), …, (199,200). Avec 101 nombres, une paire entière est choisie.
Problème 18 - Des points dans un carré
On choisit 5 points dans un carré de côté 2. Montrer qu’au moins deux sont distants d’au plus √2.
Solution
Divisons le carré en 4 carrés de côté 1. Deux des 5 points sont dans le même petit carré. Leur distance maximale est sa diagonale : d ≤ √2.
Problème 19 - Dix points dans un carré
On choisit 10 points dans un carré de côté 3. Montrer qu’au moins deux sont distants d’au plus √2.
Solution
Divisons le carré en 9 carrés de côté 1. Avec 10 points, deux sont dans le même petit carré et leur distance ne dépasse pas sa diagonale, √2.
Problème 20 - Personnes et connaissances
Une fête réunit 6 personnes. Chaque paire de personnes se connaît ou ne se connaît pas. Montrer qu’il existe toujours trois personnes qui se connaissent toutes mutuellement, ou trois personnes dont aucune ne connaît les deux autres.
Solution
Choisissons une personne A. Parmi les 5 autres, au moins 3 connaissent toutes A ou au moins 3 ne connaissent toutes pas A. Dans le premier cas, si deux de ces 3 personnes se connaissent, elles forment avec A un trio de connaissances ; si aucune paire ne se connaît, les 3 forment un trio d’inconnus. Le second cas est symétrique. C’est un petit exemple de théorie de Ramsey.
Problème 21 - Le même nombre d’amis
Une fête réunit n ≥ 2 personnes. Montrer qu’au moins deux ont le même nombre d’amis présents.
Solution
Chaque personne pourrait avoir de 0 à n − 1 amis, mais les valeurs 0 et n − 1 ne peuvent coexister : si quelqu’un connaît tout le monde, personne n’a 0 ami. Il y a donc au plus n − 1 nombres d’amis possibles pour n personnes. Deux ont nécessairement le même nombre d’amis.
Problème 22 - Deux sous-ensembles de même somme
On choisit 10 entiers positifs ne dépassant pas 100. Montrer que deux sous-ensembles différents ont la même somme.
Solution
Distinguons les dix positions choisies, même si certaines valeurs coïncident. Elles engendrent 2¹⁰ = 1024 sous-ensembles de positions, y compris l’ensemble vide. La somme totale est au plus 1000 ; il y a donc au plus 1001 sommes possibles, de 0 à 1000. Comme 1024 > 1001, deux sous-ensembles distincts ont la même somme.
Problème 23 - Sommes partielles
Soient a₁,a₂,…,aₙ des entiers quelconques. Montrer qu’il existe un bloc de termes consécutifs dont la somme est divisible par n.
Solution
Considérons les n sommes partielles S₁=a₁, S₂=a₁+a₂, …, Sₙ=a₁+…+aₙ. Si l’une est divisible par n, c’est fini. Sinon, leurs restes appartiennent à 1,…,n − 1 : n sommes dans n − 1 classes. Deux sommes Sᵢ et Sⱼ ont le même reste. Leur différence Sⱼ − Sᵢ = aᵢ₊₁+…+aⱼ est donc divisible par n.
Problème 24 - Divisibilité cachée
On choisit 51 nombres distincts dans {1,2,…,100}. Montrer que l’un de deux nombres choisis divise l’autre.
Solution
Tout entier positif s’écrit de façon unique 2^k·m avec m impair. Classons les nombres selon leur partie impaire m. Entre 1 et 100, il existe 50 parties impaires possibles. Parmi 51 nombres, deux ont la même partie impaire : 2^a·m et 2^b·m. Si a<b, le second vaut 2^(b−a) fois le premier ; le premier divise donc le second.
Problème 25 - Sous-suite croissante ou décroissante
On choisit 10 nombres distincts et on les écrit dans un certain ordre. Montrer qu’il existe toujours une sous-suite croissante d’au moins 4 nombres ou une sous-suite décroissante d’au moins 4 nombres.
Solution
À chaque terme xᵢ, associons Cᵢ, longueur de la plus longue sous-suite croissante qui finit en xᵢ, et Dᵢ, longueur analogue pour une sous-suite décroissante. Si aucune n’atteignait 4, on aurait Cᵢ,Dᵢ ∈ {1,2,3} : seulement 9 couples possibles (Cᵢ,Dᵢ) pour 10 termes. Deux termes auraient le même couple. Or, pour i<j, si xⱼ>xᵢ, la longueur croissante peut augmenter ; si xⱼ<xᵢ, c’est la longueur décroissante. Un couple identique est impossible : contradiction. 3 × 3 = 9 < 10.
6. Qu’est-ce qui rend ces problèmes difficiles ?
Dans les premiers exercices, les pigeonniers sont évidents : mois, couleurs, classes, jours. Dans les problèmes plus intéressants, il faut les inventer. Ce peuvent être des restes, des paires de nombres, des intervalles, des régions géométriques, des parties impaires, des sommes possibles ou des couples de caractéristiques. Le principe mathématique reste élémentaire ; la vraie difficulté est de choisir le bon classement.
7. Stratégie générale
- Quels sont les pigeons ?
- Quels peuvent être les pigeonniers ?
- Combien y a-t-il de pigeonniers ?
- Quel est le plus grand nombre d’objets que je peux placer sans obtenir le résultat ?
- Que se passe-t-il en ajoutant un objet ?
Question clé : comment classer les objets pour que le principe des tiroirs devienne inévitable ?