Pigeonhole principle

File:TooManyPigeons.jpg

Pigeons in holes. Here there are Template:Math pigeons in Template:Math holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon. (The top left hole has 2 pigeons.)

In mathematics, the pigeonhole principle states that if Template:Mvar items are put into Template:Mvar containers, with Template:Math, then at least one container must contain more than one item.<ref name=Herstein64>Template:Harvnb</ref> 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 of counting argument, can be used to demonstrate possibly unexpected results. For example, given that the population 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 to Jean Leurechon,<ref name=leurechon>Template:Cite journal</ref> it is commonly called Dirichlet's box principle or Dirichlet's drawer principle after an 1834 treatment of the principle by Peter Gustav Lejeune Dirichlet under the name {{#invoke:Lang|lang}} ("drawer principle" or "shelf principle").<ref>Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Electronic document, retrieved November 11, 2006</ref>

The principle has several generalizations and can be stated in various ways. In a more quantified version: for natural numbers Template:Mvar and Template:Mvar, if Template:Math objects are distributed among Template:Mvar sets, the pigeonhole principle asserts that at least one of the sets will contain at least Template:Math objects.<ref>Template:Harvnb</ref> For arbitrary Template:Mvar and Template:Mvar, this generalizes to <math>k + 1 = \lfloor(n - 1)/m \rfloor + 1 = \lceil n/m\rceil</math>, where <math>\lfloor\cdots\rfloor</math> and <math>\lceil\cdots\rceil</math> denote the floor and ceiling functions, respectively.

Though the principle's most straightforward application is to finite sets (such as pigeons and boxes), it is also used with infinite sets that cannot be put into one-to-one correspondence. To do so requires the formal statement of the pigeonhole principle: "there does not exist an injective function whose codomain is smaller than its domain". Advanced mathematical proofs like Siegel's lemma build upon this more general concept.

Etymology

File:Pigeon-hole messagebox 3.jpg

Pigeon-hole messageboxes at Stanford University

Dirichlet published his works in both French and German, using either the German {{#invoke:Lang|lang}} or the French {{#invoke:Lang|lang}}. The strict original meaning of these terms corresponds to the English drawer, that is, an open-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 to pigeonhole in the sense of a small 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 translation pigeonhole may be a better rendering of Dirichlet's original "drawer". That understanding of the term pigeonhole, referring to some furniture features, is fading—especially among those who do not speak English natively but as a lingua 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 "{{#invoke:Lang|lang}}".<ref>Template:Cite book</ref>

Besides the original terms "{{#invoke:Lang|lang}}" in German<ref>Template:Cite book</ref> and "{{#invoke:Lang|lang}}" in French,<ref>Template:Cite book</ref> other literal translations are still in use in Arabic ({{#invoke:Lang|lang}}), Bulgarian ("{{#invoke:Lang|lang}}"), Chinese ("{{#invoke:Lang|lang}}"), Danish ("{{#invoke:Lang|lang}}"), Dutch ("{{#invoke:Lang|lang}}"), Hungarian ("{{#invoke:Lang|lang}}"), Italian ("{{#invoke:Lang|lang}}"), Japanese ("{{#invoke:Lang|lang}}"), Persian ("{{#invoke:Lang|lang}}"), Polish ("{{#invoke:Lang|lang}}"), Portuguese ("{{#invoke:Lang|lang}}"), Swedish ("{{#invoke:Lang|lang}}"), Turkish ("{{#invoke:Lang|lang}}"), and Vietnamese ("{{#invoke:Lang|lang}}").

Examples

Sock picking

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 (Template:Math, using one pigeonhole per color), the answer is three (Template:Math items). Either you have three of one color, or you have two of one color and one of the other.Template:Citation needed

Hand shaking

If Template:Math people can shake hands with one another (where Template:Math), 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 to Template:Math, there are Template:Math possible holes. On the other hand, either the "0" hole, the Template:Math hole, or both must be empty, for it is impossible (if Template:Math) for some person to shake hands with everybody else while some person shakes hands with nobody. This leaves Template:Math people to be placed into at most Template:Math non-empty holes, so the principle applies.

This hand-shaking example is equivalent to the statement that in any graph with more than one vertex, there is at least one pair of vertices that share the same degree.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> This can be seen by associating each person with a vertex and each edge with a handshake.Template:Citation needed

Hair counting

One can demonstrate there must be at least two people in London with the same number of hairs on their heads as follows.<ref>Template:Cite book</ref><ref>To avoid a slightly messier presentation, this example only refers to people who are not bald.</ref> Since a typical human head has an average 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 Template:Math holes). There are more than 1,000,000 people in London (Template:Math 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, Template:Math). Assuming London has 9.002 million people,<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> 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 (Template:Math) 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 of probability distribution).Template:Citation needed

There is a passing, satirical, allusion in English to this version of the principle in A History of the Athenian Society, prefixed to A 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).<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> It seems that the question whether there were any two persons in the World that have an equal number of hairs on their head? had been raised in The Athenian Mercury before 1704.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Perhaps the first written reference to the pigeonhole principle appears in a short sentence from the French Jesuit Jean Leurechon's 1622 work Selectæ Propositiones:<ref name=leurechon/> "It is necessary that two men have the same number of hairs, écus, or other things, as each other."<ref>Template:Citation</ref> 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.<ref name=leurechon/>

The birthday problem

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}}

The birthday problem asks, for a set of Template:Math 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.

Team tournament

Imagine seven people who want to play in a tournament of teams Template:Math items), with a limitation of only four teams Template:Math 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:Template:Citation needed

<math display=block> \left\lfloor \frac{n-1}{m} \right\rfloor + 1 = \left\lfloor \frac{7-1}{4} \right\rfloor + 1 = \left\lfloor \frac64 \right\rfloor + 1 = 1 + 1 = 2 </math>

Subset sum

Any subset of size six from the set <math> S = \{ 1,2,3, \dots ,9\} </math> must contain two elements whose sum is 10. The pigeonholes will be labeled by the two element subsets <math> \{1,9\}, \{2,8\}, \{3,7\}, \{4,6\} </math> and the singleton <math> \{5\} </math> , 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.<ref>Template:Harvnb</ref>

Hashing

Hashing in computer science is the process of mapping an arbitrarily large set of data Template:Math to Template:Math fixed-size values. This has applications in caching 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 set Template:Math is larger than the number of available unique hash codes Template:Math, 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 set Template:Math, some objects must necessarily share the same hash code.Template:Citation needed

Uses and applications

The principle can be used to prove that any lossless 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 length Template:Mvar could be mapped to the (much) smaller set of all sequences of length less than Template:Mvar without collisions (because the compression is lossless), a possibility that the pigeonhole principle excludes.

File:Dudeney no 3 pawns in line.svg

The pigeonhole principle gives an upper bound of Template:Math in the no-three-in-line problem for the number of points that can be placed on an Template:Math lattice without any three being colinear – in this case, 16 pawns on a regular chessboard <ref>Template:Cite magazine</ref>

A notable problem in mathematical analysis is, for a fixed irrational number Template:Mvar, to show that the set Template:Tmath of fractional parts is dense in Template:Math. One finds that it is not easy to explicitly find integers Template:Mvar such that <math>|na-m| < e,</math> where Template:Math is a small positive number and Template:Mvar is some arbitrary irrational number. But if one takes Template:Mvar such that Template:Tmath by the pigeonhole principle there must be <math>n_1, n_2 \in \{1, 2, \ldots, M+1\}</math> such that Template:Math and Template:Math are in the same integer subdivision of size Template:Tmath (there are only Template:Mvar such subdivisions between consecutive integers). In particular, one can find Template:Math such that

<math>n_1 a \in \left(p+\frac k M,\ p + \frac{k+1}{M}\right), \quad n_2 a \in \left(q+ \frac k M,\ q+\frac{k+1}{M}\right),</math>

for some Template:Mvar integers and Template:Mvar in Template:Math}. One can then easily verify that

