Pigeonhole Principle

In one sentence: If you put more things than boxes into the boxes, at least one box must hold two or more things.

$\max_{j}\, b_j \ge \left\lceil \frac{n}{m} \right\rceil$

Read it out loud: “The largest number of items in any box is at least the ceiling of n over m. Here n is the number of items, m is the number of boxes, and the ceiling of a number means rounding it up to the next whole number. The letter j names a box, and b sub j is the number of items in box j.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Rounding up, the ceiling $\lceil x \rceil$: The ceiling of $x$ , written $\lceil x \rceil$ , is $x$ rounded up to the next whole number. For example $\lceil 2.08 \rceil = 3$ , because 2.08 rounds up to 3. A whole number is already its own ceiling, so $\lceil 4 \rceil = 4$ . Rounding down instead is called the floor, and the principle needs the ceiling, not the floor.
Dividing to find an average: A fraction bar means divide. The fraction $\frac{25}{12}$ means 25 items shared among 12 boxes, which is about 2.08 items per box. This is an average: the total divided by the number of groups. The average may not be a whole number, even when every item is a whole item.
Subscripts, like $b_j$: A small letter placed below another letter is a subscript. $b_j$ is read ‘b sub j’, and it means the number of items in box number $j$ . So $b_1$ is the count for box 1, and $b_2$ is the count for box 2. The letter $j$ is a label, not a number of items.
Maximum, $\max$ , and at least, $\ge$: $\max_{j} b_j$ means the largest value of $b_j$ over all the boxes. If three boxes hold 2, 5 and 1 items, the maximum is 5. The sign $\ge$ means ‘greater than or equal to’, so ‘at least 3’ is written $\ge 3$ , and it is true for 3 and for 4.
Proof by contradiction: A proof by contradiction assumes the opposite of what you want to show, and then finds that the assumption leads to something impossible. Here, if every box held at most 2 items, the total would be at most 24. But there are 25 items, so the assumption must be false.
Hash table and buckets (background): A hash table stores items by computing a bucket number for each key, using a rule called a hash function. The buckets are the numbered slots. Many buckets can hold items, and some buckets can end up with more than one item. That situation is called a collision.

What each symbol means

Symbol	Meaning
$\max_{j}\, b_j$	The number of items in the fullest box. The letter $j$ names a box, and $b_j$ is how many items box $j$ holds. The maximum is taken over all boxes, and the result is a count of items, with no unit.
$n$	The number of items being placed into the boxes, a whole number such as 25 members. Each item goes into exactly one box. The count has no unit, because it counts things like people, letters or files.
$m$	The number of boxes, a whole number of at least 1 such as 12 months. Some boxes may stay empty. The count has no unit, and it is set before the items are placed.
$\left\lceil x \right\rceil$	The ceiling of $x$ : $x$ rounded up to the next whole number. For example $\lceil 2.08 \rceil = 3$ and $\lceil 4 \rceil = 4$ . The result is a whole number of items, so it has no unit.

The formula piece by piece

$n$: The number of items to place. In the club example, $n = 25$ members. Every item goes into one box, and that is the only rule the principle uses about how the items are placed.
$m$: The number of boxes. In the club example, $m = 12$ months. The principle does not require every box to hold something, so some boxes can stay empty.
$\frac{n}{m}$: The average number of items per box, found by dividing the items by the boxes. For $n = 25$ and $m = 12$ it is $\frac{25}{12}$ , which is about 2.08. This average is not a whole number, so it cannot be the count of the fullest box on its own.
$\left\lceil \frac{n}{m} \right\rceil$: The average rounded up to the next whole number. Rounding up, not down, is what the principle guarantees. Since $\lceil 2.08 \rceil = 3$ , the fullest box must hold at least 3 items in the club example.
$\max_{j}\, b_j$: The largest count among all the boxes, the count of the fullest box. The principle does not say which box it is, only how big its count must be.
$\max_{j}\, b_j \ge \left\lceil \frac{n}{m} \right\rceil$: In one plain sentence: when $n$ items go into $m$ boxes, the fullest box holds at least $n$ divided by $m$ , rounded up to the next whole number.

What the formula is doing, and why

What goes in and what comes out. You put $n$ items into $m$ boxes. The principle says that the fullest box must hold a certain minimum number of items. That minimum is $\lceil \frac{n}{m} \rceil$ , which is the average $\frac{n}{m}$ rounded up. The principle makes this promise without needing to know where each item went.

