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. For instance, given that the population of London exceeds the maximum possible number of hairs on a human head by more than one, the principle proves that at least two Londoners must have the same number of hairs. Another classic example involves socks: if a drawer contains black and blue socks, pulling just three socks guarantees a matching pair, as there are only two color categories. The principle also applies to handshakes among a group of people, showing that at least two individuals will have shaken the same number of hands, which is equivalent to stating that in any graph with more than one vertex, two vertices share the same degree.
The earliest known written reference appears in a 1622 work by French Jesuit Jean Leurechon, which noted that two men must have the same number of hairs. However, the principle is most commonly named after Peter Gustav Lejeune Dirichlet, who treated it in 1834 under the German term "Schubfachprinzip" (drawer or shelf principle). Dirichlet originally wrote about distributing pearls among drawers, and the term later morphed into "pigeonhole" in English, referencing small open compartments in furniture used for sorting letters or keys. This translation has become standard, though the literal imagery of pigeons and holes has gained popularity, even influencing a modern German back-translation as "Taubenschlagprinzip."
The principle generalizes in quantified form: for natural numbers k and m, if n objects are distributed among m sets, at least one set contains at least ⌈n/m⌉ objects. More formally, it states that no injective function exists from a larger domain to a smaller codomain. This abstract version extends to infinite sets and underpins advanced proofs such as Siegel's lemma.
- common name
- Dirichlet's box principle or drawer principle
- original term
- Schubfachprinzip (German, meaning 'drawer principle')
- field
- Mathematics
- type
- Counting argument
Lore & Background
The pigeonhole principle is a fundamental counting argument in mathematics. It states that if a number of items are placed into a smaller number of containers, then at least one container must hold more than one item. For instance, if three gloves are sorted into two categories—right-handed and left-handed—then at least two gloves must share the same handedness. A classic illustration involves pigeons and holes: with ten pigeons placed into nine holes, the principle guarantees that at least one hole contains more than one pigeon. The principle can be generalized: for natural numbers \( k \) and \( m \), if \( kn + 1 \) objects are distributed among \( n \) sets, at least one set will contain at least \( k + 1 \) objects. More formally, for arbitrary \( n \) and \( m \), at least one set contains at least \( \lceil m/n \rceil \) objects, where \( \lceil \cdot \rceil \) denotes the ceiling function. The principle also applies to infinite sets that cannot be put into one-to-one correspondence, expressed as the statement that no injective function exists whose codomain is smaller than its domain. This abstract formulation underpins advanced proofs such as Siegel's lemma. The principle first appeared in writing in 1622, in a work by the French Jesuit Jean Leurechon, which noted that two men must have the same number of hairs. It is commonly called Dirichlet's box principle or drawer principle, after Peter Gustav Lejeune Dirichlet’s 1834 treatment, where he wrote of distributing pearls among drawers. The term "pigeonhole" originally referred to small open compartments in furniture for storing letters or papers, a metaphor rooted in structures housing pigeons. This translation of Dirichlet's "drawer" is now widespread, though the literal image of pigeons and holes has influenced back-translations in languages such as German. The principle is used in diverse examples, including proving that in any group of people who shake hands, at least two shake the same number of hands, and that in a city like London, with a population exceeding the maximum possible number of hairs on a human head, at least two people must have identical hair counts.
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
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