
related topics 
{math, number, function} 
{@card@, make, design} 
{theory, work, human} 
{specie, animal, plant} 
{village, small, smallsup} 

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.
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 or Dirichlet's drawer principle. In Russian and some other languages, it is contracted to simply "Dirichlet principle"—a name that could also refer to the minimum principle for harmonic functions. The original name is still in use in 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.
Full article ▸


related documents 
Base (topology) 
Generalized mean 
Definable real number 
ML (programming language) 
Trie 
Boolean ring 
MerkleHellman 
Outer product 
Chain rule 
Preorder 
Presburger arithmetic 
Riemann mapping theorem 
Idempotence 
Ring (mathematics) 
Monster group 
2 (number) 
Assignment problem 
Prim's algorithm 
Paracompact space 
Multiplicative function 
Fixed point combinator 
Oracle machine 
Richard's paradox 
Extended real number line 
Meromorphic function 
Commutator subgroup 
Splitting lemma 
Queue (data structure) 
Poisson process 
Existential quantification 
