Principe des tiroirs
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Le principe des tiroirs déclare 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 un des tiroirs.

Mathématiquement, le principe de 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.

Ou encore :

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 f n'est pas injective; autrement dit, il n'existe pas d'application injective de E dans F.

Appellation

La première version du principe fut énoncée par Dirichlet en 1834 sous le nom de Schubfachprinzip (" principe du tiroir "), suite à une observation (L’observation est l’action de suivi attentif des phénomènes, sans volonté de les modifier, à l’aide de moyens d’enquête et d’étude appropriés. Le plaisir procuré explique...) de ses chaussettes dans sa commode. Dans certains pays (Pays vient du latin pagus qui désignait une subdivision territoriale et tribale d'étendue restreinte (de l'ordre de quelques centaines de km²), subdivision de la civitas...) 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 (Le principe des tiroirs déclare 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...) de Dirichlet-Schläfli, ou encore principe des boîtes, ou par traduction littéraire de l'anglais le principe des trous de pigeons. Dans cette dernière image, on remplace chaussette par œuf de pigeon et tiroir par nid (Le nid désigne généralement la structure construite par les oiseaux pour contenir leurs œufs et fournir un premier abri à leur progéniture. Les nids sont généralement fabriqués à partir...) de pigeon !

Applications

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

Par exemple, il doit y avoir au moins deux personnes à Dallas (Pour le feuilleton, voir Dallas (feuilleton télévisé).) au Texas avec le même nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de cheveux sur leur tête. Démonstration (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment...): une tête normale a environ 150 000 cheveux et il est raisonnable de supposer que personne n'a pas plus de 1 000 000 de cheveux sur la tête. Il y a plus de 1 000 000 personnes à Dallas. 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 ! Évidemment, le résultat reste vrai pour n'importe quelle mégalopole (Une mégalopole (du grec megas, megalos, « grand » et polis, « ville ») est un espace urbanisé polynucléaire formé de plusieurs agglomérations dont les banlieues...).
Donnons un autre exemple d'application du principe des tiroirs dans la situation (En géographie, la situation est un concept spatial permettant la localisation relative d'un espace par rapport à son environnement proche ou non. Il inscrit un lieu dans un cadre plus général afin de le qualifier...) où il y a cinq personnes qui veulent jouer au rugby, mais seulement quatre équipes. Ce ne serait pas un problème si chacune des cinq personnes ne refusait pas de jouer dans une équipe avec l'une quelconques des quatre autres. Pour montrer qu'il n'y a aucun moyen pour que chacune des cinq personnes jouent au rugby, nous appliquons le principe des tiroirs qui indique qu'il est impossible de répartir cinq personnes dans quatre équipes sans mettre deux joueurs dans la même équipe. Puisque les joueurs refusent de jouer dans la même équipe, tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) au plus quatre joueurs pourront jouer.

Approximation (Une approximation est une représentation grossière c'est-à-dire manquant de précision et d'exactitude, de quelque chose, mais encore assez significative pour être utile. Bien qu'une approximation soit le plus...) d'un réel

Soit un réel x et un entier naturel n. Pour tout réel y, on définit {y} la partie fractionnaire de y, id est yE(y). On dispose de (n + 1) éléments de [0,1] : 0, {x}, \dots, {nx}. Deux de ces éléments appartiennent nécessairement à un intervalle de la forme [q / n,(q + 1) / n]. Il existe donc 0\leq k<l\leq n avec |\{kx\}-\{lx\}|\leq 1/n. Il existe donc un entier relatif r, différence des parties entières {kx} et {lx}, avec :

| (kl)xq | < 1 / n donc \left|x-\frac{q}{k-l}\right|<1/n

Généralisations

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 (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le terme désigne des échanges de courrier personnels plutôt qu'administratifs.) 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.

Page générée en 0.061 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique