The Pigeonhole Principle: One Idea, Endless Consequences

If 13 people are in a room, at least two of them have birthdays in the same month. There’s no exception to this. With only 12 months and 13 people, at least one month is shared.

If 367 people are in a room, at least two have the same birthday. (366 days in a leap year, so 367 people guarantee a collision.)

If 26 people are in a room, at least two have the same first letter of their name. (Alphabet has 26 letters, but allowing case-folding and unusual cases, the principle still applies.)

These are all instances of the pigeonhole principle: if you put more items than containers into a set of containers, at least one container must hold more than one item. It’s a principle so obvious it sounds trivial. And it is, until you start using it to prove non-obvious theorems — at which point it becomes one of the most surprisingly powerful tools in mathematics.

This article is about what the pigeonhole principle is, how to use it, and the kinds of theorems it can prove that nothing else can.

The basic statement

Pigeonhole principle (basic form): if $n$ items are placed into $k$ containers and $n > k$, then at least one container holds more than one item.

A pictorial way to see it:

Three boxes, four items. By any distribution, at least one box has at least two items. With more items, the lower bound grows: for $n$ items in $k$ boxes, some box has at least $\lceil n/k \rceil$ items. This is the generalized pigeonhole principle.

The proof is one line: if every box had at most $\lceil n/k \rceil - 1$ items, the total would be at most $k(\lceil n/k \rceil - 1) < n$. Contradiction.

That’s the whole principle. It’s obvious. It’s also extraordinarily productive.

Surprising applications

The pigeonhole principle proves theorems where the conclusion isn’t obvious in advance. A few classic examples:

Two people in London with the same number of hairs. The number of hairs on a human head is at most about 200,000. London has 9 million people. By the pigeonhole principle (people = items, possible hair counts 0 through 200,000 = boxes), at least two Londoners have exactly the same number of hairs. Probably hundreds. We can’t identify them, but we know they exist.

Two-thirds of any 17 numbers. Take any 17 distinct integers. At least 3 of them have the same remainder when divided by 5 (because $17 > 3 \cdot 5$). Useful in many number-theory arguments.

Dirichlet’s approximation theorem. For any irrational number $\alpha$ and any positive integer $N$, there exist integers $p, q$ with $1 \leq q \leq N$ such that $\left| \alpha - \frac{p}{q} \right| < \frac{1}{qN}.$ The proof: consider the fractional parts of $0, \alpha, 2\alpha, \ldots, N\alpha$ — these are $N+1$ numbers in $[0, 1)$. Divide $[0, 1)$ into $N$ equal subintervals. Pigeonhole: two of the fractional parts fall in the same subinterval, so their difference is small. From that difference, you extract the rational approximation. This connects to our continued fractions piece.

Erdős–Ko–Rado theorem (special case). Out of any subsets of $\{1, 2, \ldots, n\}$ of size $k$ (with $k \leq n/2$), at most $\binom{n-1}{k-1}$ can be pairwise intersecting. Pigeonhole-type arguments are central to proofs.

Repeating decimals. In the decimal expansion of $1/n$, the cycle of repeating digits has length at most $n - 1$. Why? When you do long division, the remainders at each step are between $0$ and $n-1$. If you get $0$, the expansion terminates. Otherwise, the remainders are among $1, 2, \ldots, n-1$ — only $n-1$ possibilities. After at most $n-1$ steps, by pigeonhole, you must repeat a remainder, which means the decimal cycles.

Chinese restaurant problem. In a restaurant with $n$ customers and $n$ different menu items, can each customer always get a different dish? Pigeonhole gives easy “yes” or “no” answers depending on item availability.

Erdős’s friendship theorem. In any party of 6 or more people, either 3 mutual friends or 3 mutual strangers exist. (This is the special case $R(3,3) = 6$ of Ramsey numbers.) The proof uses pigeonhole repeatedly: pick one person, look at their five other connections (friend or stranger), pigeonhole guarantees three of one type, then case-analysis among those three completes the proof.

These are the gateway examples. There are hundreds more in combinatorics, number theory, geometry, and computer science.

Geometric applications

The pigeonhole principle works geometrically too.

Among any 5 points in a unit square, two are within distance $\sqrt{2}/2$ of each other. Divide the square into 4 quarter-squares (each of side $1/2$). Five points in 4 boxes — pigeonhole says some quarter contains at least 2 points, and any two points in a quarter-square are within $\sqrt{2}/2$.

Among any 10 points in an equilateral triangle of side 3, two are within distance 1 of each other. Divide the triangle into 9 smaller triangles, each with side 1.

These geometric pigeonhole arguments are central to combinatorial geometry. They prove existence of close pairs, intersecting configurations, and structural patterns.

The probabilistic pigeonhole

A subtler version: if you have $n$ items distributed at random among $k$ boxes, the expected fraction of boxes with at least one item is approximately $1 - (1 - 1/k)^n$.

For large $k$ and $n = O(\sqrt{k})$, this gives the birthday paradox: with about $\sqrt{2k \ln 2}$ items, you expect a collision (two items in the same box) with probability around 50%. This is why 23 people are enough to make two birthdays likely. (See our birthday paradox piece for details.)

The same calculation underlies cryptographic security analysis: how large does a hash-output space need to be to avoid collisions? The answer involves the square root of the space size.

