Pigeonhole principle
If n items go into m boxes and n > m, one box holds more.
The pigeonhole principle is a fundamental concept in mathematics, stating that if n items are placed into m containers and n > m, then at least one container must contain more than one item. Though seemingly obvious, it serves as a powerful counting argument used to demonstrate unexpected results, such as proving that in any large population, at least two people must have the same number of hairs on their heads.
- common name
- Dirichlet's box principle or drawer principle
- original term
- Schubfachprinzip (German, meaning 'drawer principle')
- field
- Mathematics
- type
- Counting argument
Reader's Guide
The pigeonhole principle is a foundational tool in combinatorics and discrete mathematics, used to prove existence results without constructing explicit examples. The principle has been generalized to quantified forms, such as: if n = km + 1 objects are distributed among m sets, at least one set contains at least k + 1 objects. Its formal statement—'there does not exist an injective function whose codomain is smaller than its domain'—extends its use to infinite sets and advanced proofs like Siegel's lemma. The principle's name has evolved from Dirichlet's original 'drawer' to 'pigeonhole,' a term that originally referred to small open spaces in furniture for sorting letters, though this meaning is fading in favor of a more pictorial interpretation involving pigeons and holes.
Did You Know?
- The principle can be used to prove that in London, with a population over 1 million, at least two people have the same number of hairs on their heads.
- The German back-translation of 'pigeonhole principle' is 'Taubenschlagprinzip.'
Frequently Asked Questions
What are Pigeonhole principle's powers/role?
Its core move is deceptively simple: whenever you distribute more objects than there are containers, at least one container is forced to hold two or more. Despite that simplicity, it can lock down surprising conclusions, such as guaranteeing that two people in a large city share the exact same number of hairs.
How does Pigeonhole principle's story end?
It never really has an ending; instead it became a permanent fixture of combinatorial proof, showing up wherever an argument needs to establish that some overlap or repetition is mathematically unavoidable.
Why is Pigeonhole principle important?
Because it upgrades a trivially obvious everyday observation into a rigorous tool that can prove results which feel counterintuitive at first glance. It remains one of the most frequently invoked arguments in discrete mathematics and combinatorics.
What is Pigeonhole principle's real name?
In Dirichlet's original German the term was Schubfachprinzip, literally the 'drawer principle,' and it is also widely known in English as Dirichlet's box principle.
More in Combinatorics 1-24
Elsewhere in the Combinatorics universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record