<math>(n_2 - n_1)a \in \left(q-p-\frac 1 M, q-p+\frac 1 M \right).</math>

This implies that Template:Tmath where Template:Math or Template:Math. This shows that 0 is a limit point of {[[[:Template:Math]]]}. One can then use this fact to prove the case for Template:Mvar in Template:Math: find Template:Mvar such that Template:Tmath then if Template:Tmath the proof is complete. Otherwise

<math>p \in \left(\frac j M, \frac{j+1}{M}\right],</math>

and by setting

<math>k = \sup \left\{r \in N : r[na] < \frac j M \right\},</math>

one obtains

<math>\Bigl| \bigl[ (k+1)na \bigr] - p \Bigr| < \frac 1 M < e.</math>

Variants occur in a number of proofs. In the proof of the pumping 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.<ref>Introduction to Formal Languages and Automata, Peter Linz, pp. 115–116, Jones and Bartlett Learning, 2006</ref> In Fisk's solution to the Art gallery problem a sort of converse is used: If Template:Mvar objects are placed into Template:Mvar boxes, then there is a box containing at most Template:Tmath objects.<ref>Computational Geometry in C, Cambridge Tracts in Theoretical Computer Science, 2nd Edition, Joseph O'Rourke, page 9.</ref>

Alternative formulations

The following are alternative formulations of the pigeonhole principle.

1. If Template:Math objects are distributed over Template:Math places, and if Template:Math, then some place receives at least two objects.<ref name=Herstein64 />
2. (equivalent formulation of 1) If Template:Math objects are distributed over Template:Math places in such a way that no place receives more than one object, then each place receives exactly one object.<ref name=Herstein64 />
3. (generalization of 1) If Template:Math and Template:Math are sets, and the cardinality of Template:Math is greater than the cardinality of Template:Math, then there is no injective function from Template:Math to Template:Math.
4. If Template:Math objects are distributed over Template:Math places, and if Template:Math, then some place receives no object.
5. (equivalent formulation of 4) If Template:Math objects are distributed over Template:Math places in such a way that no place receives no object, then each place receives exactly one object.<ref>Template:Harvnb</ref>
6. (generalization of 4) If Template:Math and Template:Math are sets, and the cardinality of Template:Math is less than the cardinality of Template:Math, then there is no surjective function from Template:Math to Template:Math.

