Théorie > Combinatoire > Principe des tiroirs

É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 :

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

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 :

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 :

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