Pigeonhole Principle

n items in k boxes: some box has ≥ n/k items.

The idea

Theorem (Pigeonhole principle).

If $n$ items are placed into $k$ boxes, then some box contains at least $\lceil n/k \rceil$ items. In particular, if $n > k$ then some box contains at least $2$ items.

Here $\lceil x \rceil$, the ceiling of $x$, means $x$ rounded up to the nearest integer. Nothing else is assumed — not what the items are and not how they were distributed.

The principle guarantees that a crowded box exists without offering any way to find it, and that bare existence is often exactly what a proof needs. In applications the work lies in choosing what to call an item and what to call a box.

Ways to work on it

• Walkthrough. Birthdays, friends, and the pigeonhole logic.
• Proof. See why it's forced — a one-line counting contradiction.
• Practice. Easy pigeonhole bound — small k.
• Hardest. Reverse pigeonhole: fewest items to force a box of a given size.

Not sure where to start? Take the ten-question placement test.