Pigeonhole principle

In mathematics and computer science, the pigeonhole principle states that if n items are put into m pigeonholes with n > m, then at least one pigeonhole must contain more than one item. This theorem is exemplified in reallife by truisms like "there must be at least two left gloves or two right gloves in a group of three gloves". It is an example of a counting argument, and despite seeming intuitive it can be used to demonstrate possibly unexpected results; for example, that two people in London have the same number of hairs on their heads (see below).
The first formalization of the idea is believed to have been made by Johann Dirichlet in 1834 under the name Schubfachprinzip ("drawer principle" or "shelf principle"). For this reason it is also commonly called Dirichlet's box principle, Dirichlet's drawer principle or simply "Dirichlet principle"—a name that could also refer to the minimum principle for harmonic functions. The original "drawer" name is still in use in French ("principe des tiroirs"), Italian ("principio dei cassetti") and German ("Schubfachprinzip").
Though the most straightforward application is to finite sets (such as pigeons and boxes), it is also used with infinite sets that cannot be put into onetoone correspondence. To do so requires the formal statement of the pigeonhole principle, which is "there does not exist an injective function on finite sets whose codomain is smaller than its domain". Advanced mathematical proofs like Siegel's lemma build upon this more general concept.
Contents
Examples
Softball team
Imagine five people who want to play softball (n = 5 items), with a limitation of only four softball teams (m = 4 holes) to choose from. A further limitation is imposed in the form of each of the five refusing to play on a team with any of the other four players. It is impossible to divide five people among four teams without putting two of the people on the same team, and since they refuse to play on the same team, by asserting the pigeonhole principle it is easily deducible that at most four of the five possible players will be able to play.
Sockpicking
Assuming that in a box there are 10 black socks and 12 blue socks, calculate the maximum number of socks needed to be drawn from the box before a pair of the same color can be made. Using the pigeonhole principle, to have at least one pair of the same color (m = 2 holes, one per colour) using one pigeonhole per color, you need only three socks (n = 3 items). In this example, if the first and second sock drawn are not of the same color, the very next sock drawn would complete at least one samecolor pair. (m = 2)
Handshaking
If there are n number of people who can shake hands with one another (where n > 1), the pigeonhole principle shows that there is always a pair of people who will shake hands with the same number of people. As the 'holes', or m, correspond to number of hands shaken, and each person can shake hands with anybody from 0 to n − 1 other people, this creates n − 1 possible holes. This is because either the '0' or the 'n − 1' hole must be empty (if one person shakes hands with everybody, it's not possible to have another person who shakes hands with nobody; likewise, if one person shakes hands with no one there cannot be a person who shakes hands with everybody). This leaves n people to be placed in at most n − 1 nonempty holes, guaranteeing duplication.
Haircounting
We can demonstrate there must be at least two people in London with the same number of hairs on their heads as follows. A typical human head has around 150,000 hairs; therefore it is reasonable to assume that no one has more than 1,000,000 hairs on their head (m = 1 million holes). Since there are more than 1,000,000 people in London (n is bigger than 1 million items), if we assign a pigeonhole to each number of hairs on a person's head, and assign people to pigeonholes according to the number of hairs on each person's head, there must be at least two people with the same number of hair on their heads (or, n > m). In the case with the fewest overlaps, there will be at least one person assigned to every pigeonhole, at which point the 1,000,001^{st} person is assigned to the same pigeonhole as someone else. Of course, there may be empty pigeonholes in which case this "collision" happens before we get to the 1,000,000^{th} person. The principle just proves the existence of an overlap; it says nothing of the number of overlaps.
Uses and applications
The pigeonhole principle arises in computer science. For example, collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. A hashing algorithm, no matter how clever, cannot avoid these collisions. The principle can also be used to prove that any lossless compression algorithm, provided it makes some inputs smaller (as the name 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, and do so without collisions (because the compression is lossless), which possibility the pigeonhole principle excludes.
A notable problem in mathematical analysis is, for a fixed irrational number a, to show that the set {[na]: n is an integer} of fractional parts is dense in [0, 1]. After a moment's thought, one finds that it is not easy to explicitly find integers n, m such that 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 1/M < e, by the pigeonhole principle there must be n_{1}, n_{2} ∈ {1, 2, ..., M + 1} such that n_{1}a and n_{2}a are in the same integer subdivision of size 1/M (there are only M such subdivisions between consecutive integers). In particular, we can find n_{1}, n_{2} such that n_{1}a is in (p + k/M, p + (k + 1)/M), and n_{2}a is in (q + k/M, q + (k + 1)/M), for some p, q integers and k in {0, 1, ..., M − 1}. We can then easily verify that (n_{2} − n_{1})a is in (q − p − 1/M, q − p + 1/M). This implies that [na] < 1/M < e, where n = n_{2} − n_{1} or n = n_{1} − n_{2}. This shows that 0 is a limit point of {[na]}. We can then use this fact to prove the case for p in (0, 1]: find n such that [na] < 1/M < e; then if p ∈ (0, 1/M], we are done. Otherwise p in (j/M, (j + 1)/M], and by setting k = sup{r ∈ N : r[na] < j/M}, one obtains [(k + 1)na] − p < 1/M < e.
Generalizations of the pigeonhole principle
A generalized version of this principle states that, if n discrete objects are to be allocated to m containers, then at least one container must hold no fewer than objects, where is the ceiling function, denoting the smallest integer larger than or equal to x. Similarly, at least one container must hold no more than objects, where 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
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 at birthday paradox.
A further probabilistic generalisation is that when a realvalued 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.
Infinite sets
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. What makes the situation of finite sets particular is that adding at least one element to a set is sufficient to ensure that the cardinality increases.
See also
 Combinatorial principles
 Dedekindinfinite set
 Hilbert's paradox of the Grand Hotel
 Multinomial theorem
 Ramsey's theorem
 Combinatorial proof
References
 Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0201199122. pp. 244–248.
 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.
External links
 "The strange case of The Pigeonhole 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.
 "The Puzzlers' Pigeonhole"; Alexander Bogomolny on the importance of the principle in the field of puzzle solving and analysis.
Categories: Combinatorics
 Theorems in discrete mathematics
 Mathematical principles
 Ramsey theory
Wikimedia Foundation. 2010.
Look at other dictionaries:
pigeonhole principle — noun A theorem which states that there does not exist an injective function on finite sets whose codomain is smaller than its domain … Wiktionary
Pigeonhole — may refer to:*Pigeonholes, nesting spaces formed in a dovecote (also spelt dovecot or doocot ) *Pigeonhole, one of the boxes in a pigeon coop *Pigeonhole principle, a mathematical principle *Pigeonhole sort, a sorting algorithm *Pigeonhole… … Wikipedia
Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) … Wikipedia
pigeonhole — 1. noun a) One of an array of compartments for sorting post, messages etc. at an office, or college (for example). Fred was disappointed at the lack of post in his pigeonhole. b) A hole, or roosting place for pigeons. 2. verb To categorize;… … Wiktionary
Dirichlet's principle — Not to be confused with Pigeonhole principle. In mathematics, Dirichlet s principle in potential theory states that, if the function u(x) is the solution to Poisson s equation on a domain Ω of with boundary condition then u can be obtained as the … Wikipedia
Combinatorial principles — In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion exclusion principle are often used for enumerative purposes.… … Wikipedia
Ramsey theory — This article provides an introduction. For a more detailed and technical article, see Ramsey s theorem. Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in… … Wikipedia
Lossless data compression — is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be… … Wikipedia
Twelvefold way — In combinatorics, the twelvefold way is a name given to a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and… … Wikipedia
Auxiliary function — In mathematics, auxiliary functions are an important construction in transcendental number theory. They are functions which appear in most proofs in this area of mathematics and that have specific, desirable properties, such as taking the value… … Wikipedia