The Pigeonhole Principle

The pigeonhole principle is simply this: if there are more things than places to put them, some place has to get doubled up. The name comes from pigeons and their nesting holes (a "pigeonhole" is also an old word for a small mail slot in a desk): more pigeons than holes, and two must share. It's good for proving something has to happen, like a hash collision, without finding it. The formula just makes that precise: $N$ (how many objects), $k$ (how many boxes), $N/k$ (the average per box) and $\lceil\;\rceil$ (round up to a whole number). Some box holds at least the average, rounded up. Everything so far in this unit has counted things exactly; this last tool is different, because it doesn't tell you how many, it tells you something must happen.

Put 4 letters into 3 mailboxes and some mailbox gets two. Why? If every mailbox had at most one, there'd be at most 3 letters. The general version works the same way. The average box holds $N/k$ objects, and not every box can be below average. If every box held fewer than $\lceil N/k \rceil$ objects, then each would hold at most $\lceil N/k \rceil - 1 < N/k$, and the boxes together would hold fewer than $N$. So some box must hold at least $\lceil N/k \rceil$.

Classic uses:

• Among 13 people, two share a birth month.
• London has about 9 million people, and nobody has more than about 1 million hairs, so at least two Londoners have exactly the same number of hairs.
• Pull socks from a drawer of black and white socks in the dark: 3 socks guarantee a matching pair.
• Any 5 points in a unit square include two within $\frac{\sqrt 2}{2}$ of each other: cut the square into 4 smaller squares, and two points share one.

Notice that the principle proves something exists without saying which box overflows. You never find the two Londoners; you just know they're out there. The hard part, and the creative part, is choosing the right "boxes." In the square example nobody hands you the 4 smaller squares; you have to think of cutting it up.

A common mistake. It's tempting to read the principle as "some box gets $N/k$" and round down, or to think it says the objects spread out evenly. It says neither. It only promises one box with at least $\lceil N/k \rceil$, rounded up, and the other boxes could be empty.

It proves that no compression scheme shrinks every file and that every hash table must handle collisions.