Symptom

You are asked to build a cache key. You have a 64-bit hash, and someone on the team says: “collisions are basically impossible, there are eighteen quintillion values.”

Or: your service assigns short IDs to uploads, six characters of base-36, and you are wondering when you need to worry.

Or, the one that shows up in a bug report rather than a design doc: a compression routine has been running happily for two years, and then a customer file comes back from the round trip one byte longer than it went in, and nobody can find the bug. There is no bug.

All three are the same question, and the answer is not a matter of engineering judgment. It is a two-line proof from 1834.

Statement

If you put $n+1$ items into $n$ boxes, some box contains at least two items.

That is the whole thing. The generalized form is barely longer, and is the one you will actually use:

If $m$ items are placed into $n$ boxes, some box contains at least $\lceil m/n \rceil$ items.

Note what the statement does not mention: which items, which boxes, or any procedure for finding the collision. It is an existence claim, and it is the cheapest one in mathematics.

Argument

Suppose not. Suppose every box holds at most one item. There are $n$ boxes, so there are at most $n \cdot 1 = n$ items in total. But we placed $n+1$ items. And $n+1 > n$. Contradiction.

For the generalized form, run the same argument with a different bound: if every box held at most $\lceil m/n \rceil - 1$ items, the total would be at most

$$n \left( \left\lceil \frac{m}{n} \right\rceil - 1 \right) < n \cdot \frac{m}{n} = m$$

which is fewer than the $m$ items we started with. Contradiction again.

The strict inequality in the middle is the only step that needs care, and it holds because $\lceil x \rceil - 1 < x$ for every real $x$.

That is a complete proof. It is worth pausing on how little it used: no structure on the items, no assumption about how they were placed, no randomness, no limit. Counting two ways and noticing the two counts disagree. Most of the impossibility results in this series are this argument wearing a heavier coat.

Forbids

A lossless compressor that shrinks every input. Consider all $2^n$ inputs of length exactly $n$ bits. Suppose your compressor maps each to a shorter string. There are only $2^0 + 2^1 + \dots + 2^{n-1} = 2^n - 1$ strings shorter than $n$ bits. So $2^n$ inputs must fit into $2^n - 1$ output slots, and two inputs collide, and a compressor that maps two inputs to the same output is not lossless. Every “compresses any data by 30%” claim dies here, permanently, with no need to inspect the algorithm.

A hash function with no collisions, once the input space is bigger than the output space. A 64-bit hash of arbitrary-length strings has infinitely many inputs and $2^{64}$ outputs. Collisions do not merely happen; they are guaranteed to exist in unlimited supply.

Two people in a room of 366 with distinct birthdays. Boxes are days, items are people. (How quickly collisions arrive once you allow randomness is a very different and much more surprising question, and it gets its own post.)

Does not forbid

Here is where the principle gets misused, and the misuse is common enough to have a shape.

It does not say collisions are likely. This is the one that matters commercially. “Pigeonhole proves 64-bit hashes collide, therefore we need 256 bits for our cache keys” is an argument that has cost real teams real memory. The principle is an existence result over the whole input space: it says a colliding pair exists somewhere among all possible inputs. It says nothing about whether your particular ten million inputs will contain one. That question needs a probability, and the answer is roughly $m^2/2N$ for $m$ items and $N$ slots — the birthday bound, which is a genuinely different theorem and which gives much scarier numbers than most people expect. Pigeonhole is not the reason to size your hash. It is just the reason you cannot claim zero.

It does not forbid compression that works. The zip file on your disk is not a counterexample, and it is not cheating. General-purpose compressors shrink structured inputs and pay for it by lengthening some others, almost all of which are high-entropy strings nobody ever wants to store. The theorem forbids a universal win; it permits an enormously profitable trade, and the entire field of data compression lives in that gap.

It does not forbid perfect hashing. This trips people up. If you have a fixed, known set of $k$ keys and you build a table of $n \ge k$ slots, a collision-free hash function exists and there are standard constructions that find one. No contradiction: pigeonhole only bites when the items outnumber the boxes. Perfect hashing simply refuses to be in that regime, which is exactly why compilers and CDN routers use it for fixed keyword sets.

It does not forbid UUIDs from being fine. Version-4 UUIDs have 122 random bits. Pigeonhole guarantees two UUIDs collide somewhere in the space of all possible UUIDs, which is a true and completely useless statement about a space you will never enumerate.

The general shape: pigeonhole tells you a thing exists, and people read it as telling them a thing is probable, or as telling them a design is unsound. It does neither. It draws a hard line and says nothing whatsoever about how close to the line you are standing.

Boundary

The principle is tight in the strongest possible sense: with $n$ items and $n$ boxes there may well be no collision, so $n+1$ is exactly the threshold. There is no slack to exploit.

What lives just outside it:

  • Probabilistic pigeonhole. Ask not “does a collision exist” but “how many items before one is likely”, and you get the birthday bound and a $\sqrt{N}$ answer instead of an $N$ one. This is the single most practically important refinement, and it is the reason 64-bit IDs are riskier than intuition suggests.
  • Counting with weights. Replace “at least two items in a box” with averaging: if the mean is 5, some box holds at least 5. That is linearity of expectation, and it is pigeonhole with the integrality relaxed.
  • Changing what a box is. Most clever uses of this principle are not clever about the proof, which never changes. They are clever about choosing the boxes. The next post takes the compression argument above and pushes it to its full strength — no lossless compressor can shrink anything without growing something else — and the decision-tree bound for comparison sorting (T003) is the same principle applied to boxes you would not have thought of.