Pigeonhole principle

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.