Principe des tiroirs

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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 ») ; sa première utilisation lui est cependant antérieure d'au moins deux siècles[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.

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.

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

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

Preuve en logique propositionnelle[modifier | modifier le code]

On considère un nombre entier . Dire que lorsque l'on répartit pigeons dans trous, un trou au moins comprend 2 pigeons, c'est affirmer la négation de la proposition "il existe une répartition de pigeons dans trous telle que chaque trou contienne au plus un seul pigeon".

Or on peut montrer que toutes les preuves par réfutations en résolution de la formule propositionnelle qui dit "il y a pigeons dans trous et au plus un pigeon par trou" est asymptotiquement de taille au moins , c'est-à-dire que la taille minimale d'une preuve de cette proposition croît exponentiellement avec le nombre de trous[2].

Exemple[modifier | modifier le code]

On considère la cas où , c'est-à-dire que l'on essaie de ranger 4 pigeons dans 3 trous. Pour tout et tout on définit la variable booléenne qui vaut si le pigeon numéro est dans le trou numéro et qui vaut sinon.

Expression du rangement des pigeons[modifier | modifier le code]

Soit . On écrit que le pigeon numéro est dans l'un des trois trous par la formule logique :

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

Expression de ce qu'aucun trou ne contient plus d'un pigeon[modifier | modifier le code]

Soit . On écrit que le trou numéro 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 :

Formule logique résultante[modifier | modifier le code]

La proposition "il existe une répartition de 4 pigeons dans 3 trous telle que chaque trou contienne au plus un seul pigeon" s'écrit donc sous la forme de la conjonction de clauses suivante :

Taille de la preuve de réfutation[modifier | modifier le code]

On cherche à montrer que la formule logique précédente est fausse. Pour cela il faut montrer qu'aucune des instanciations des 12 variables 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.

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.

En dehors du champ des mathématiques[modifier | modifier le code]

Il est certain qu'au moins deux personnes à Dallas au Texas 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 1 000 000 cheveux sur la tête (une tête normale a environ 150 000 cheveux). 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.

Géométrie[modifier | modifier le code]

Subdivisions d'un triangle[modifier | modifier le code]

Les quatre petits triangles ont une aire égale au quart de celle du grand triangle. Si l'on choisit 9 points dans le grand triangle, alors d'après le principe des tiroirs l'un au moins des quatre petits triangles en contiendra 3.

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 à . 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[3],[4],[note 1].

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 délimitent nécessairement une aire inférieure à [3]. En choisissant comme tiroirs les trois parallélogrammes formés par l'un des sommets et par le triangle des milieux (en)[note 2], 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 [3],[4],[note 1].

Mathématiques récréatives[modifier | modifier le code]

Disposition de fous sur un échiquier[modifier | modifier le code]

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 choisi[note 3] 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[5].

abcdefgh
8
Chessboard480.svg
Fou noir sur case blanche a8
Fou noir sur case noire b8
Fou noir sur case blanche c8
Fou noir sur case noire d8
Fou noir sur case blanche e8
Fou noir sur case noire f8
Fou noir sur case blanche g8
Fou noir sur case noire h8
Fou noir sur case blanche b1
Fou noir sur case noire c1
Fou noir sur case blanche d1
Fou noir sur case noire e1
Fou noir sur case blanche f1
Fou noir sur case noire g1
8
77
66
55
44
33
22
11
abcdefgh
Disposition où aucun des 14 fous ne peut menacer les autres.
Partage d'un échiquier en 14 tiroirs colorés dans chacun desquels deux fous se menacent forcément

Théorie des nombres[modifier | modifier le code]

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

Soient un réel x et un entier n > 0. Pour tout réel y, on note {y} sa partie fractionnaire (c'est-à-dire la différence entre y et sa partie entière). Les n + 1 éléments 0, {x}, … , {n x} de [0, 1[ (non nécessairement distincts) se répartissent dans les n « tiroirs » [r/n, (r + 1)/n[, où r = 0, … , n – 1. Il existe donc un entier r et deux entiers 0 ≤ k < ln tels que :

et donc :

.

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

,

ou encore, en introduisant l'entier q = l – k ≥ 1 :

[6],[note 4].

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 théorique[modifier | modifier le code]

Lemme de l'étoile[modifier | modifier le code]

Article détaillé : Lemme de l'étoile.

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.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. a et b En fait les deux références indiquent aussi que l'on peut montrer que cinq points suffisent (et que quatre ne suffisent pas) et donnent une généralisation pour tout polygone convexe, mais la preuve en est beaucoup plus difficile et ne fait plus appel au principe des tiroirs.
  2. Sur l'image ci contre, il s'agit des trois parallélogrammes formés par le triangle rouge et l'un des trois triangles noirs. Le fait que leur intersection soit non-vide n'invalide pas la méthode.
  3. Par exemple en disposant huit fous sur la rangée supérieure, et six sur la rangée inférieure, les coins étant exclus.
  4. En affinant ce raisonnement, (en) Yann Bugeaud, Approximation by Algebraic Numbers, CUP, (ISBN 978-0-521-82329-6, lire en ligne), p. 2, trouve deux entiers q (encore compris entre 1 et n) et p, vérifiant même : .

Références[modifier | modifier le code]

  1. (en) Benoît Rittaud et Albrecht Heeffer, « The pigeonhole principle, two centuries before Dirichlet », The Mathematical Intelligencer, vol. 36, no 2,‎ , p. 27-29 (DOI 10.1007/s00283-013-9389-1, lire en ligne).
  2. (en) Sanjeev Arora et Boaz Barak, Computational complexity, p. 310, Theorem 15.1
  3. a b et c Jean-Paul Delahaye, « Non, la géométrie du triangle n'est pas morte ! », Pour la Science,‎ (lire en ligne).
  4. a et b (en) Alexander Soifer (en), How Does One Cut a Triangle ?, Springer, (1re éd. 1990) (lire en ligne), chap. 7 (« Pursuit of the best result »).
  5. Jean-Paul Delahaye, « Logique et calcul : Le principe des tiroirs », Pour la science, no 433,‎ , p. 78.
  6. G. H. Hardy et E. M. Wright (trad. de l'anglais par François Sauvageot, préf. Catherine Goldstein), Introduction à la théorie des nombres [« An Introduction to the Theory of Numbers »] [détail de l’édition], p. 200-201.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]