Pigeonhole Principle and Generalizations

Intro to Proofs · Axiom Academy

LESSON The Pigeonhole Principle A deceptively simple idea — more pigeons than holes — that proves things must exist without ever constructing them. This is almost too obvious to state! If you have 3 pigeons and only 2 holes, then at least one hole must contain at least 2 pigeons. There's simply nowhere else for the third pigeon to go. The basic principle tells us some container has more than one item. But we can be more precise about how many must be in the fullest container: (Here is the ceiling function: the smallest integer .) Place 10 items into 3 boxes. Then some box must hold at least items. Why? Suppose not — suppose every container held fewer than items, i.e. at most each. Then the total is at most items, contradicting that we placed all n . Proof. We have 13 people (pigeons) and 12 months (holes). Since 13 > 12 , the Pigeonhole Principle forces at least one month to contain at least people. In any group of 367 people, at least two share a birthday (366 possible dates, including Feb 29). In any set of 11 integers, at least two leave the same remainder when divided by 10. Any two people on Earth have the same number of hairs on their head (at most ~150,000 hairs, but ~8 billion people). The true power of the Pigeonhole Principle emerges where the "pigeons" and "holes" aren't handed to you — you have to invent them.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.