If you place more than n items into n containers, at least one container must hold more than one item. This statement is so obviously true it barely seems worth stating — yet it is one of the most surprisingly powerful and widely applicable proof techniques throughout mathematics, capable of establishing deep, non-obvious results in number theory, combinatorics, and computer science.
If you have 13 pigeons and only 12 pigeonholes to put them in, at least one pigeonhole must contain 2 or more pigeons — there's simply no way around it, no matter how cleverly you try to distribute them. This is the entire Pigeonhole Principle: it sounds almost too obvious to bother proving, yet it turns out to be an extraordinarily useful and versatile tool for proving genuinely surprising things.
The power of the Pigeonhole Principle lies in cleverly choosing what counts as your "pigeons" and what counts as your "pigeonholes" for a given problem. Once you find the right way to set up this correspondence, a seemingly hard question about whether something must happen can often be answered immediately, with no further calculation required — you've simply shown that the "pigeons" outnumber the "pigeonholes."
There are at least two people in New York City with exactly the same number of hairs on their head. The reasoning: no human head has more than about 200,000 hairs, but New York City's population is many millions — so there simply aren't enough distinct possible "hair-count pigeonholes" to give every single person their own unique number, guaranteeing some pair of people must coincidentally match.
If n items are placed into k containers, at least one container must hold at least ⌈n/k⌉ items (where ⌈⌉ denotes rounding up to the nearest whole number). The basic version above is simply the special case k=n−1 (or more precisely, whenever n>k). This generalisation lets the principle handle situations demanding a stronger guarantee than "at least 2 in one container."
A classic and genuinely elegant application: in any sequence of n²+1 distinct real numbers, there must exist either an increasing subsequence of length n+1, or a decreasing subsequence of length n+1 (the Erdős–Szekeres theorem, 1935). The proof cleverly assigns each number in the sequence to a "pigeonhole" pair recording the length of the longest increasing and longest decreasing subsequence ending at that specific number, and shows that if no such long subsequence of either kind existed, there wouldn't be enough distinct possible pigeonhole pairs to accommodate all n²+1 numbers without at least two numbers colliding into an impossible, contradictory pigeonhole pair.
Every rational number's decimal expansion either terminates or eventually repeats (see the Rational Number entry) — and the Pigeonhole Principle explains precisely why. When performing long division to compute p/q, at each step, the possible remainders are limited to the q values 0, 1, ..., q−1. If the division process continues indefinitely without terminating, then among any q+1 consecutive division steps, some remainder value must necessarily repeat (by the Pigeonhole Principle) — and once a remainder repeats, the entire subsequent sequence of digits is forced to repeat identically as well.
Dirichlet's approximation theorem (1842) uses the Pigeonhole Principle to prove that for any irrational number α and any positive integer N, there exists a fraction p/q (with q≤N) such that |α−p/q| < 1/(qN) — establishing that irrational numbers can always be approximated remarkably well by comparatively simple fractions, a foundational result in the theory of continued fractions and Diophantine approximation.
As introduced in the Combinatorics entry, Ramsey theory studies the inevitability of specific patterns emerging within sufficiently large structures — and the Pigeonhole Principle can be viewed as the simplest, most elementary possible case of a genuinely Ramsey-type result: it guarantees that some specific pattern (a repeated assignment) must inevitably occur once a structure grows sufficiently large, exactly mirroring the deeper logical structure underlying the far more elaborate results of full Ramsey theory.
The Pigeonhole Principle underlies the fundamental theoretical limitation of hash functions in computer science: since a hash function maps a very large (in principle infinite) space of possible inputs down to a fixed, finite space of output "hash values," collisions (two distinct inputs mapping to the identical hash output) are mathematically unavoidable once enough distinct inputs are considered. The birthday attack in cryptography exploits precisely this unavoidable fact combined with the (initially quite counterintuitive) mathematics of the birthday problem to find hash collisions considerably faster than naive brute-force searching would suggest is possible, directly informing minimum required cryptographic hash output lengths in real-world security-critical system design.
The principle extends meaningfully to infinite sets: if infinitely many items are placed into finitely many containers, at least one container must contain infinitely many items. This infinite version, while intuitively almost as obvious as the finite case, still requires care in its proof and has genuinely important applications throughout set theory and mathematical logic — including, notably, within certain proofs related to Ramsey's original theorem (1930) in its full, general infinite form.
The principle itself is, of course, mathematically ancient and self-evident, but the specific whimsical name "pigeonhole principle" is generally attributed to Peter Gustav Lejeune Dirichlet, who applied the idea rigorously in number theory in the 1830s–40s (it is consequently sometimes still called Dirichlet's box principle, or Dirichlet's drawer principle, reflecting the German original term Schubfachprinzip, literally "drawer principle"). Despite Dirichlet's clear priority in rigorous mathematical application, the underlying elementary logical observation itself is so immediately self-evident that it likely occurred informally to countless individuals across history, entirely independently of any formal or named mathematical tradition.
The Pigeonhole Principle offers a valuable and instructive broader lesson about the nature of mathematics itself: a foundational logical statement's ultimate power and usefulness need not correlate at all closely with how sophisticated, difficult, or surprising that statement initially sounds when first encountered. Some of the most broadly applicable and productive tools throughout all of mathematics are, at their logical core, almost embarrassingly self-evident — the genuine skill and creativity lies entirely in learning to recognise precisely when and how to cleverly apply them to a given, often superficially unrelated, problem.