Principe des tiroirs

Le principe des tiroirs est un énoncé très simple des mathématiques qui formalise l'évidence suivante : si vous avez $10$ caleçons et que votre commode comporte $9$ tiroirs, alors il y a au moins un tiroir qui contient $2$ caleçons! Mathématiquement ceci se traduit de la façon suivante : si $E$ et $F$ sont des ensembles finis avec $\card(E)>\card(F)$, et si $f:E\to F$ est une fonction, alors elle ne peut pas être injective.

Ce principe a été énoncé pour la première fois par Dirichlet au XIXè s. et il est fécond en mathématiques pour résoudre des problèmes d'existence sans construire explicitement un objet. Donnons deux exemples d'application :

Application en algèbre linéaire :

Soit $E$ un espace vectoriel (sur $\mathbb R$), et $E_1,\dots,E_p$ des sous-espaces vectoriels de $E$. Alors $E_1\cup\cdots\cup E_p$ est un sous-espace vectoriel de $E$ si et seulement s'il existe $i\in\{1,\dots,p\}$ tel que, pour tout $j=1,\dots,p$, $E_j\subset E_i$.

Le sens réciproque est évident. Pour le sens direct, on fait un raisonnement par récurrence. Le cas $p=1$ est trivial. On suppose maintenant que le problème est résolu pour $(p-1)$ sous-espaces vectoriels. Si $E_1\subset E_2\cup\cdots \cup E_p$, alors on peut appliquer directement l'hypothèse de récurrence. Si $E_2\cup\cdots \cup E_p\subset E_1$, alors le résultat est trivial. Il reste donc le cas où il existe $x\in E_1\backslash (E_2\cup\cdots \cup E_p)$ et $y\in (E_2\cup\cdots \cup E_p)\backslash E_1$. Considérons alors les éléments $x+ty$, pour $t$ parcourant $\mathbb R$. On les "range" dans les "tiroirs" $E_1,\dots,E_p$. Comme $\mathbb R$ est infini et qu'il n'y a qu'un nombre fini de tiroirs, il existe deux réels distincts $t$ et $t'$ tels que $x+ty$ et $x+t'y$ appartiennent au même sous-espace vectoriel $E_i$. Faisant la différence, on obtient $(t-t')y\in E_i$, puis $y\in E_i$. Mais ceci entraîne aussi que $x\in E_i$, ce qui est une contradiction avec le choix de $x$ et de $y$.

Application en théorie des nombres :

Soit $x\in\mathbb R$ et $N\geq 1$. Alors il existe des entiers $p,q$ avec $1\leq q\leq N$ tels que $$\left|x-\frac pq\right|\leq \frac1{qN}.$$ En effet, posons, pour $k=0,\dots,N$, $x_k=kx-\lfloor kx\rfloor$. Alors, pour chaque $k$, $x_k\in[0,1[$. Rangeons ces nombres dans les $N$ tiroirs $[r/N,(r+1)/N[$ avec $r=0,\dots,N-1$. Comme il y a $N+1$ nombres, deux au moins sont dans le même tiroir. Il existe donc $k< \ell$ tel que $$|x_\ell-x_k|<\frac 1N.$$ Posons $p$ l'entier $\lfloor lx\rfloor-\lfloor kx\rfloor$ et $q=\ell-k$. Alors l'inégalité précédente se réécrit $$|qx-p|<\frac 1n\iff \left|x-\frac pq\right|\leq \frac1{qN}.$$

Dans les pays anglo-saxons, on parle plutôt de principe du pigeonnier (pigeonhole principle), terme qui semble avoir été utilisé pour la première fois par le mathématicien Raphel Robinson en 1940.