Principe des tiroirs

En mathématiques, le principe des tiroirs de Dirichlet, affirme que, si $n$ chaussettes sont rangées dans $m$ tiroirs, et que $m < n$ , alors il y a un tiroir qui contient au moins deux chaussettes. Mathématiquement, le principe peut s'énoncer ainsi :

Si

E

et

F

sont deux ensembles finis tels que

Card (E) > Card (F)

, alors 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 Modèle:Lang (« principe du tiroir ») ; sa première utilisation lui est cependant antérieure d'au moins deux siècles^[1]Modèle:,^{[note 1]}. 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 portant le même nom). Ce principe est aussi appelé principe des tiroirs de Dirichlet-Schläfli.

On a ici $n = 10$ pigeons répartis dans $m = 9$ cases. Il y a donc une case qui contient au moins deux pigeons (sur l'image, en haut à gauche).

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

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 $⌈ \frac{n}{m} ⌉$ objets où $⌈ ⌉$ est la fonction partie entière par excès, qui associe à un réel x le plus petit entier supérieur ou égal à x ; ce nombre peut s'écrire avec la fonction partie entière : $⌈ \frac{n}{m} ⌉ = - E (- \frac{n}{m})$ .

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, résultat qui porte le nom de lemme de Siegel.

Des généralisations aux ensembles infinis existent ; ainsi, une partition d'un ensemble de cardinal α en β sous-ensembles, avec β<α, contient au moins un sous-ensemble de cardinal α si α est un cardinal régulier (en admettant l'axiome du choix).

Applications

Bien que le principe des tiroirs semble être une observation triviale, il peut être employé de manière inattendue pour démontrer des résultats complexes.

En dehors du champ des sciences

Il est certain qu'au moins deux personnes en Australie ont exactement le même nombre de cheveux sur leur tête. En effet il est raisonnable de supposer que personne n'a plus de Modèle:Nombre sur la tête (une tête normale a environ Modèle:Nombre^[2]). Or l'Australie compte plus de Modèle:Nombre. Si nous associons à chaque nombre de cheveux sur une tête un tiroir, et si nous plaçons chaque Australien 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 en Australie^[3]. De plus comme il y a quatre fois plus d'Australiens que de tiroirs, on peut affirmer qu'il existe au moins quatre Australiens ayant le même nombre de cheveux^[3].

Géométrie

Subdivisions d'un triangle

Soit un triangle d'aire égale à 1. Si l'on choisit 9 points à l'intérieur de celui-ci, alors on peut en trouver trois d'entre eux qui déterminent un triangle d'aire inférieure à $\frac{1}{4}$ . En effet on peut découper le triangle en 4 triangles d'aire quatre fois plus petite, et d'après le principe des tiroirs généralisé l'un au moins de ces petits triangles contiendra au moins trois points, délimitant une aire inférieure au quart de celle du grand triangle^[4]Modèle:,^[5]Modèle:,^{[note 2]}.

La méthode peut être raffinée, toujours à l'aide du principe des tiroirs, en faisant usage de ce que trois points dans un parallélogramme d'aire $\frac{1}{2}$ délimitent nécessairement une aire inférieure à $\frac{1}{4}$ ^[4]. En choisissant comme tiroirs les trois parallélogrammes formés par l'un des sommets et par le Modèle:Lien^{[note 3]}, il s'ensuit que parmi 7 points quelconques dans un triangle d'aire 1, on peut en trouver 3 qui délimitent un triangle d'aire $\frac{1}{4}$ ^[4]Modèle:,^[5]Modèle:,^{[note 2]}. Modèle:-

Combinatoire

Sous-ensembles d'entiers de même somme

Parmi les nombres allant de 1 à 100, on en choisit dix différents. Il existe toujours deux sous-ensembles disjoints non vides de ces dix nombres ayant la même somme^[3]. En effet les sommes des sous-ensembles peuvent valoir entre 1 et 955^{[note 4]}, alors qu'il y a 2¹⁰-1 = 1023 sous-ensembles non vide possibles : on doit donc répartir 1023 éléments (les sous-ensembles) dans 955 tiroirs (les différentes sommes) donc l'un des tiroirs contient deux combinaisons différentes ayant la même somme^[3]Modèle:,. Les deux combinaisons obtenues peuvent ne pas être disjointes mais comme elles sont différentes il est possible de supprimer tous les éléments communs pour obtenir deux combinaisons non-vides de même somme. Cette méthode ne permet cependant pas de trouver d'exemple de deux telles sommes^{[note 5]}.

