Concept
If n+1 pigeons go into n holes, at least one hole has ≥2. A trivial-looking principle that powers Ramsey theory, finite combinatorics, and Dirichlet approximation.
Understand it in one breath
Among 10 million people, two must share an exactly equal hair count — humans have fewer than 1 million hairs. A one-line principle that is a perennial Olympiad weapon and the seed of Ramsey theory: any sufficiently large structure must contain any pattern you specify.
At a glance
Scenario | Pigeonholes | Pigeons | Conclusion |
|---|---|---|---|
A gathering of 367 people in one year | 366 days | 367 people | At least two share a birthday |
10 million residents of Seoul | Fewer than 1 million possible hair counts | 10 million people | At least two people have exactly the same number of hairs |
Five cards drawn from an eight-card hand | 4 suits | 5 cards | At least two cards share a suit |
n+1 pigeons | n pigeonholes | n+1 | Some pigeonhole contains ≥ 2 pigeons |
Compression algorithm | Fewer short outputs than possible inputs | Set of inputs | Universal lossless compression is impossible |
"The least visible principles can become the most powerful tools." Dirichlet first used it to approximate irrational numbers; it is a starting point for Ramsey theory.
Key formula
Modern applications
Guarantees of hash collisions, proofs of compression limits, and lower bounds for algorithms.
Beyond MathVoyage
Loading…