Voir la source de Principe des tiroirs

En [[mathématiques]], le '''principe des tiroirs''' de [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet]], affirme que, si <math>n</math> [[chaussette]]s sont rangées dans <math>m</math> tiroirs, et que <math>m<n</math>, alors il y a un tiroir qui contient au moins deux chaussettes. Mathématiquement, le principe peut s'énoncer ainsi :
: Si <math>E</math> et <math>F</math> sont deux [[Ensemble fini|ensembles finis]] tels que <math>\operatorname{Card}(E) > \operatorname{Card}(F)</math>, alors il n'existe pas d'[[injection (mathématiques)|application injective]] de <math>E</math> dans <math>F</math>.

== Appellation ==

La première version du principe fut énoncée par [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet]] en [[1834]] sous le nom de ''{{lang|de|Schubfachprinzip}}'' (« principe du tiroir ») ; sa première utilisation lui est cependant antérieure d'au moins deux siècles<ref>{{Article|lang=en|titre=The pigeonhole principle, two centuries before Dirichlet|auteur=Benoît Rittaud|auteur2=Albrecht Heeffer|revue=[[The Mathematical Intelligencer]]|année=2014|vol=36|numéro=2|p.=27-29|doi=10.1007/s00283-013-9389-1|lire en ligne=https://biblio.ugent.be/publication/4115264/file/4115265.pdf}}.</ref>{{,}}<ref group = "note">Le principe est notamment utilisé au {{XVIIe siècle}} par [[Jean Leurechon]] dans sa ''Récréation mathématique: Composée de plusieurs problèmes plaisants''</ref>. Dans certains pays comme la [[Russie]], ce principe s'appelle le principe de Dirichlet (à ne pas confondre avec le [[principe de Dirichlet|principe du maximum]] pour les [[fonction harmonique|fonctions harmoniques]] portant le même nom). Ce principe est aussi appelé ''principe des tiroirs de Dirichlet-Schläfli''.
[[Fichier:TooManyPigeons.jpg|vignette|On a ici <math>n=10</math> pigeons répartis dans <math>m = 9</math> 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é ''{{lang|en|pigeonhole principle}}''. Il fait référence à la répartition des [[Columba (genre)|pigeons]] dans les cases (ou « boulins ») d'un [[Colombier (édifice)|pigeonnier]]{{Note|texte=Le mot ''pigeonhole'' désigne bien originellement les boulins, mais également et par analogie (depuis le {{s-|18}}) les tiroirs d'un bureau<ref>Voir [https://www.merriam-webster.com/words-at-play/pigeonhole-meaning-origin cette analyse] {{en}}  sur le site étymologique de Webster.</ref>.|groupe=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 <math>\left\lceil\frac{n}{m}\right\rceil</math> objets où <math>\lceil\ \rceil</math> est la fonction [[Partie entière et partie fractionnaire#Partie entière par excès|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 : <math>\left\lceil\frac{n}{m}\right\rceil=-E\left(-\frac{n}{m}\right)</math>.

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 [[Ensemble infini|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 [[Nombre cardinal|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 [[trivial]]e, 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 {{nombre|6000000 cheveux}} sur la tête (une tête normale a environ {{nombre|100000 [[cheveu]]x}}<ref>{{Youtube|langue = en|id = NdnByi_tK6Q|chaîne = [[Numberphile]]|titre =A Hairy Problem (and a Feathery Solution)}}</ref>). Or l'Australie compte plus de {{nombre|24000000 habitants}}. 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<ref name = "mathologer">{{Youtube|langue = en|chaîne = [[Mathologer]]|titre =The Pigeon Hole Principle: 7 gorgeous proofs |id =TCZ3YwbcDaw }}, chapitre 1.</ref>. 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<ref name = "mathologer"/>.

=== Géométrie ===
==== Subdivisions d'un triangle ====
[[Fichier:Medial Triangle.svg|vignette|droite|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 à <math>\textstyle\frac{1}{4}</math>. 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<ref name="delahaye">{{Ouvrage|langue=fr|auteur1=[[Jean-Paul Delahaye]]|titre=Inventions mathématiques|lieu=Paris|éditeur=[[Belin éditeur|Belin]]|collection=Pour la Science|année=2014|pages totales=191|passage=26-33|isbn=978-2-84245-128-8|lire en ligne=https://www.pourlascience.fr/sd/logique/non-la-geometrie-du-triangle-nest-pas-morte-2073.php|partie=Arts géométriques sur un plan|numéro chapitre=3|titre chapitre=Non, la géométrie du triangle n'est pas morte !}}.</ref>{{,}}<ref name="Soifer">{{Ouvrage|langue=en|auteur1=[[Alexander Soifer]]|titre=How Does One Cut a Triangle ?|éditeur=Springer|année=2009|année première édition=1990|lire en ligne=https://www.springer.com/fr/book/9780387746500|numéro chapitre=7|titre chapitre=Pursuit of the best result}}.</ref>{{,}}<ref group=note name="general">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.</ref>.

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 <math>\textstyle\frac{1}{2}</math> délimitent nécessairement une aire inférieure à <math>\textstyle\frac{1}{4}</math><ref name="delahaye"/>. En choisissant comme tiroirs les trois parallélogrammes formés par l'un des sommets et par le {{Lien|langue=en|trad=Medial triangle|fr=triangle des milieux}}<ref group=note>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 (mathématiques)|intersection]] soit [[Ensemble vide|non-vide]] n'invalide pas la méthode.</ref>, 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 <math>\textstyle\frac{1}{4}</math><ref name="delahaye"/>{{,}}<ref name="Soifer"/>{{,}}<ref group = note name="general"/>.
{{-}}

=== 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<ref name = "mathologer"/>. En effet les sommes des sous-ensembles peuvent valoir entre 1 et 955<ref group="note">En effet 955 = 91 + 92 + 93 + 94 + 95 + 96 + 97 + 98 + 99 + 100.</ref>, 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<ref name = "mathologer"/>{{,}}. 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<ref group="note">Par exemple si les nombres de départ sont 15, 22, 24, 29, 31, 37, 45, 68, 76 et 90, la méthode proposée ne permet pas de trouver que 15 + 37 + 68 = 22 + 24 + 29 + 45 = 120.</ref>.

==== Problèmes d'empilement ====
[[File:Empilement-carres-24.gif|thumb|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 et borne inférieure|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é]]<ref>{{Lien web|langue = anglais|titre = Packing Unit Squares in Squares|sous-titre = A Survey and New Results|site = [[Electronic Journal of Combinatorics]]|url = https://www.combinatorics.org/files/Surveys/ds7/ds7v5-2009/ds7-2009.html|auteur = Erich Friedman|année  = 2009}}.</ref>.

=== 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 choisi{{Note|texte=Par exemple en disposant huit fous sur la rangée supérieure, et six sur la rangée inférieure, les coins étant exclus.|groupe=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<ref name = "delahaye18">{{Article |langue=français |auteur=[[Jean-Paul Delahaye]]|périodique=[[Pour la science]]|titre =Logique et calcul|sous-titre = Le principe des tiroirs |numéro = 433|mois=janvier |année =2018|passage = 78}}.</ref>.

{{Diagramme d'échecs petit 
| tleft
|
|bd|bd|bd|bd|bd|bd|bd|bd
|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__
|__|bd|bd|bd|bd|bd|bd|__

| <center>Disposition où aucun des 14 fous ne menace les autres.</center>
}}

{| class="wikitable center" style = "height:15em; width:15em;"
|+ Partage d'un échiquier en 14 tiroirs colorés dans chacun desquels deux fous se menacent forcément
|-
| bgcolor="#FF8000"| || bgcolor="#000080"| || bgcolor="#00FFFF"| || bgcolor="#808040"| || bgcolor="#FF80FF"| || bgcolor="#FF0000"| || bgcolor="#FFFF00"| || bgcolor="#80FF00"|
|-
| bgcolor="#000080"| || bgcolor="#FF8000"| || bgcolor="#808040"| || bgcolor="#00FFFF"| || bgcolor="#FF0000"| || bgcolor="#FF80FF"| || bgcolor="#80FF00"| || bgcolor="#FFFF00"|
|-
| bgcolor="#800080"| || bgcolor="#808040"| || bgcolor="#FF8000"| || bgcolor="#FF0000"| || bgcolor="#00FFFF"| || bgcolor="#80FF00"| || bgcolor="#FF80FF"| || bgcolor="#008000"|
|-
| bgcolor="#808040"| || bgcolor="#800080"| || bgcolor="#FF0000"| || bgcolor="#FF8000"| || bgcolor="#80FF00"| || bgcolor="#00FFFF"| || bgcolor="#008000"| || bgcolor="#FF80FF"|
|-
| bgcolor="#FFFFFF"| || bgcolor="#FF0000"| || bgcolor="#800080"| || bgcolor="#80FF00"| || bgcolor="#FF8000"| || bgcolor="#008000"| || bgcolor="#00FFFF"| || bgcolor="#0080C0"|
|-
| bgcolor="#FF0000"| || bgcolor="#FFFFFF"| || bgcolor="#80FF00"| || bgcolor="#800080"| || bgcolor="#008000"| || bgcolor="#FF8000"| || bgcolor="#0080C0"| || bgcolor="#00FFFF"|
|-
| bgcolor="#000000"| || bgcolor="#80FF00"| || bgcolor="#FFFFFF"| || bgcolor="#008000"| || bgcolor="#800080"| || bgcolor="#0080C0"| || bgcolor="#FF8000"| || bgcolor="#C0C0C0"|
|-
| bgcolor="#80FF00"| || bgcolor="#000000"| || bgcolor="#008000"| || bgcolor="#FFFFFF"| || bgcolor="#0080C0"| || bgcolor="#800080"| || bgcolor="#C0C0C0"| || bgcolor="#FF8000"|
|}

=== Théorie des nombres ===
==== Approximation d'un réel ====

Soient un [[Nombre réel|réel]] {{math|''x''}} et un [[entier naturel|entier]] {{math|''n'' > 0}}. Pour tout réel {{math|''y''}}, on note {{math|<nowiki>{</nowiki>''y''<nowiki>}</nowiki>}} sa [[partie fractionnaire]] (c'est-à-dire la différence entre {{math|''y''}} et sa [[partie entière]]). Les {{math|''n'' + 1}} éléments {{math|0, {''x''}, … , {''n x''} }}de {{math|[0, 1[}} (non nécessairement distincts) se répartissent dans les {{math|''n''}} « tiroirs » {{math|[''r''/''n'', (''r'' + 1)/''n''[}}, où {{math|1=''r'' = 0, … , ''n'' – 1}}. Il existe donc un entier {{math|''r''}} et deux entiers {{math|0 ≤ ''k'' < ''l'' ≤ ''n''}} tels que :
<center><math>\frac rn\le\{kx\},\{lx\}<\frac{r+1}n.</math></center>
et donc :
<center><math>|\{kx\}-\{lx\}|<\frac1n</math>.</center>
En notant {{math|''p''}} la différence des parties entières de {{math|''lx''}} et {{math|''kx''}}, on en déduit :
<center><math>|(l-k)x-p|<\frac1n</math>,</center>
ou encore, en introduisant l'entier {{math|1=''q = l – k'' ≥ 1}} :
<center><math>\left|x-\frac pq\right|<\frac1{nq}\le\frac1{q^2}</math><ref>{{HardyWrightFr}}, {{p.|200-201}}.</ref>{{,}}<ref group="note">En affinant ce raisonnement, {{Ouvrage|langue=en|auteur1=Yann Bugeaud|titre=Approximation by Algebraic Numbers|éditeur=[[Cambridge University Press|CUP]]|année=2004|pages totales=292|passage=2|isbn=978-0-521-82329-6|lire en ligne={{Google Livres|iAg8FL5jKSgC|page=2}}}}, trouve deux entiers ''q'' (encore compris entre 1 et ''n'') et ''p'', vérifiant même : <math>\left|x-\frac pq\right|\le\frac1{(n+1)q}</math>.</ref>.</center>

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, [[Théorème d'approximation de Dirichlet#Utilisations|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 ====
{{Article détaillé|Recherche des deux points les plus rapprochés}}
[[File:Plus-proche-tiroir.png|thumb|left|Le grand rectangle est découpé en 8 carrés de côté <math>\frac{\delta}{2}</math>. Deux points dans un de ces 8 tiroirs sont séparés de moins de <math>\delta</math> : on ne peut donc pas placer 9 points séparés de <math>\delta</math> 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 (informatique)|diviser pour régner]]. Celle-ci nécessite de savoir combien, dans un rectangle de longueur <math>2\delta</math> et de largeur <math>\delta</math>, on peut avoir de points séparés par une distance au moins égale à <math>\delta</math><ref group="note">On se place ici dans le cas où tous les points sont dans un même plan, mais il est possible d'utiliser des arguments analogues pour des dimensions supérieures, par exemple avec 16 sous-cubes d'arête <math>\frac{\delta}{2}</math> si l'on a des points répartis dans l'espace.</ref>. Par principe des tiroirs on peut montrer que ce nombre est nécessairement inférieur ou égal à 8<ref name="rau">{{Article|langue = anglais|titre =Verification of Closest Pair of Points Algorithms|périodique = {{Lien| trad = Lecture Notes in Computer Science}} |date = 24 juin 2020|auteur1= Martin Rau|auteur2 = Tobias Nipkow|lire en ligne =https://link.springer.com/chapter/10.1007/978-3-030-51054-1_20}}, disponible en accès libre.</ref>.
[[File:Closest pair of points.svg|thumb|Une paire de points les plus proches (en rouge).]]
{{-}}

==== Lemme de l'étoile ====
{{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]].

==== 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 [[Collision (informatique)|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 <math>n</math>.
Dire que lorsque l'on répartit <math>n + 1</math> pigeons dans <math>n</math> trous, un trou au moins comprend 2 pigeons, c'est affirmer la [[Négation logique|négation]] de la proposition {{citation|il existe une répartition de <math>n + 1</math> pigeons dans <math>n</math> trous telle que chaque trou contienne au plus un seul pigeon}}.

Or on peut montrer que toutes les preuves par réfutations en [[Règle de résolution|résolution]] de la formule [[Logique propositionnelle|propositionnelle]] qui dit {{citation|il y a <math>n+1</math> pigeons dans <math>n</math> trous et au plus un pigeon par trou}} sont [[Comparaison asymptotique|asymptotiquement]] de taille au moins <math>\textstyle{2^{\frac{n}{20}}}</math>, c'est-à-dire que la taille minimale d'une preuve de cette proposition croît [[Fonction exponentielle|exponentiellement]] avec le nombre <math>n</math> de trous<ref>{{Ouvrage|langue=en|auteur1=Sanjeev Arora|auteur2=Boaz Barak|titre=Computational complexity|passage=p. 310, Theorem 15.1}}</ref>.

=== Exemple ===
On considère le cas où <math>n = 3</math>, c'est-à-dire que l'on essaie de ranger 4 pigeons dans 3 trous. Pour tout <math>p\in \{1,2,3,4\} </math> et tout <math>t \in \{1,2,3\}</math> on définit la [[variable booléenne]] <math>x_p^t</math> qui vaut <math>\mathtt{Vrai}</math> si le pigeon numéro <math>p</math> est dans le trou numéro <math>t</math> et qui vaut <math>\mathtt{Faux}</math> sinon<ref>{{Lien web|langue = français|titre = Le problème SAT|url = https://leria-info.univ-angers.fr/~jeanmichel.richer/uco_opt_combi_sat.php|site = [[AtlanSTIC#Le LERIA|leria-info.univ-angers.fr]]|auteur = Jean-Michel Richer}}, section 2.4.1 - le problème des pigeons.</ref>.

==== Expression du rangement des pigeons ====
Soit <math>p\in \{1,2,3,4\} </math>. On écrit que le pigeon numéro <math>p</math> est dans l'un des trois trous par la [[formule logique]] :
<center><math>x_p^1 \vee x_p^2 \vee x_p^3</math></center>
Le fait que chacun des quatre pigeons soit dans un des trous s'écrit donc :
<center><math>(x_1^1 \vee x_1^2 \vee x_1^3) \wedge (x_2^1 \vee x_2^2 \vee x_2^3) \wedge (x_3^1 \vee x_3^2 \vee x_3^3) \wedge (x_4^1 \vee x_4^2 \vee x_4^3)</math></center>

==== Expression de ce qu'aucun trou ne contient plus d'un pigeon ====
Soit <math>t \in \{1,2,3\}</math>. On écrit que le trou numéro <math>t</math> 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 :
<center><math>(\lnot x_1^t \wedge \lnot x_2^t \wedge \lnot x_3^t \wedge \lnot x_4^t) \vee (x_1^t \wedge \lnot x_2^t \wedge \lnot x_3^t \wedge \lnot x_4^t) \vee (\lnot x_1^t \wedge x_2^t \wedge \lnot x_3^t \wedge \lnot x_4^t) \vee (\lnot x_1^t \wedge \lnot x_2^t \wedge x_3^t \wedge \lnot x_4^t) \vee (\lnot x_1^t \wedge \lnot x_2^t \wedge \lnot x_3^t \wedge x_4^t)</math></center>

==== Formule logique résultante ====
La proposition {{citation|il existe une répartition de 4 pigeons dans 3 trous telle que chaque pigeon soit dans un trou et telle que chaque trou contienne au plus un seul pigeon}} s'écrit donc sous la forme de la [[Conjonction logique|conjonction]] de [[Clause (logique)|clauses]] suivante :
<center><math>(x_1^1 \vee x_1^2 \vee x_1^3) \wedge (x_2^1 \vee x_2^2 \vee x_2^3) \wedge (x_3^1 \vee x_3^2 \vee x_3^3) \wedge (x_4^1 \vee x_4^2 \vee x_4^3)</math></center>
<center><math>\bigwedge [(\lnot x_1^1 \wedge \lnot x_2^1 \wedge \lnot x_3^1 \wedge \lnot x_4^1) \vee (x_1^1 \wedge \lnot x_2^1 \wedge \lnot x_3^1 \wedge \lnot x_4^1) \vee (\lnot x_1^1 \wedge x_2^1 \wedge \lnot x_3^1 \wedge \lnot x_4^1) \vee (\lnot x_1^1 \wedge \lnot x_2^1 \wedge x_3^1 \wedge \lnot x_4^1) \vee (\lnot x_1^1 \wedge \lnot x_2^1 \wedge \lnot x_3^1 \wedge x_4^1)]</math></center>
<center><math>\bigwedge [(\lnot x_1^2 \wedge \lnot x_2^2 \wedge \lnot x_3^2 \wedge \lnot x_4^2) \vee (x_1^2 \wedge \lnot x_2^2 \wedge \lnot x_3^2 \wedge \lnot x_4^2) \vee (\lnot x_1^2 \wedge x_2^2 \wedge \lnot x_3^2 \wedge \lnot x_4^2) \vee (\lnot x_1^2 \wedge \lnot x_2^2 \wedge x_3^2 \wedge \lnot x_4^2) \vee (\lnot x_1^2 \wedge \lnot x_2^2 \wedge \lnot x_3^2 \wedge x_4^2)]</math></center>
<center><math>\bigwedge [(\lnot x_1^3 \wedge \lnot x_2^3 \wedge \lnot x_3^3 \wedge \lnot x_4^3) \vee (x_1^3 \wedge \lnot x_2^3 \wedge \lnot x_3^3 \wedge \lnot x_4^3) \vee (\lnot x_1^3 \wedge x_2^3 \wedge \lnot x_3^3 \wedge \lnot x_4^3) \vee (\lnot x_1^3 \wedge \lnot x_2^3 \wedge x_3^3 \wedge \lnot x_4^3) \vee (\lnot x_1^3 \wedge \lnot x_2^3 \wedge \lnot x_3^3 \wedge x_4^3)]</math></center>

==== Taille de la preuve de réfutation ====
{{...}}
On cherche à montrer que la formule logique précédente est fausse. Pour cela il faut montrer qu'aucune des <math>2^{12} = 4096</math> [[Instance (programmation)|instanciations]] des 12 variables <math>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</math> ne [[Satisfaisabilité|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 ===
{{références|groupe="note"}}

=== Références ===
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Lemme des bergers]]
* [[Nombre cardinal]]
* [[Théorie de Ramsey]]

=== Bibliographie ===
* {{Article|lang=en|titre=The pigeonhole principle, two centuries before Dirichlet|auteur=Benoît Rittaud|auteur2=Albrecht Heeffer|revue=[[The Mathematical Intelligencer]]|année=2014|vol=36|numéro=2|p.=27-29|doi=10.1007/s00283-013-9389-1|lire en ligne=https://biblio.ugent.be/publication/4115264/file/4115265.pdf|plume = oui}}
* {{article|titre=Trivial mais puissant : le principe des tiroirs|auteur=[[Jean-Paul Delahaye]]|revue=[[Pour la science]]|date=janvier 2018|vol=483}}

{{Portail|mathématiques}}

[[Catégorie:Théorie des ensembles]]
[[Catégorie:Théorème de combinatoire|Tiroirs]]