Problèmes d'empilement

Points inévitables lorsque l'on essaie de disposer des carrés de taille 1 dans un carré de taille inférieure à 5 : comme il y a 23 points il n'est pas possible de disposer 24 carrés d'après le principe des tiroirs.

Un problème d'empilement est une situation où l'on cherche à agencer des objets dans une forme plus grande de façon à pouvoir en disposer le plus possible sans qu'il n'y ait de recoupement. Trouver le nombre maximal d'objets que l'on peut disposer peut être un problème difficile ; pour obtenir une borne inférieure il suffit d'exhiber un exemple de disposition mais trouver une borne supérieure est nettement plus difficile. L'une des techniques pouvant être utilisée est d'identifier un ensemble de points dont on est sûr que chaque objet de la configuration choisie couvrira au moins l'un des points : le principe des tiroirs assure alors qu'il est impossible de disposer plus d'objet qu'il n'y a de points-tiroirs. Ce type de raisonnement est utilisé dans le problème de l'empilement de carrés dans un carré^[6].

Mathématiques récréatives

Disposition de fous sur un échiquier

Par analogie avec le problème des huit dames, on peut se demander combien de fous au maximum on peut disposer sur un échiquier sans qu'aucun d'eux ne soit en prise si l'on ne tient pas compte de leurs couleurs.

On peut montrer en exhibant un exemple bien choisiModèle:Note que la bonne réponse est supérieure ou égale à 14. Pour montrer qu'elle est également inférieure ou égale à 14, et donc égale à 14, on peut avoir recours au principe des tiroirs. Pour cela on subdivise astucieusement l'échiquier en 14 groupes de cases de telle sorte que deux fous posés sur deux cases d'un même groupe se menacent forcément : le principe des tiroirs permet alors d'affirmer qu'il est impossible de disposer 15 fous sans qu'au moins deux d'entre eux soient placés dans un même groupe et se menacent mutuellement^[7].

Modèle:Diagramme d'échecs petit

Partage d'un échiquier en 14 tiroirs colorés dans chacun desquels deux fous se menacent forcément

Théorie des nombres

Approximation d'un réel

