Prérequis
Aucun prérequis.
Résumé
Le principe des tiroirs est un principe important qui peut servir dans des contextes variés. Il est également appelé principe de Dirichlet ou pigeonhole principle en anglais. Ce principe, qui peut a priori sembler trivial, permet pourtant dans certains cas de résoudre des situations très complexes.
Ce chapitre a été
écrit par N. Franco et
mis en ligne le 8 décembre 2014.
1. Idée intuitive
Le nom de principe des tiroirs vient de la simple idée de placer des chaussettes dans des tiroirs (ou des pigeons dans des cases de pigeonnier pour le nom anglais : pigeonhole principle).
Supposons que nous avons $5$ tiroirs à notre disposition et que $6$ chaussettes sont rangées dedans. Nous n'avons aucune connaissance de la façon dont sont rangées ces chaussettes, et pourtant nous pouvons affirmer la chose suivante : dans un de ces tiroirs se trouvent au moins $2$ chaussettes.
Nous pouvons le vérifier facilement. En effet, si nous imaginons que ce résultat est faux (raisonnement par l'absurde), alors nous devons avoir au maximum $1$ chaussette par tiroir. Comme il y a $5$ tiroirs, il y a maximum $5$ chaussettes, ce qui contredit le nombre de $6$ chaussettes. Donc le résultat doit être vrai, et il y a au moins un tiroir qui contient au moins $2$ chaussettes.
Si maintenant nous savons qu'il y a $16$ chaussettes dans $5$ tiroirs, nous pouvons pousser le raisonnement un peu plus loin et déclarer qu'il y a au moins un tiroir qui contient au moins $4$ chaussettes.
Attention : nous parlons bien d'au moins un tiroir qui contient au moins $4$ chaussettes. En effet, il est tout à fait possible que plusieurs tiroirs contiennent $4$ chaussettes, ou qu'un tiroir contienne plus que $4$ chaussettes, voire même toutes les chaussettes. De plus, ce type de raisonnement prouve seulement l'existence du tiroir et n'indique lequel en aucune façon. Ce type de raisonnement est donc principalement efficace pour des problèmes du type "Prouver qu'il existe..." demandant seulement la preuve de l'existence d'un élément et non sa construction.
2. Énoncés
Voici les énoncés plus rigoureux des différentes versions du principe des tiroirs.
Le principe des tiroirs
Le principe des tiroirs sous sa forme la plus simple est le suivant :
Principe des tiroirs
Si $n+1$ éléments doivent être placés dans $n$ ensembles, alors il existe au moins un ensemble qui contient au moins $2$ éléments.
Démonstration
Par l'absurde, si tous les ensembles contiennent $0$ ou $1$ élément, alors le nombre d'éléments est inférieur ou égal à $n$.
Ceux qui connaissent la notion de
fonction injective peuvent comprendre que le principe des tiroirs est équivalent à la propriété suivante.
Le principe des tiroirs généralisé
On peut généraliser ce principe comme suit :
Principe des tiroirs généralisé
Si $n$ éléments doivent être placés dans $k$ ensembles, alors il existe au moins un ensemble qui contient au moins $\left\lceil\frac{n}{k}\right\rceil$ éléments.
Note : $\lceil x\rceil$ désigne la partie entière supérieure, soit le plus petit entier supérieur ou égal à $x$, ou l'unique entier tel que $\lceil x\rceil -1< x \leq \lceil x\rceil$.
Démonstration
Par l'absurde, supposons que chaque ensemble contienne au maximum $\left\lceil\frac{n}{k}\right\rceil-1$ éléments. Par définition de la partie entière supérieure, nous avons $\left\lceil\frac{n}{k}\right\rceil-1 < \frac{n}{k}$, donc le nombre maximum d'éléments est
$$k\cdot\left(\left\lceil\frac{n}{k}\right\rceil-1\right) < k\cdot \frac{n}{k} = n.$$
Le principe des tiroirs infini
Il existe aussi une version du principe des tiroirs dans le cas où on a une infinité d'éléments :
Principe des tiroirs infini
Si une infinité d'éléments doivent être placés dans $n$ ensembles, alors il existe au moins un ensemble qui contient une infinité d'éléments.
Démonstration
Par l'absurde, si chaque ensemble contient un nombre fini d'éléments, alors il ne peut y avoir qu'un nombre fini d'éléments au total, ce qui contredit le fait qu'il y en a une infinité.
3. Exemples d'application
Voici deux exemples d'applications du principe des tiroirs, illustrant le fait que l'on peut démontrer des résultats assez divers avec ce principe.
Solution
Considérons le partitionnement de cet ensemble en $6$ sous-ensembles $\{1,11\}$, $\{2,10\}$, $\{3,9\}$, $\{4,8\}$, $\{5,7\}$ et $\{6\}$. Ces six sous-ensembles seront nos "tiroirs". Nos sept "chaussettes" sont alors les sept nombres choisis entre $1$ et $11$. Par le principe des tiroirs, il existe deux de nos sept nombres qui appartiennent à un même sous-ensemble. Comme ces nombres sont distincts, et vu la définition de nos sous-ensembles, leur somme vaut obligatoirement $12$.
Solution
Considérons les deux intervalles $\left[0,\frac 12\right[$ et $\left[\frac 12,1\right[$ formant une partition de $[0,1[$. Ces deux intervalles seront nos "tiroirs", et les trois nombres réels considérés seront nos "chaussettes". Par le principe des tiroirs, l'un de ces intervalles contient au moins deux nombres. Leur différence, en valeur absolue, est strictement inférieure à $\frac 12$.