The pigeonhole principle is a simple but powerful counting observation used to prove that some configuration must exist when a limited number of containers (or categories) receives a larger number of objects. Informally: if n+1 or more objects are placed into n boxes, at least one box contains more than one object. Although the wording evokes birds and holes, the idea applies to any discrete allocation problem.
Statement and common variants
The basic or "simple" form says: if k objects are placed into n containers and k>n, then some container holds at least two objects. The generalized or quantitative form (sometimes called the strong pigeonhole principle) states that if k objects go into n boxes, then some box contains at least ceil(k/n) objects. There is also an infinite version used in set theory and analysis: if an infinite set is partitioned into finitely many subsets, at least one subset is infinite.
The principle is usually proved by contradiction: assume every box has at most m objects, count the maximum possible number of objects and show this contradicts the assumed total. This makes the pigeonhole principle an existence tool rather than a constructive one: it guarantees that a particular type of object or collision exists but does not always provide a method for finding it.
Illustrative examples
- Socks: with five black drawers each holding at most one sock of a certain type, placing six socks forces a repeat in some drawer.
- Birthdays: in a group of 366 people, two must share a birthday (ignoring leap-year details) because there are only 365 possible birthdays.
- Hashing and collisions: hashing n+1 items into n buckets must produce at least one collision; this is a practical concern in computer science.
- Graph theory: the principle underlies basic arguments about degrees and matchings in graphs and appears often in graph theory proofs.
For a formal statement and many textbook examples see a standard reference on the topic: pigeonhole principle. The idea is also a staple of elementary number theory and combinatorics in mathematics, where it provides short, elegant existence proofs.
History and usage: the principle is commonly attributed to the 19th‑century mathematician Peter Gustav Lejeune Dirichlet and is often called Dirichlet's box (or drawer) principle. Over time it has become a fundamental technique for proving impossibility or inevitability statements across many areas of mathematics and theoretical computer science.
Notable facts and cautions: the pigeonhole principle yields existential conclusions and sometimes only weak quantitative bounds; selecting tighter partitions or refining categories often strengthens its conclusions. It also appears in surprising settings — from real analysis to Ramsey theory — where simple counting yields nontrivial consequences.