The Pigeonhole Principle
If 10 pigeons fly into 9 nesting holes, at least one hole is guaranteed to end up with two or more pigeons.
Definition The pigeonhole principle is a fundamental mathematical rule stating that if you have more items than containers to put them in, at least one container must hold more than one item. While simple on the surface, it serves as a remarkably powerful tool for solving complex problems in mathematics and computer science.
10 Pigeons and 9 Nesting Holes
Imagine a sock drawer filled with only black socks and white socks mixed together. How many socks do you need to pull out in the dark to guarantee a matching pair? The answer is 3. Since there are only 2 color "containers" and you drew 3 socks, at least one color is bound to have a pair.
This illustrates the core concept of the pigeonhole principle. If you have 10 pigeons and 9 nesting holes, no matter how evenly you try to distribute them, at least one hole must contain two or more pigeons. Once 9 pigeons each claim their own hole, the 1 remaining pigeon has no choice but to share with someone else.
It might sound too simple to be useful, but this obvious truth is a formidable proof technique in mathematics. It allows us to prove that a certain outcome *must* happen with absolute certainty, without having to check every single scenario individually.
Do Two People in a Big City Have the Exact Same Number of Hairs?
In a crowded metropolis like New York City with over 8 million residents, is there anyone with the exact same number of hairs on their head as you? Even without counting a single strand on anyone's head, the pigeonhole principle lets us say "absolutely yes" in less than a second.
The average human head has around 100,000 to 150,000 hairs. Even being extremely generous, let's set the maximum possible hair count at 500,000. That gives us 500,001 possible "pigeonholes" (from 0 hairs up to 500,000 hairs).
Yet the city's population represents over 8 million "pigeons." Placing 8 million pigeons into 500,000 holes means there is guaranteed to be a group of people with the exact same hair count. The pigeonhole principle effortlessly uncovers hidden certainties within massive data sets.
Taking It a Step Further
The pigeonhole principle was formally introduced in the 19th century by mathematician Peter Gustav Lejeune Dirichlet, which is why it is also known as "Dirichlet's box principle." The concept extends far beyond just finding pairs.
For instance, what happens if you place 21 pigeons into 10 holes? Even if you distribute them as evenly as possible with 2 pigeons in each hole, you still have 1 pigeon left over. In this case, at least one hole must hold 3 or more pigeons. This is known as the "generalized pigeonhole principle."
This principle plays a crucial role in computer science as well. For example, it mathematically proves that an all-purpose compression tool capable of shrinking every possible file without loss is impossible. Whenever items outnumber boxes, this principle defines the fundamental limits of mathematics and algorithms.
๐ค Common misconceptions
The pigeonhole principle tells you exactly which container holds the duplicates.
It cannot specify which container has duplicates; it only guarantees that at least one such container must exist.
๐งบ Where you meet it
When you have more items than containers, at least one container is guaranteed to hold two or more items.