Pigeonhole principle

Pigeon-hole messageboxes at Stanford University

Dirichlet published his works in both French and German, using either the German Schubfach or the French tiroir. 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 "Taubenschlagprinzip".[5]

Besides the original terms "Schubfachprinzip" in German[6] and "Principe des tiroirs" in French,[7] other literal translations are still in use in Arabic ("مبدأ برج الحمام"), 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"), and Vietnamese ("nguyên lý hộp").

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

The pigeonhole principle gives an upper bound of 2n in the no-three-in-line problem for the number of points that can be placed on an n × n lattice without any three being colinear – in this case, 16 pawns on a regular chessboard [17]

A notable problem in mathematical analysis is, for a fixed irrational number a, to show that the set ${\displaystyle \{[na]:n\in \mathbb {Z} \}}$ of fractional parts is dense in [0, 1]. One finds that it is not easy to explicitly find integers n, m such that ${\displaystyle |na-m|<e,}$ where e > 0 is a small positive number and a is some arbitrary irrational number. But if one takes M such that ${\displaystyle {\tfrac {1}{M}}<e,}$ by the pigeonhole principle there must be ${\displaystyle n_{1},n_{2}\in \{1,2,\ldots ,M+1\}}$ such that n₁a and n₂a are in the same integer subdivision of size ${\displaystyle {\tfrac {1}{M}}}$ (there are only M such subdivisions between consecutive integers). In particular, one can find n₁, n₂ such that

${\displaystyle 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),}$

for some p, q integers and k in {0, 1, ..., M − 1}. One can then easily verify that

${\displaystyle (n_{2}-n_{1})a\in \left(q-p-{\frac {1}{M}},q-p+{\frac {1}{M}}\right).}$

This implies that ${\displaystyle [na]<{\tfrac {1}{M}}<e,}$ where n = n₂ − n₁ or n = n₁ − n₂. This shows that 0 is a limit point of {[na]}. One can then use this fact to prove the case for p in (0, 1]: find n such that ${\displaystyle [na]<{\tfrac {1}{M}}<e;}$ then if ${\displaystyle p\in {\bigl (}0,{\tfrac {1}{M}}{\bigr ]},}$ the proof is complete. Otherwise

${\displaystyle p\in \left({\frac {j}{M}},{\frac {j+1}{M}}\right],}$

and by setting

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

one obtains

${\displaystyle {\Bigl |}{\bigl [}(k+1)na{\bigr ]}-p{\Bigr |}<{\frac {1}{M}}<e.}$

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.[18] In Fisk's solution to the Art gallery problem a sort of converse is used: If n objects are placed into k boxes, then there is a box containing at most ${\displaystyle {\tfrac {n}{k}}}$ objects.[19]

The following are alternative formulations of the pigeonhole principle.

1. If n objects are distributed over m places, and if n > m, then some place receives at least two objects.[1]
2. (equivalent formulation of 1) If n objects are distributed over n places in such a way that no place receives more than one object, then each place receives exactly one object.[1]
3. If n objects are distributed over m places, and if n < m, then some place receives no object.
4. (equivalent formulation of 3) If n objects are distributed over n places in such a way that no place receives no object, then each place receives exactly one object.[20]

Let q₁, q₂, ..., q_n be positive integers. If

${\displaystyle q_{1}+q_{2}+\cdots +q_{n}-n+1}$

objects are distributed into n boxes, then either the first box contains at least q₁ objects, or the second box contains at least q₂ objects, ..., or the nth box contains at least q_n objects.[21]

The simple form is obtained from this by taking q₁ = q₂ = ... = q_n = 2, which gives n + 1 objects. Taking q₁ = q₂ = ... = q_n = r gives the more quantified version of the principle, namely:

Let n and r be positive integers. If n(r - 1) + 1 objects are distributed into n boxes, then at least one of the boxes contains r or more of the objects.[22]

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

A probabilistic generalization of the pigeonhole principle states that if n pigeons are randomly put into m pigeonholes with uniform probability 1/m, then at least one pigeonhole will hold more than one pigeon with probability

${\displaystyle 1-{\frac {(m)_{n}}{m^{n}}},}$

where (m)_n is the falling factorial m(m − 1)(m − 2)...(m − n + 1). For n = 0 and for n = 1 (and m > 0), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For n > 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 the birthday paradox.

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

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

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.[23] Later research has called this conclusion into question.[24][25] 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.

• 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

• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pentice Hall, ISBN 978-0-13-602040-0
• Fletcher, Peter; Patty, C.Wayne (1987), Foundations of Higher Mathematics, PWS-Kent, ISBN 978-0-87150-164-6
• Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics: An Applied Introduction (3rd ed.), Addison-Wesley, ISBN 978-0-201-54983-6
• Herstein, I. N. (1964), Topics In Algebra, Waltham: Blaisdell Publishing Company, ISBN 978-1114541016

• "Dirichlet box principle", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• "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.
• "How Many Humans Have the Same Number of Body Hairs?". PBS Infinite Series. December 1, 2016. Archived from the original on 2021-12-11 – via YouTube.