Soient un réel Modèle:Math et un entier Modèle:Math. Pour tout réel Modèle:Math, on note Modèle:Math sa partie fractionnaire (c'est-à-dire la différence entre Modèle:Math et sa partie entière). Les Modèle:Math éléments Modèle:Mathde Modèle:Math (non nécessairement distincts) se répartissent dans les Modèle:Math « tiroirs » Modèle:Math, où Modèle:Math. Il existe donc un entier Modèle:Math et deux entiers Modèle:Math tels que :

\frac{r}{n} \leq {k x}, {l x} < \frac{r + 1}{n} .

et donc :

| {k x} - {l x} | < \frac{1}{n}

.

En notant Modèle:Math la différence des parties entières de Modèle:Math et Modèle:Math, on en déduit :

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

,

ou encore, en introduisant l'entier Modèle:Math :

| x - \frac{p}{q} | < \frac{1}{n q} \leq \frac{1}{q^{2}}

^[8]Modèle:,^{[note 6]}.

On démontre de même le théorème d'approximation de Dirichlet, un résultat plus général d'approximation simultanée de d réels. Pour d = 1, on en déduit que la mesure d'irrationalité de tout nombre irrationnel est supérieure ou égale à 2.

Informatique

Problème de recherche des plus proches voisins

Modèle:Article détaillé

Le grand rectangle est découpé en 8 carrés de côté $\frac{δ}{2}$ . Deux points dans un de ces 8 tiroirs sont séparés de moins de $δ$ : on ne peut donc pas placer 9 points séparés de $δ$ dans le grand rectangle.

L'un des problèmes fondateurs de la géométrie algorithmique consiste à identifier parmi un ensemble de points la paire séparée par la plus petite distance. Une technique de résolution efficace repose sur la technique diviser pour régner. Celle-ci nécessite de savoir combien, dans un rectangle de longueur $2 δ$ et de largeur $δ$ , on peut avoir de points séparés par une distance au moins égale à $δ$ ^{[note 7]}. Par principe des tiroirs on peut montrer que ce nombre est nécessairement inférieur ou égal à 8^[9].

Modèle:-

Lemme de l'étoile

Modèle:Article détaillé La preuve la plus classique du lemme de l'étoile repose essentiellement sur l'application du principe des tiroirs où chaque tiroir est un état d'un automate fini.

Fonction de hachage

Une fonction de hachage est une fonction qui transforme une suite de bits de longueur arbitraire en une chaîne de longueur fixe. Du fait qu'il y a plus de chaînes possibles en entrée qu'en sortie découle par le principe des tiroirs l'existence de collisions : plusieurs chaînes distinctes ont le même haché. Rendre ces collisions difficiles à déterminer efficacement est un enjeu important en cryptographie.

Modélisation en logique propositionnelle

On considère un nombre entier $n$ . Dire que lorsque l'on répartit $n + 1$ pigeons dans $n$ trous, un trou au moins comprend 2 pigeons, c'est affirmer la négation de la proposition Modèle:Citation.

Or on peut montrer que toutes les preuves par réfutations en résolution de la formule propositionnelle qui dit Modèle:Citation sont asymptotiquement de taille au moins $2^{\frac{n}{20}}$ , c'est-à-dire que la taille minimale d'une preuve de cette proposition croît exponentiellement avec le nombre $n$ de trous^[10].

Exemple

On considère le cas où $n = 3$ , c'est-à-dire que l'on essaie de ranger 4 pigeons dans 3 trous. Pour tout $p \in {1, 2, 3, 4}$ et tout $t \in {1, 2, 3}$ on définit la variable booléenne $x_{p}^{t}$ qui vaut $𝚅 𝚛 𝚊 𝚒$ si le pigeon numéro $p$ est dans le trou numéro $t$ et qui vaut $𝙵 𝚊 𝚞 𝚡$ sinon^[11].

Expression du rangement des pigeons

Soit $p \in {1, 2, 3, 4}$ . On écrit que le pigeon numéro $p$ est dans l'un des trois trous par la formule logique :

x_{p}^{1} \lor x_{p}^{2} \lor x_{p}^{3}

Le fait que chacun des quatre pigeons soit dans un des trous s'écrit donc :

(x_{1}^{1} \lor x_{1}^{2} \lor x_{1}^{3}) \land (x_{2}^{1} \lor x_{2}^{2} \lor x_{2}^{3}) \land (x_{3}^{1} \lor x_{3}^{2} \lor x_{3}^{3}) \land (x_{4}^{1} \lor x_{4}^{2} \lor x_{4}^{3})

Expression de ce qu'aucun trou ne contient plus d'un pigeon

Soit $t \in {1, 2, 3}$ . On écrit que le trou numéro $t$ contient au plus un pigeon, c'est-à-dire qu'il contient soit 0 pigeon, soit un seul des pigeons numérotés de 1 à 4 :

(\neg x_{1}^{t} \land \neg x_{2}^{t} \land \neg x_{3}^{t} \land \neg x_{4}^{t}) \lor (x_{1}^{t} \land \neg x_{2}^{t} \land \neg x_{3}^{t} \land \neg x_{4}^{t}) \lor (\neg x_{1}^{t} \land x_{2}^{t} \land \neg x_{3}^{t} \land \neg x_{4}^{t}) \lor (\neg x_{1}^{t} \land \neg x_{2}^{t} \land x_{3}^{t} \land \neg x_{4}^{t}) \lor (\neg x_{1}^{t} \land \neg x_{2}^{t} \land \neg x_{3}^{t} \land x_{4}^{t})

Formule logique résultante

La proposition Modèle:Citation s'écrit donc sous la forme de la conjonction de clauses suivante :

(x_{1}^{1} \lor x_{1}^{2} \lor x_{1}^{3}) \land (x_{2}^{1} \lor x_{2}^{2} \lor x_{2}^{3}) \land (x_{3}^{1} \lor x_{3}^{2} \lor x_{3}^{3}) \land (x_{4}^{1} \lor x_{4}^{2} \lor x_{4}^{3})

⋀ [(\neg x_{1}^{1} \land \neg x_{2}^{1} \land \neg x_{3}^{1} \land \neg x_{4}^{1}) \lor (x_{1}^{1} \land \neg x_{2}^{1} \land \neg x_{3}^{1} \land \neg x_{4}^{1}) \lor (\neg x_{1}^{1} \land x_{2}^{1} \land \neg x_{3}^{1} \land \neg x_{4}^{1}) \lor (\neg x_{1}^{1} \land \neg x_{2}^{1} \land x_{3}^{1} \land \neg x_{4}^{1}) \lor (\neg x_{1}^{1} \land \neg x_{2}^{1} \land \neg x_{3}^{1} \land x_{4}^{1})]

⋀ [(\neg x_{1}^{2} \land \neg x_{2}^{2} \land \neg x_{3}^{2} \land \neg x_{4}^{2}) \lor (x_{1}^{2} \land \neg x_{2}^{2} \land \neg x_{3}^{2} \land \neg x_{4}^{2}) \lor (\neg x_{1}^{2} \land x_{2}^{2} \land \neg x_{3}^{2} \land \neg x_{4}^{2}) \lor (\neg x_{1}^{2} \land \neg x_{2}^{2} \land x_{3}^{2} \land \neg x_{4}^{2}) \lor (\neg x_{1}^{2} \land \neg x_{2}^{2} \land \neg x_{3}^{2} \land x_{4}^{2})]

⋀ [(\neg x_{1}^{3} \land \neg x_{2}^{3} \land \neg x_{3}^{3} \land \neg x_{4}^{3}) \lor (x_{1}^{3} \land \neg x_{2}^{3} \land \neg x_{3}^{3} \land \neg x_{4}^{3}) \lor (\neg x_{1}^{3} \land x_{2}^{3} \land \neg x_{3}^{3} \land \neg x_{4}^{3}) \lor (\neg x_{1}^{3} \land \neg x_{2}^{3} \land x_{3}^{3} \land \neg x_{4}^{3}) \lor (\neg x_{1}^{3} \land \neg x_{2}^{3} \land \neg x_{3}^{3} \land x_{4}^{3})]

Taille de la preuve de réfutation

Modèle:... On cherche à montrer que la formule logique précédente est fausse. Pour cela il faut montrer qu'aucune des $2^{12} = 4096$ instanciations des 12 variables $x_{1}^{1}, x_{1}^{2}, x_{1}^{3}, x_{2}^{1}, x_{2}^{2}, x_{2}^{3}, x_{3}^{1}, x_{3}^{2}, x_{3}^{3}, x_{4}^{1}, x_{4}^{2}, x_{4}^{3}$ ne satisfait la formule. D'un point de vue informel, le théorème affirme qu'il n'existe pas de moyen « court » de montrer cela.

Notes et références

Notes

Modèle:Références

Références

Modèle:Références

Voir aussi

Articles connexes

Bibliographie

Modèle:Portail

↑ Modèle:Article.
↑ Modèle:Youtube
↑ ^3,0 ^3,1 ^3,2 et ^3,3 Modèle:Youtube, chapitre 1.
↑ ^4,0 ^4,1 et ^4,2 Modèle:Ouvrage.
↑ ^5,0 et ^5,1 Modèle:Ouvrage.
↑ Modèle:Lien web.
↑ Modèle:Article.
↑ Modèle:HardyWrightFr, Modèle:P..
↑ Modèle:Article, disponible en accès libre.
↑ Modèle:Ouvrage
↑ Modèle:Lien web, section 2.4.1 - le problème des pigeons.

Erreur de référence : Des balises <ref> existent pour un groupe nommé « note », mais aucune balise <references group="note"/> correspondante n’a été trouvée

[1] Modèle:Article.

[3] Modèle:Youtube

[mathologer-4] 3,0 ^3,1 ^3,2 et ^3,3 Modèle:Youtube, chapitre 1.

[delahaye-5] 4,0 ^4,1 et ^4,2 Modèle:Ouvrage.

[Soifer-6] 5,0 et ^5,1 Modèle:Ouvrage.

[11] Modèle:Lien web.

[delahaye18-12] Modèle:Article.

[13] Modèle:HardyWrightFr, Modèle:P..

[rau-16] Modèle:Article, disponible en accès libre.

[17] Modèle:Ouvrage

[18] Modèle:Lien web, section 2.4.1 - le problème des pigeons.

[1]

[note 1]

[2]

[3]

[4]

[5]

[note 2]

[note 3]

[note 4]

[note 5]

[6]

[7]

[8]

[note 6]

[note 7]

[9]

[10]

[11]

Principe des tiroirs

Sommaire

Appellation

Généralisations