Pigeonhole principle
A Socratic walk-through of the pigeonhole principle — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why must two people in a large city have exactly the same number of hairs on their head?
Somebody tells you that in a city of several million, two people certainly have precisely the same number of hairs on their head. Not probably. Certainly. And they say this without having counted a single head, without knowing a single resident, and without any claim about how hair works.
That should feel like a trick, because ordinarily a claim about the world is bought with evidence about the world. Here the claim seems to arrive free. So what is actually being paid? It is worth being suspicious enough to find the invoice.
Reasoning it through
REASONING #Strip the hair away and look at the shape of the assertion. There is a set of people, and each person is assigned one value from some set of possible values. If the people outnumber the possible values, at least two must share — because the only way for everyone to differ is for each to occupy a distinct value, and you have run out of distinct values before you have run out of people. That is the whole argument, and stated that baldly it is not so much a theorem as a refusal to allow a contradiction.
So where did the world sneak in? Precisely in "the set of possible values". The mathematics contributes nothing about heads. Someone has to supply an upper bound on how many hairs a human head can carry, and that bound is empirical. The commonly quoted figure for a typical scalp is on the order of a hundred thousand, with the usual range running up towards a hundred and fifty thousand — and those numbers are estimates from sampling small patches, so treat them as approximate. But the argument does not need precision. It needs a ceiling that no head could plausibly reach, and one million is generous by a factor of several. Take a city larger than a million, and the counting closes.
Notice that the ceiling is doing the real work, and notice also what else is quietly required. The values must be whole numbers. If we asked instead for two people with exactly the same mass of hair, in grams to the last decimal, the argument dies instantly — not because masses are unbounded, but because between any two of them lie infinitely many others, so the boxes never run out. Discreteness and boundedness, together, are the price of the free claim. Change either and the certainty evaporates.
Now, having got the conclusion, ask what kind of thing we actually got. We know two such people exist. Can we name them? No. Can we narrow them down? Not at all. Could we find them faster than by counting every head in the city? Nothing in the argument helps. This is about as pure an example as exists of a proof that establishes existence while offering not one step towards construction — and that gap is not a defect of this particular argument but a recurring feature of the technique.
There is a second thing worth noticing, which cuts the other way: the conclusion is embarrassingly weak. The principle generalises — if you place N items in k boxes, some box holds at least N divided by k, rounded up. With nine million residents and at most a million possible counts, we are entitled to say that at least nine people share a value, and we could raise that considerably by using a tighter ceiling. Yet the truth is far stronger still, because the counts are not spread evenly across the range; nearly everyone sits in a narrow band, so in reality thousands share each common value. Pigeonholing gives a guarantee that no arrangement can dodge, which is exactly why it stays so far below what typical arrangements do.
And this is where the technique earns its place in real mathematics rather than in puzzles. Dirichlet used it to prove that every irrational can be approximated by fractions to better than one over the square of the denominator — by chopping the unit interval into a fixed number of boxes and dropping in the fractional parts of successive multiples until two collide. That result founds the theory of Diophantine approximation. The same counting also sets the hard limit on lossless compression: there are fewer short files than long ones, so no scheme can shorten every input.
The analogy
THE ANALOGY #Think of a car park with a fixed number of marked bays and a queue of cars longer than that number. Nobody has to inspect the cars, know their owners, or watch them arrive. Once the last bay is taken, the next car shares a bay with somebody — and you can be certain of that from the gate, without seeing inside.
A car park physically prevents double occupancy, whereas nothing prevents two people having equal hair counts — the principle is not a force pushing anyone into a shared box, only a bookkeeping fact about the counts. And a real car park has a bay count you can read off a sign; the number of possible hair counts is something we must argue for from outside the mathematics.
Clarifying the model
THE MODEL #Two clarifications keep the principle from being over-claimed.
First, "at least two share" is a floor, never a description. People sometimes take a pigeonhole result as though it characterised the situation — it does not; it states the least that any arrangement whatsoever must concede. When the actual distribution is lumpy, as human hair counts certainly are, the floor sits absurdly far beneath the truth. That is a feature: the guarantee holds even for an adversary arranging things to make it fail.
Second, applying it to the world is always two claims joined, and only one of them is safe. The combinatorial half is airtight. The half that says "there are at most a million possible values" is a physical assertion that can be wrong, and if it is wrong, the certainty goes with it. Most bad uses of the principle in the wild are not counting errors; they are unexamined ceilings.
A picture of it
THE PICTURE #How to readThis repurposes a kanban board: the columns are not stages of work but the possible values a quantity can take, and the cards are the individuals being placed. Read it as a miniature of the real problem with the numbers shrunk — five people, four available columns. Every card must land in some column, and no arrangement of five cards across four columns leaves each alone, so one column carries two. That doubled column is the whole conclusion; note that nothing on the board tells you in advance which column it will be.
What became clearer
WHAT CLEARED #The certainty is real, and it is cheap, and it is cheap because it says so little. The principle contributes only the observation that you cannot fit more items than boxes without a repeat; everything specific to hair — and every way the argument could fail — lives in the claim that the boxes are finite in number and whole in kind. What you buy for that price is a guarantee no arrangement can escape, together with total ignorance about where in the city to look.
Where to go next
ONWARD #- Why the birthday problem reaches a similar conclusion by a completely different route, trading certainty for a much smaller number of people.
- Ramsey theory, which pushes the same counting idea until it forces structure rather than mere repetition.
Key terms
TERMS #| Term | What it means |
|---|---|
| Pigeonhole principle | if more items than boxes are distributed among the boxes, some box holds at least two. |
| Generalised pigeonhole principle | with N items in k boxes, some box holds at least N/k rounded up. |
| Non-constructive proof | an argument establishing that something exists without indicating how to find or build it. |
Every term the collection defines is gathered in the glossary.