Théorie > Combinatoire > Principe des tiroirs

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).

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 que nous parlons bien d'au moins un tiroir qui contient au moins $4$ chaussettes. En effet, il est tout a 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.

Autre formulation
Si $E$ et $F$ sont deux ensembles finis tels que $|E| > |F|$, alors il n'existe aucune application injective de $E$ dans $F$.

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.

Problème
Prouver que si $7$ nombres distincts sont choisis dans l'ensemble $\{1,2,3,4,5,6,7,8,9,10,11\}$, alors il en existe deux dont la somme vaut $12$.

Solution
Considérons le partitionnement de cet ensemble en $6$ sous-ensembles $\{1,11\}$, $\{2,10\}$, $\{3,9\}$, $\{4,8\}$, $\{5,7\}$ et $\{6\}$. Par le principe des tiroirs, Il existe $2$ nombres qui appartiennent à un même sous-ensemble. Comme ces nombres sont distincts, leur somme vaut obligatoirement $12$.

Problème
Prouver que si $3$ nombres réels sont dans l'intervalle $[0,1[$, alors il existe parmi eux deux nombres $a$ et $b$ tels que $|b-a|<\frac 12$.

Solution
Considérons les deux intervalles $\left[0,\frac 12\right[$ et $\left[\frac 12,1\right[$ formant une partition de $[0,1[$. 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$.