Principe des tiroirs

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, le principe des tiroirs de Dirichlet, affirme que si n chaussettes occupent m tiroirs, et si n > m, alors au moins un tiroir doit contenir strictement plus d'une chaussette. Une autre formulation serait que m tiroirs ne peuvent contenir strictement plus de m chaussettes avec une seule chaussette par tiroir ; ajouter une autre chaussette obligera à réutiliser l'un des tiroirs.

Mathématiquement, le principe des tiroirs peut s'énoncer ainsi :

Si E et F sont deux ensembles finis, tels que card(E) > card(F) et si f : EF est une application de E dans F, alors il existe un élément de F qui admet au moins deux antécédents par f ; autrement dit il n'existe pas d'application injective de E dans F.

Appellation[modifier | modifier le code]

La première version du principe fut énoncée par Dirichlet en 1834 sous le nom de Schubfachprinzip (« principe du tiroir »), suite à une observation de ses chaussettes dans sa commode. Dans certains pays comme la Russie, ce principe s'appelle le principe de Dirichlet (à ne pas confondre avec le principe du maximum pour les fonctions harmoniques, du même nom). Ce principe est aussi appelé principe des tiroirs de Dirichlet-Schläfli.

En anglais, ce principe est appelé pigeonhole principle. Il fait référence à la répartition des pigeons dans les cases (ou « boulins ») d'un pigeonnier.

Applications[modifier | modifier le code]

Bien que le principe des tiroirs semble être une observation triviale, il peut être employé pour démontrer des résultats inattendus.

Par exemple, il est certain qu'au moins deux personnes à Dallas au Texas ont exactement le même nombre de cheveux sur leur tête. Démonstration : une tête normale a environ 150 000 cheveux et il est raisonnable de supposer que personne n'a plus de 1 000 000 cheveux sur la tête. Or Dallas compte plus de 1 000 000 habitants. Si nous associons à chaque nombre de cheveux sur une tête un tiroir, et si nous plaçons chaque habitant de Dallas dans le tiroir correspondant à son nombre de cheveux sur la tête, alors d'après le principe des tiroirs, il y a nécessairement au moins deux personnes ayant exactement le même nombre de cheveux sur la tête à Dallas.

Une application plus mathématique du principe est le fait qu'une application f d'un ensemble fini A vers lui-même est injective si et seulement si elle est surjective (ce qui est bien sûr faux quand A est infini). Si on supposait pour f injective qu'un élément a de A était absent de l'image de f, cela permettrait de ranger chaque élément (chaussette) x de A dans l'élément (tiroir) f(x) de A privé de a, sans jamais mettre deux chaussettes dans le même tiroir (à cause de l'injectivité) ; comme l'ensemble des tiroirs est strictement plus petit que l'ensemble fini des chaussettes, cela contredirait le principe des tiroirs. Réciproquement si f est surjective, on définit une application g:AA en choisissant pour chaque élément y un antécédent g(y) de y pour f, c'est-à-dire telle que f(g(y)) = y pour tout y. De cette équation on déduit que g est injective, donc aussi surjective (d'après la partie déjà démontrée) si bien que par injectivité de fg, f est injective.

Approximation d'un réel[modifier | modifier le code]

Soit un réel x et un entier naturel n. Pour tout réel y, on note \{y\} la partie fractionnaire de y (c'est-à-dire la différence entre y et sa partie entière). Les (n+1) éléments de [0,1[ définis par 0,\{x\},\dots,\{nx\} se répartissent dans les n « tiroirs » [r/n,(r+1)/n[, où  r=0,\ldots,n-1. Il existe donc un entier r et deux entiers 0\leq k<l\leq n tels que :

\frac{r}{n} \leq \{kx\},\{lx\}< \frac{r+1}{n}.

et donc

|\{kx\}-\{lx\}|< \frac{1}{n}.

En notant p la différence des parties entières de kx et lx, on en déduit :

|(l-k)x-p|<\frac{1}{n},

ou encore, en introduisant l'entier q=l-k, inférieur à n :

\left|x-\frac{p}{q}\right|<\frac{1}{q^2}.

Généralisations[modifier | modifier le code]

Une version généralisée de ce principe déclare que, si n objets discrets occupent m récipients, alors au moins un récipient doit contenir au moins P\left(\frac{n}{m}\right) objets où P est la fonction qui associe à un réel x le plus petit entier supérieur ou égal à x. Le nombre P\left(\frac{n}{m}\right) est donc le plus petit entier supérieur ou égal à \frac{n}{m}, et peut s'écrire avec la fonction partie entière : -E\left(-\frac{n}{m}\right).

Le principe des tiroirs est un exemple d'argument de dénombrement. Ce principe peut être appliqué à de nombreux problèmes sérieux, y compris ceux qui impliquent des ensembles infinis qui ne peuvent pas être mis en correspondance univoque. En approximation diophantienne, l'application quantitative du principe montre l'existence de solutions entières d'un système d'équations linéaires et ce résultat porte le nom de lemme de Siegel.

Articles connexes[modifier | modifier le code]