Pigeonhole and the infinite

The infinite version: if a function $f: \mathbb{N} \to S$ takes values in a finite set $S$, then $f$ takes some value infinitely often. Pigeonhole, but for an infinite sequence.

This is used throughout analysis and topology. A typical use: if you have a sequence that takes only finitely many values but is infinite, some value repeats infinitely often. This basic fact is the start of many compactness arguments.

The full infinitary pigeonhole: if $f: A \to B$ where $|A| > |B|$ (in the sense of cardinality), some value of $f$ is taken by more than one element of $A$. Used in set theory, logic, and Ramsey theory.

Pigeonhole in computer science

The pigeonhole principle has consequences for computational complexity.

Hash function collisions: any hash function mapping a large set to a smaller set has collisions. This is just pigeonhole — but the principle determines the lower bounds on what’s achievable in cryptographic hash design.

Lossless compression: there is no algorithm that can losslessly compress all inputs. Why? The number of compressed strings of length $n$ is at most $2^n + 2^{n-1} + \cdots + 2 + 1 = 2^{n+1} - 1$ — but the number of possible inputs of length $n$ is $2^n$. So by pigeonhole, no compression scheme produces strictly shorter output for every input. Some inputs must compress to longer strings.

Cache and memory limits: any cache of finite size must fail to hold some workloads — at some point, you have more data than slots, and pigeonhole forces evictions. Cache-replacement algorithms minimize evictions but can’t eliminate them.

Error correction: codes have a fundamental trade-off: you can detect/correct only a finite number of errors per code word, because the code word space is finite. The Singleton bound and related limits are pigeonhole arguments.

Why is it surprising

The pigeonhole principle is surprising because it produces existence proofs without construction. You can prove “two Londoners have the same number of hairs” without identifying them. You prove “the decimal of 1/7 repeats” without computing the decimal expansion in detail. You prove “some element of this sequence repeats” without knowing which.

This kind of non-constructive existence is at odds with how engineers think — they want to find things, not just know they exist. But for mathematicians, it’s a feature: existence is sometimes all you need.

Many of the most elegant proofs in mathematics are pigeonhole proofs in disguise. They establish results that no concrete computation could verify (because the search space is too large) but that pigeonhole forces with certainty.

What the pigeonhole principle teaches

The deepest lesson is that trivially-true statements can have non-trivial consequences. The pigeonhole principle is so simple it’s barely worth stating. But applied carefully — finding the right boxes and the right items — it produces results that resist all other approaches.

This is a recurring pattern in mathematics. Big theorems often have small kernels. The intermediate value theorem (continuous functions take all values between their endpoints) is “obvious” but proves the existence of solutions to enormous numbers of equations. The pigeonhole principle is its combinatorial cousin: an obvious counting fact that, applied with cleverness, proves much more than counting.

For students learning mathematics, the pigeonhole principle is one of the cleanest demonstrations of “non-obvious from obvious.” A trivial statement, when applied to the right setup, generates non-trivial conclusions. That’s what mathematical proof often looks like at its best.

For working mathematicians, it’s a constant tool. Whenever you need to prove that two things must coincide, must conflict, must collide, must overlap — and you can identify the right “boxes” — pigeonhole is your first move. It’s the simplest non-trivial proof technique in combinatorics.

The principle that 13 socks in 12 drawers force a doubling is the same principle that, applied to integers and irrational numbers, gives Dirichlet his approximation theorem. Same trick, different setting. That portability across domains is what makes simple ideas in mathematics endlessly useful.

Frequently asked

Why is it called the pigeonhole principle?

Because the original metaphor is pigeons and pigeonholes (small compartments). If you have more pigeons than holes, at least one hole has at least two pigeons. The German term Schubfachprinzip ('drawer-compartment principle') is older and was used by Dirichlet in 1834. The pigeon metaphor became popular in English-language texts later.

Is it really a fundamental principle?

Yes. It's one of the basic tools of combinatorial mathematics, alongside the principle of induction and counting in two ways. Many proofs that seem to require sophisticated machinery turn out to use the pigeonhole principle in disguise. It's particularly useful when you need to prove that something must exist (there must be two people with the same haircut, for example) without finding it explicitly.

Can it be generalized?

Yes — the generalized pigeonhole principle says: if you put n items into k boxes, some box has at least ⌈n/k⌉ items. This is more useful when the simple version doesn't immediately apply. Probabilistic and infinitary versions exist too, including the probabilistic pigeonhole principle (used in random algorithms) and the infinite version (used in measure theory and topology).

Continue reading

Blog

The Birthday Paradox: Why 23 People Is All You Need

In a room of 23 people, the chance two share a birthday is greater than 50%. A closer look at one of the most counterintuitive results in elementary probability.

Read →Blog

Pascal's Triangle: Patterns Hidden in a Simple Construction

Start with 1 at the top. Each row, add adjacent entries to get the row below. The result contains binomial coefficients, Fibonacci numbers, the Sierpinski triangle, and many surprising patterns.

Read →Blog

The Coupon Collector's Problem: Why the Last Sticker Is Always the Hardest

Buy random stickers until the album is full, or roll dice until every face shows. The expected number of attempts is roughly n·ln(n) — and most of that wait is for the very last item.

Read →