Definition
The pigeonhole principle is a rule in mathematics: if you have more items to put away than boxes to hold them, at least one box must hold two or more items. It looks obvious, but it is a powerful tool for solving tricky problems in math and computer science.
10 Pigeons and 9 Nests
Imagine a sock drawer with only black socks and white socks mixed together. With the lights off, how many socks must you pull out to be sure you have a matching pair? The answer is 3. There are only 2 "boxes," the two colors, and you took 3 socks, so at least one color has to appear twice.
This is the pigeonhole principle in its basic form. With 10 pigeons and 9 nests, no matter how evenly you try to spread them out, some nest must hold two or more pigeons. Once 9 pigeons have taken one nest each, the last pigeon has to join a nest that is already taken.
It may seem too obvious to matter. But in math, that obviousness makes it a very strong tool for proofs. It can show that something must happen without checking every possible case one by one.
Do Two People in Seoul Have the Same Number of Hairs?
Seoul, the capital of South Korea, has more than 9 million people. Are there two people there with exactly the same number of hairs on their heads? You don't have to count every citizen's hairs. With the pigeonhole principle, you can say "yes, there must be" in one second.
A person usually has at most about 150,000 hairs. Let's be very generous and say 500,000 at most. Then the "nests" you can make from hair counts run from 0 to 500,000, which is 500,001 nests in total.
But the "pigeons," the citizens of Seoul, number more than 9 million. That's like putting 9 million pigeons into 500,000 nests. So in Seoul there must be a group of people with exactly the same number of hairs. The pigeonhole principle has uncovered a hidden rule of a huge city in one step.
A Little More Precisely
The 19th-century mathematician Dirichlet laid out this principle in a systematic way, so it is also called Dirichlet's drawer principle. It doesn't stop at "two or more overlap." It extends much further.
Say you put 21 pigeons into 10 nests. Even if you spread them as evenly as possible, 2 per nest, 1 pigeon is left over. So at least one nest must hold 3 or more pigeons. This is called the generalized pigeonhole principle.
The principle also plays a key role in computer science. It is used to prove that, however clever compression gets, there can never be a magic program that makes every file smaller. Situations with more pigeons than nests reveal important limits throughout math and algorithms.
Common misconceptions
The pigeonhole principle tells you exactly which nest ends up with extra pigeons.
It can't tell you which nest is crowded. It only guarantees that at least one crowded nest must exist.
Where you meet it
Pull 3 socks from a drawer of mixed black and white socks, and you always get a matching pair.
In a group of 13 people, at least two were born in the same month.
Among the people of Seoul, there must be some whose hair counts match exactly.
In one sentence
If there are more items than boxes to hold them, at least one box must hold two or more items.