The Pigeonhole Principle

In this lesson you’ll learn the pigeonhole principle in its simple and generalized forms, how to identify the “pigeons” and “holes” in a problem, and how a nearly obvious statement proves genuinely surprising things.

If $n+1$ objects are placed into $n$ boxes, then at least one box contains at least 2 objects.

That’s it. If you have 13 people and 12 months, at least two share a birth month. Nothing deep is happening.

The name comes from the picture of pigeons flying into pigeonholes: more birds than holes means someone is sharing.

Formally, if $f: A \rightarrow B$ is a function and $|A| > |B|$, then $f$ cannot be injective. Some two inputs map to the same output.

The principle proves that something must exist without telling you where it is or how to find it. That’s an unusual and powerful kind of statement.

It also lets you prove things with no computation at all. You count two quantities, notice one is bigger, and you’re done.

If $n$ objects are placed into $k$ boxes, then at least one box contains at least $\left\lceil \dfrac{n}{k} \right\rceil$ objects.

The $\lceil \cdot \rceil$ is the ceiling function, meaning round up to the nearest integer.

$$\left\lceil \frac{100}{12} \right\rceil = \lceil 8.33 \rceil = 9$$

So among 100 people, at least 9 share a birth month.

The reverse direction is often what you want: to guarantee at least $m$ objects in some box with $k$ boxes, you need

$$n > k(m-1) \quad \text{objects, so} \quad n = k(m-1) + 1$$

The logic: $k(m-1)$ objects could spread out with exactly $m-1$ in each box, dodging the requirement. One more forces a box to reach $m$. This is the worst case reasoning, and it’s the heart of every “how many must I take?” problem.

Three steps, and the whole difficulty is in step 1:

1. Identify the pigeons (the objects being placed).
2. Identify the holes (the categories).
3. Compare the counts and apply the formula.

Choosing the right holes is the creative part. In easy problems the categories are obvious (months, colors, days). In harder ones you have to invent them: remainders after division, ranges of values, positions on a board.

A quick check on your setup: if it isn’t clear that every pigeon lands in exactly one hole, your holes are wrong.

Example 1: The basic version.

Show that in any group of 13 people, at least two were born in the same month.

Solution. Pigeons: 13 people. Holes: 12 months. Since $13 > 12$, some month holds at least 2 people. ∎

Example 2: Socks in the dark.

A drawer holds 10 black socks, 12 white socks, and 8 gray socks, all mixed up. How many socks must you pull out, without looking, to guarantee a matching pair?

Solution. Holes: 3 colors. Worst case, the first 3 socks are all different colors. The 4th must match one of them.

$$n = k(m-1) + 1 = 3(2-1) + 1 = 4$$

4 socks. The counts of each color never mattered, only the number of colors, which is the kind of detail these problems like to bury.

Example 3: Guaranteeing a larger group.

How many people are needed to guarantee that at least 4 share a birth month?

Solution. $k = 12$ holes, want $m = 4$ in some hole:

$$n = 12(4-1) + 1 = 37$$

37 people. With 36 you could have exactly 3 per month and never hit 4.

Example 4: Inventing the holes with remainders.

Show that among any 5 integers, some two have the same remainder when divided by 4.

Solution. Holes: the possible remainders mod 4, which are $\{0, 1, 2, 3\}$. That’s 4 holes. Pigeons: 5 integers. Since $5 > 4$, two share a remainder. ∎

A consequence: those two integers have a difference divisible by 4, since equal remainders subtract away. Remainder classes are the single most useful non-obvious choice of holes.

Example 5: Sums from a set.

Choose any 5 numbers from $\{1, 2, 3, 4, 5, 6, 7, 8\}$. Show that some two of them sum to 9.

Solution. Group the numbers into pairs that sum to 9:

$$\{1,8\}, \{2,7\}, \{3,6\}, \{4,5\}$$

That’s 4 holes covering all 8 numbers. Pigeons: your 5 chosen numbers. Since $5 > 4$, two of your numbers fall in the same pair, and that pair sums to 9. ∎

Notice the holes were constructed to make the conclusion automatic. That’s the technique in these harder problems: build the categories so that sharing a category is the property you want.

Example 6: Handshakes.

In a room of $n$ people ($n \geq 2$) where some pairs shake hands, show that at least two people shook the same number of hands.

Solution. Each person shakes between 0 and $n-1$ hands, giving $n$ possible values, so naively pigeons and holes are equal and we get nothing.

But the values 0 and $n-1$ cannot both occur. If someone shook everyone’s hand ($n-1$), then nobody shook zero hands. So at most $n-1$ of the $n$ values are actually available.

Now $n$ people into at most $n-1$ holes forces a repeat. ∎

The extra step of eliminating one hole is what makes this problem interesting, and it’s a common pattern: get the counts to $n$ versus $n$, then argue one hole is unreachable.

Example 7: The hair count classic.

Show that in a city of 1,000,000 people, at least two have exactly the same number of hairs on their head.

Solution. A human head holds at most about 150,000 hairs. Holes: the possible hair counts, $0$ through $150{,}000$, so $150{,}001$ holes. Pigeons: 1,000,000 people. Since $1{,}000{,}000 > 150{,}001$, at least two match. ∎

In fact by the generalized form at least $\lceil 1{,}000{,}000 / 150{,}001 \rceil = 7$ people share a hair count.

Hash collisions are the pigeonhole principle in production. A hash function maps arbitrarily many possible inputs into a fixed number of output slots, so collisions are not a bug to be engineered away, they are mathematically unavoidable. Every hash table implementation must handle them, and every claim of a “collision-free” hash for unbounded input is false by this principle.

Lossless compression has the same limit. You cannot write a program that shrinks every possible input file, because mapping all $2^n$ inputs into fewer than $2^n$ outputs would force two inputs to the same compressed form, making decompression ambiguous. Real compressors shrink typical files and grow random ones.

Memory allocation and caching hit it too. With more memory addresses than cache lines, some addresses must map to the same line, which is exactly why cache eviction policies exist.

Network port exhaustion, IP address collisions, and database index bucketing all come from the same place. And in scheduling, the principle tells you when a conflict is guaranteed: 25 meetings in a day with only 8 available rooms and 8 time slots means overlap is unavoidable, no matter how clever the scheduler is.

Outside of computing, it’s an argument you can make in a sentence. Two people in any group of 400 share a birthday, guaranteed, because there are only 366 possible dates.