Strong form

Let Template:Math be positive integers. If

<math>q_1 + q_2 + \cdots + q_n - n + 1</math>

objects are distributed into Template:Math boxes, then either the first box contains at least Template:Math objects, or the second box contains at least Template:Math objects, ..., or the Template:Mathth box contains at least Template:Math objects.<ref>Template:Harvnb</ref>

The simple form is obtained from this by taking Template:Math, which gives Template:Math objects. Taking Template:Math gives the more quantified version of the principle, namely:

Let Template:Math and Template:Math be positive integers. If Template:Math objects are distributed into Template:Math boxes, then at least one of the boxes contains Template:Math or more of the objects.<ref>In the lead section this was presented with the substitutions Template:Math and Template:Math.</ref>

This can also be stated as, if Template:Math discrete objects are to be allocated to Template:Math containers, then at least one container must hold at least <math>\lceil k/n \rceil</math> objects, where <math>\lceil x\rceil</math> is the ceiling function, denoting the smallest integer larger than or equal to Template:Math. Similarly, at least one container must hold no more than <math>\lfloor k/n \rfloor</math> objects, where <math>\lfloor x \rfloor</math> is the floor function, denoting the largest integer smaller than or equal to Template:Math.Template:Citation needed

Generalizations of the pigeonhole principle

Template:Citations needed A probabilistic generalization of the pigeonhole principle states that if Template:Math pigeons are randomly put into Template:Math pigeonholes with uniform probability Template:Math, then at least one pigeonhole will hold more than one pigeon with probability

<math>1 - \frac{(m)_n}{m^n}, </math>

where Template:Math is the falling factorial Template:Math. For Template:Math and for Template:Math (and Template:Math), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For Template:Math (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 (Template:Math), 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 the birthday paradox.

A further probabilistic generalization is that when a real-valued random variable Template:Math has a finite mean Template:Math, then the probability is nonzero that Template:Math is greater than or equal to Template:Math, and similarly the probability is nonzero that Template:Math is less than or equal to Template:Math. To see that this implies the standard pigeonhole principle, take any fixed arrangement of Template:Math pigeons into Template:Math holes and let Template:Math be the number of pigeons in a hole chosen uniformly at random. The mean of Template:Math is Template:Math, so if there are more pigeons than holes the mean is greater than one. Therefore, Template:Math is sometimes at least 2.

Infinite sets

The pigeonhole principle can be extended to infinite sets by phrasing it in terms of cardinal numbers: if the cardinality of set Template:Mvar is greater than the cardinality of set Template:Mvar, then there is no injection from Template:Mvar to Template:Mvar. However, in this form the principle is tautological, since the meaning of the statement that the cardinality of set Template:Mvar is greater than the cardinality of set Template:Mvar is exactly that there is no injective map from Template:Mvar to Template:Mvar. 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 are Dedekind finite: Let Template:Mvar and Template:Mvar be finite sets. If there is a surjection from Template:Mvar to Template:Mvar that is not injective, then no surjection from Template:Mvar to Template:Mvar is injective. In fact no function of any kind from Template:Mvar to Template:Mvar 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 if Template:Mvar and Template:Mvar are finite sets such that any surjective function from Template:Mvar to Template:Mvar is not injective, then there exists an element Template:Mvar of Template:Mvar such that there exists a bijection between the preimage of Template:Mvar and Template:Mvar. This is a quite different statement, and is absurd for large finite cardinalities.

Quantum mechanics

Yakir Aharonov et al. presented arguments that quantum mechanics may violate the pigeonhole principle, and proposed interferometric experiments to test the pigeonhole principle in quantum mechanics.<ref>Template:Cite journal</ref>

Later research has called this conclusion into question.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref name="Rae Forgan 2014">Template:Cite arXiv</ref> In a January 2015 arXiv preprint, researchers Alastair Rae and Ted Forgan at the University of Birmingham performed a theoretical wave function analysis, employing the standard pigeonhole principle, on the flight of electrons at various energies through an interferometer. 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 the lattice 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.Template:Citation needed

See also

• Axiom of choice
• Blichfeldt's theorem
• Combinatorial principles
• Combinatorial proof
• Dedekind-infinite set
• Dirichlet's approximation theorem
• Hilbert's paradox of the Grand Hotel
• Multinomial theorem
• Pochhammer symbol
• Ramsey's theorem

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

External links

• Template:Springer
• "The strange case of The Pigeon-hole Principle"; Edsger Dijkstra investigates interpretations and reformulations of the principle.
• "The Pigeon Hole Principle"; Elementary examples of the principle in use by Larry Cusick.
• "Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles"; basic Pigeonhole Principle analysis and examples by Alexander Bogomolny.
• "16 fun applications of the pigeonhole principle"; Interesting facts derived by the principle.
• {{#invoke:citation/CS1|citation

|CitationClass=web }}Template:Cbignore