Principe des tiroirs

Dans cet article, nous présentons le principe des tiroirs. C'est une propriété bien connue et utile de la théorie (naïve) des ensembles.

Soit $E$ un ensemble, on dit que $n$ sous-ensembles $E_1,\ldots,E_n$ de $E$ sont deux à deux disjoints si pour tout $i\neq j$, tels que $1\leq i\leq n$ et $1\leq j\leq n$, l'intersection $E_i\cap E_j$ est vide, autrement dit, s'il n'existe aucun élément appartenant à la fois à $E_i$ et à $E_j$. 

Propriété. Soit $E$ un ensemble et soient $E_1,E_2,\ldots,E_n\subset E$ des sous-ensembles finis deux à deux disjoints. Soient $x_1,x_2,\ldots,x_{n+1}$ des éléments de la réunion 

$$E'=\bigcup_{i=1}^n E_i$$

Alors il existe un sous-ensemble $E_{i_0}$ avec $1\leq i_0\leq n$ tel que $E_{i_0}$ contient au moins deux éléments $x_{j_1}$ et  $x_{j_2}$ où $j_1\neq j_2$, avec $1\leq j_1\leq n$ et $1\leq j_2\leq n$.  

Démonstration. Par récurrence sur $n$.

Initialisation. Si $n=1$, alors $x_1$ et $x_2$ appartiennent à $E_1$ donc c'est vérifié.

Hérédité. Supposons le résultat montré pour $n=k$. Supposons que nous avons $E_1,E_2,\ldots,E_{k},E_{k+1}\subset E$. Soient $x_1,\ldots,x_{k+1},x_{k+2}$ des éléments de  $E'=\bigcup_{i=1}^{k+1} E_i$. 

Posons $F_1=\bigcup_{i=1}^{k} E_i$ et $F_2=E_{k+1}$. Ces deux ensembles sont disjoints.

Nous avons deux possibilités : 

(1) Tous les $x_1,\ldots,x_{k+1},x_{k+2}$ sont dans $F_1$. Alors en particulier, tous les $x_1,\ldots,x_{k+1}$ sont dans les $E_i$ pour $1\leq i \leq k$. Par l'hypothèse de récurrence, il existe au moins des ces sous-ensembles contenant deux $x_i$.     

(2) Dans l'autre cas, $F_2$ contient un élément $x_i$, disons $x_{k+1}$. Il reste à répartir $x_1,\ldots,x_{k+1}$. Nous  avons deux sous-cas : 

(2.a) $F_2=E_{k+1}$ contient deux éléments $x_i$ et c'est fini. 

(2.b) $F_2$ ne contient qu'un $x_i$. Dans ce cas $F_1=\bigcup_{i=1}^{k} E_i$ contient $k+1$ éléments $x_i$. Par l'hypothèse de récurrence, l'un de ces $E_i$ contient deux éléments $x_i$.

Conclusion. La  propriété est démontrée.

Remarque 1. On appelle cette propriété principe des tiroirs car si l'on veut ranger $n+1$ objets dans $n$ tiroirs, il y aura au moins un tiroirs qui contiendra deux objets.

Remarque 2. Cette propriété s'appelle aussi principe des chaussettes ou principe des pigeons.