Why must it be true? Suppose every box held at most $\lceil \frac{n}{m} \rceil - 1$ items, which is one less than the minimum. Then all the boxes together hold at most $m$ times that number. But $\lceil \frac{n}{m} \rceil - 1$ is less than $\frac{n}{m}$ , so the total is less than $n$ . That leaves some items with nowhere to go, which is impossible. So some box must hold at least $\lceil \frac{n}{m} \rceil$ items.

Why is only one box promised? The rule says nothing about which box is crowded, or how the items got there. It only promises that one box is full enough. That is what makes it useful: you can prove that a repeat or a collision must happen without finding the example itself.

The simplest case and the limits. The simplest case is $n = m + 1$ . Then $\frac{m+1}{m}$ is more than 1 and at most 2, so its ceiling is 2, and some box holds two items. The guaranteed crowding goes up only when $n$ passes a multiple of $m$ . If $n$ is at most $m$ , the rule guarantees only that one box holds at least 1 item, which says nothing new.

An everyday picture

Think of a coat rack with 4 hooks and 5 coats. Hang every coat on a hook, and at least one hook must carry two coats, because there is no way to avoid it. The average is $\frac{5}{4} = 1.25$ coats per hook, and rounded up that is 2. You do not have to see which hook is crowded to know that a crowded hook exists.

Worked example: Birthday months in a club

A club has 25 members, and each one has a birthday in one of 12 months. The months are the boxes and the members are the items. The question is: what is the least number of members that the fullest month must hold? The answer is a guarantee, and it does not depend on knowing any real birthdays.

Divide the members by the months. The average per month is $\frac{25}{12}$ . Dividing 25 by 12 gives 2 with 1 left over, which is about 2.08 members per month on average.
Round up to the next whole number. The principle uses the ceiling, which rounds up. So $\lceil 2.08 \rceil = 3$ . Rounding up is what makes the promise hold for every possible arrangement of birthdays, not only for the average one.
Test the opposite idea. Suppose every month held at most 2 members. Then the 12 months together would hold at most $12 \times 2 = 24$ members in total. This is the opposite of what we want to show, so we test it to see if it can be true.
Compare with the real total. But there are 25 members, and $25 - 24 = 1$ member too many. The assumption that every month holds at most 2 is therefore impossible, so at least one month must hold 3 members.
Notice what the argument did not need. We never looked at any birthday, and we never named a month. The argument works for any club of 25 members with 12 months, so the guarantee holds for every such club.
Notice why rounding down would fail. Rounding 2.08 down gives 2. But a club where every month held at most 2 members would hold only 24 members, one short of 25. So 3 is the value the principle can promise, and 2 is too small.

Answer: The fullest month holds at least 3 members. The principle proves this for any club of 25 people, without knowing a single birthday.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Expecting the principle to name the crowded month. It proves that a month with at least 3 members exists, but it does not say which month it is.
Rounding down. The floor of $\frac{25}{12}$ , which is rounding down, is 2. That is too small. The ceiling, 3, is the value the principle guarantees.
Thinking every box must hold something. Some boxes may stay empty. The rule only sets a lower bound on the count of the fullest box, which is the smallest value that count can have.
Swapping the counts. The items go into the boxes, so $n$ is the number of items and $m$ is the number of boxes.

Where you will meet it

Hash tables: once there are more keys than buckets, at least two keys must share a bucket, which is a collision.
Lossless compression, which shrinks files without losing any data. No method can shrink every file of a fixed length, because the list of shorter sequences of 0s and 1s, called bits, has fewer entries than the list of files of that length.
Number theory proofs, such as showing that among any 5 whole numbers, two have the same remainder when divided by 4. The remainder is the part left over after dividing.
Scheduling and seating puzzles, where a limited number of slots forces at least one slot to be shared.

Questions people ask

Does the principle say which box is crowded?

No. It only proves that some box holds at least $\lceil \frac{n}{m} \rceil$ items. It does not name the box, and it does not say how many boxes are crowded.

Where does the name come from?

The picture is pigeons flying into pigeonholes, which are small compartments in a desk or cabinet. With more pigeons than holes, one hole has to hold two pigeons. Some books call the same rule the drawer principle, for the same reason.

How does it apply to hash collisions?

A hash table with $m$ buckets that stores $n > m$ keys must have at least one bucket with two or more keys. The collision cannot be avoided once the keys outnumber the buckets.

Hash Table Load Factor: The load factor is how full a hash table is on average: the number of keys divided by the number of buckets.
Birthday Problem: The birthday problem asks how likely it is that some pair of items in a random group match, and the answer rises faster than most people expect.
Combinations: A combination counts the different groups you can pick from a set of items when the order of the picks does not matter.