Lemme des tiroirs

Lemme des tiroirs

Principe des tiroirs

En mathématiques, le principe des tiroirs, ou 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.

Sommaire

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 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 d'un pigeonnier.

Applications

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 doit y avoir au moins deux personnes à Dallas au Texas avec 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 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.

Approximation d'un réel

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\}\leq \{lx\}< \frac{r+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 = lk, inférieur à n :

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

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

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Principe des tiroirs ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Lemme des tiroirs de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Lemme des bergers — En mathématiques, le lemme des bergers, ou principe des bergers[1] est une propriété combinatoire. Il peut s énoncer au niveau élémentaire par : Lemme des bergers   Si un ensemble E possède une partition en p sous ensembles… …   Wikipédia en Français

  • Principe des tiroirs — En mathématiques, le principe des tiroirs, ou 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… …   Wikipédia en Français

  • Lemme de l'étoile — En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, lemme de la pompe, pumping lemma en anglais) énonce une propriété typique de tout langage rationnel. Informellement, il stipule que tout mot… …   Wikipédia en Français

  • Lemme d'itération —  Ne pas confondre avec le Théorème d itération. En informatique théorique, et spécialement en théorie des langages, un lemme d itération (pumping lemma en anglais) est un énoncé qui stipule que, dans un langage formel d une classe… …   Wikipédia en Français

  • Lemme de Siegel — En mathématiques, le lemme de Siegel (1929) affirme l existence d une solution non nulle et de grandeur contrôlée à un système linéaire homogène à coefficients entiers. L exemple le plus simple est sans doute le suivant : Soit A = (ai,j) une …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Quasigroupe — En mathématiques, un quasigroupe est un ensemble muni d une loi de composition interne (un magma) pour laquelle (en pensant cette loi comme une multiplication), il est possible de diviser, à droite comme à gauche, le quotient à droite et le… …   Wikipédia en Français

  • Ensemble Fini — En mathématiques, un ensemble E est dit fini si et seulement s il existe un entier n et une bijection de E sur l ensemble des entiers naturels strictement plus petits que n, en particulier, si n = 0, E est l ensemble vide qui est donc bien fini.… …   Wikipédia en Français

  • Ensemble fini — En mathématiques, un ensemble E est dit fini si et seulement s il existe un entier n et une bijection de E sur l ensemble des entiers naturels strictement plus petits que n, en particulier, si n = 0, E est l ensemble vide qui est donc bien fini.… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”