Inmathematics, thepigeonhole principle states that ifn items are put intom containers, withn >m, then at least one container must contain more than one item.[1] For example, of three gloves, at least two must be right-handed or at least two must be left-handed, because there are three objects but only two categories of handedness to put them into. This seemingly obvious statement, a type ofcounting argument, can be used to demonstrate possibly unexpected results. For example, given that thepopulation of London is more than one unit greater than the maximum number of hairs that can be on a human's head, the principle requires that there must be at least two people in London who have the same number of hairs on their heads.
Although the pigeonhole principle appears as early as 1624 in a book attributed toJean Leurechon,[2] it is commonly calledDirichlet's box principle orDirichlet's drawer principle after an 1834 treatment of the principle byPeter Gustav Lejeune Dirichlet under the nameSchubfachprinzip ("drawer principle" or "shelf principle").[3]
The principle has several generalizations and can be stated in various ways. In a more quantified version: fornatural numbersk andm, ifn =km + 1 objects are distributed amongm sets, the pigeonhole principle asserts that at least one of the sets will contain at leastk + 1 objects.[4] For arbitraryn andm, this generalizes to, where and denote thefloor and ceiling functions, respectively.
Though the principle's most straightforward application is tofinite sets (such as pigeons and boxes), it is also used withinfinite sets that cannot be put intoone-to-one correspondence. To do so requires the formal statement of the pigeonhole principle: "there does not exist aninjective function whosecodomain is smaller than itsdomain". Advanced mathematical proofs likeSiegel's lemma build upon this more general concept.
Dirichlet published his works in both French and German, using either the GermanSchubfach or the Frenchtiroir. The strict original meaning of these terms corresponds to the Englishdrawer, that is, anopen-topped box that can be slid in and out of the cabinet that contains it. (Dirichlet wrote about distributing pearls among drawers.) These terms morphed topigeonhole in the sense of asmall open space in a desk, cabinet, or wall for keeping letters or papers, metaphorically rooted in structures that house pigeons.
Because furniture with pigeonholes is commonly used for storing or sorting things into many categories (such as letters in a post office or room keys in a hotel), the translationpigeonhole may be a better rendering of Dirichlet's original "drawer". That understanding of the termpigeonhole, referring to some furniture features, is fading—especially among those who do not speak English natively but as alingua franca in the scientific world—in favor of the more pictorial interpretation, literally involving pigeons and holes. The suggestive (though not misleading) interpretation of "pigeonhole" as "dovecote" has lately found its way back to a German back-translation of the "pigeonhole principle" as the "Taubenschlagprinzip".[5]
Besides the original terms "Schubfachprinzip" in German[6] and "Principe des tiroirs" inFrench,[7] other literal translations are still in use inArabic ("مبدأ برج الحمام"),Bulgarian ("принцип на чекмеджетата"),Chinese ("抽屉原理"),Danish ("Skuffeprincippet"),Dutch ("ladenprincipe"),Hungarian ("skatulyaelv"),Italian ("principio dei cassetti"),Japanese ("引き出し論法"),Persian ("اصل لانه کبوتری"),Polish ("zasada szufladkowa"),Portuguese ("Princípio das Gavetas"),Swedish ("Lådprincipen"),Turkish ("çekmece ilkesi"), andVietnamese ("nguyên lý hộp").
Suppose a drawer contains a mixture of black socks and blue socks, each of which can be worn on either foot. You pull a number of socks from the drawer without looking. What is the minimum number of pulled socks required to guarantee a pair of the same color? By the pigeonhole principle (m = 2, using one pigeonhole per color), the answer is three (n = 3 items). Either you havethree of one color, or you havetwo of one color andone of the other.[citation needed]
Ifn people can shake hands with one another (wheren > 1), the pigeonhole principle shows that there is always a pair of people who will shake hands with the same number of people. In this application of the principle, the "hole" to which a person is assigned is the number of hands that person shakes. Since each person shakes hands with some number of people from 0 ton − 1, there aren possible holes. On the other hand, either the "0" hole, the"n − 1" hole, or both must be empty, for it is impossible (ifn > 1) for some person to shake hands with everybody else while some person shakes hands with nobody. This leavesn people to be placed into at mostn − 1 non-empty holes, so the principle applies.
This hand-shaking example is equivalent to the statement that in anygraph with more than onevertex, there is at least one pair of vertices that share the samedegree.[8] This can be seen by associating each person with a vertex and eachedge with a handshake.[citation needed]
One can demonstrate there must be at least two people inLondon with the same number of hairs on their heads as follows.[9][10] Since a typical human head has anaverage of around 150,000 hairs, it is reasonable to assume (as an upper bound) that no one has more than 1,000,000 hairs on their head(m = 1 million holes). There are more than 1,000,000 people in London (n is bigger than 1 million items). Assigning a pigeonhole to each number of hairs on a person's head, and assigning people to pigeonholes according to the number of hairs on their heads, there must be at least two people assigned to the same pigeonhole by the 1,000,001st assignment (because they have the same number of hairs on their heads; or,n >m). Assuming London has 9.002 million people,[11] it follows that at least ten Londoners have the same number of hairs, as having nine Londoners in each of the 1 million pigeonholes accounts for only 9 million people.
For the average case (m = 150,000) with the constraint: fewest overlaps, there will be at most one person assigned to every pigeonhole and the 150,001st person assigned to the same pigeonhole as someone else. In the absence of this constraint, there may be empty pigeonholes because the "collision" happens before the 150,001st person. The principle just proves the existence of an overlap; it says nothing about the number of overlaps (which falls under the subject ofprobability distribution).[citation needed]
There is a passing, satirical, allusion in English to this version of the principle inA History of the Athenian Society, prefixed toA Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries (printed for Andrew Bell, London, 1710).[12] It seems that the questionwhether there were any two persons in the World that have an equal number of hairs on their head? had been raised inThe Athenian Mercury before 1704.[13][14]
Perhaps the first written reference to the pigeonhole principle appears in a short sentence from the French JesuitJean Leurechon's 1622 workSelectæ Propositiones:[2] "It is necessary that two men have the same number of hairs,écus, or other things, as each other."[15] The full principle was spelled out two years later, with additional examples, in another book that has often been attributed to Leurechon, but might be by one of his students.[2]
The birthday problem asks, for a set ofn randomly chosen people, what is the probability that some pair of them will have the same birthday? The problem itself is mainly concerned with counterintuitive probabilities, but we can also tell by the pigeonhole principle that among 367 people, there is at least one pair of people who share the same birthday with 100% probability, as there are only 366 possible birthdays to choose from.
Imagine seven people who want to play in a tournament of teams(n = 7 items), with a limitation of only four teams(m = 4 holes) to choose from. The pigeonhole principle tells us that they cannot all play for different teams; there must be at least one team featuring at least two of the seven players:[citation needed]
Anysubset of size six from theset must contain two elements whose sum is 10. The pigeonholes will be labeled by the two element subsets and thesingleton , five pigeonholes in all. When the six "pigeons" (elements of the size six subset) are placed into these pigeonholes, each pigeon going into the pigeonhole that has it contained in its label, at least one of the pigeonholes labeled with a two-element subset will have two pigeons in it.[16]
Hashing incomputer science is the process of mapping an arbitrarily large set of datan tom fixed-size values. This has applications incaching whereby large data sets can be stored by a reference to their representative values (their "hash codes") in a "hash table" for fast recall. Typically, the number of unique objects in a data setn is larger than the number of available unique hash codesm, and the pigeonhole principle holds in this case that hashing those objects is no guarantee of uniqueness, since if you hashed all objects in the data setn, some objects must necessarily share the same hash code.[citation needed]
The principle can be used to prove that anylossless compression algorithm, provided it makes some inputs smaller (as "compression" suggests), will also make some other inputs larger. Otherwise, the set of all input sequences up to a given lengthL could be mapped to the (much) smaller set of all sequences of length less thanL without collisions (because the compression is lossless), a possibility that the pigeonhole principle excludes.
A notable problem inmathematical analysis is, for a fixedirrational numbera, to show that the set offractional parts isdense in[0, 1]. One finds that it is not easy to explicitly find integersn, m such that wheree > 0 is a small positive number anda is some arbitrary irrational number. But if one takesM such that by the pigeonhole principle there must be such thatn1a andn2a are in the same integer subdivision of size (there are onlyM such subdivisions between consecutive integers). In particular, one can findn1,n2 such that
for somep, q integers andk in{0, 1, ...,M − 1}. One can then easily verify that
This implies that wheren =n2 −n1 orn =n1 −n2. This shows that 0 is a limit point of {[na]}. One can then use this fact to prove the case forp in(0, 1]: findn such that then if the proof is complete. Otherwise
and by setting
one obtains
Variants occur in a number of proofs. In the proof of thepumping lemma for regular languages, a version that mixes finite and infinite sets is used: If infinitely many objects are placed into finitely many boxes, then two objects share a box.[18] In Fisk's solution to theArt gallery problem a sort of converse is used: Ifn objects are placed intok boxes, then there is a box containing at most objects.[19]
The following are alternative formulations of the pigeonhole principle.
Letq1,q2, ...,qn be positive integers. If
objects are distributed inton boxes, then either the first box contains at leastq1 objects, or the second box contains at leastq2 objects, ..., or thenth box contains at leastqn objects.[21]
The simple form is obtained from this by takingq1 =q2 = ... =qn = 2, which givesn + 1 objects. Takingq1 =q2 = ... =qn =r gives the more quantified version of the principle, namely:
Letn andr be positive integers. Ifn(r − 1) + 1 objects are distributed inton boxes, then at least one of the boxes containsr or more of the objects.[22]
This can also be stated as, ifk discrete objects are to be allocated ton containers, then at least one container must hold at least objects, where is theceiling function, denoting the smallest integer larger than or equal tox. Similarly, at least one container must hold no more than objects, where is thefloor function, denoting the largest integer smaller than or equal tox.[citation needed]
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Pigeonhole principle" – news ·newspapers ·books ·scholar ·JSTOR(February 2025) (Learn how and when to remove this message) |
A probabilistic generalization of the pigeonhole principle states that ifn pigeons are randomly put intom pigeonholes with uniform probability1/m, then at least one pigeonhole will hold more than one pigeon with probability
where(m)n is thefalling factorialm(m − 1)(m − 2)...(m −n + 1). Forn = 0 and forn = 1 (andm > 0), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. Forn >m (more pigeons than pigeonholes) it is one, in which case it coincides with the ordinary pigeonhole principle. But even if the number of pigeons does not exceed the number of pigeonholes (n ≤m), due to the random nature of the assignment of pigeons to pigeonholes there is often a substantial chance that clashes will occur. For example, if 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon; for 5 pigeons and 10 holes, that probability is 69.76%; and for 10 pigeons and 20 holes it is about 93.45%. If the number of holes stays fixed, there is always a greater probability of a pair when you add more pigeons. This problem is treated at much greater length in thebirthday paradox.
A further probabilistic generalization is that when a real-valuedrandom variableX has a finitemeanE(X), then the probability is nonzero thatX is greater than or equal toE(X), and similarly the probability is nonzero thatX is less than or equal toE(X). To see that this implies the standard pigeonhole principle, take any fixed arrangement ofn pigeons intom holes and letX be the number of pigeons in a hole chosen uniformly at random. The mean ofX isn/m, so if there are more pigeons than holes the mean is greater than one. Therefore,X is sometimes at least 2.
| This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Pigeonhole principle" – news ·newspapers ·books ·scholar ·JSTOR(February 2025) (Learn how and when to remove this message) |
The pigeonhole principle can be extended toinfinite sets by phrasing it in terms ofcardinal numbers: if the cardinality of setA is greater than the cardinality of setB, then there is no injection fromA toB. However, in this form the principle istautological, since the meaning of the statement that the cardinality of setA is greater than the cardinality of setB is exactly that there is no injective map fromA toB. However, adding at least one element to a finite set is sufficient to ensure that the cardinality increases.
Another way to phrase the pigeonhole principle for finite sets is similar to the principle that finite sets areDedekind finite: LetA andB be finite sets. If there is a surjection fromA toB that is not injective, then no surjection fromA toB is injective. In fact no function of any kind fromA toB is injective. This is not true for infinite sets: Consider the function on the natural numbers that sends 1 and 2 to 1, 3 and 4 to 2, 5 and 6 to 3, and so on.
There is a similar principle for infinite sets: If uncountably many pigeons are stuffed into countably many pigeonholes, there will exist at least one pigeonhole having uncountably many pigeons stuffed into it.
This principle is not a generalization of the pigeonhole principle for finite sets however: It is in general false for finite sets. In technical terms it says that ifA andB are finite sets such that any surjective function fromA toB is not injective, then there exists an elementb ofB such that there exists a bijection between the preimage ofb andA. This is a quite different statement, and is absurd for large finite cardinalities.
Yakir Aharonov et al. presented arguments thatquantum mechanics may violate the pigeonhole principle, and proposedinterferometric experiments to test the pigeonhole principle in quantum mechanics.[23]
Later research has called this conclusion into question.[24][25] In a January 2015arXiv preprint, researchers Alastair Rae and Ted Forgan at the University of Birmingham performed a theoreticalwave function analysis, employing the standard pigeonhole principle, on the flight of electrons at various energies through aninterferometer. If the electrons had no interaction strength at all, they would each produce a single, perfectly circular peak. At high interaction strength, each electron produces four distinct peaks, for a total of 12 peaks on the detector; these peaks are the result of the four possible interactions each electron could experience (alone, together with the first other particle only, together with the second other particle only, or all three together). If the interaction strength was fairly low, as would be the case in many real experiments, the deviation from a zero-interaction pattern would be nearly indiscernible, much smaller than thelattice spacing of atoms in solids, such as the detectors used for observing these patterns. This would make it very difficult or impossible to distinguish a weak-but-nonzero interaction strength from no interaction whatsoever, and thus give an illusion of three electrons that did not interact despite all three passing through two paths.[citation needed]
{{cite book}}:ISBN / Date incompatibility (help){{citation}}:ISBN / Date incompatibility (help)