Technique Encyclopedia
Pigeonhole Principle
What it is
The pigeonhole principle states that if n items are distributed among fewer than n containers, at least one container receives more than one item. It's almost trivial to state, but it proves existence results that would otherwise require an explicit (and often impossible) construction.
Signals that suggest using it
- The problem asks you to prove that at least two things must share some property, or that some configuration must occur.
- You're given a bounded set of categories (dates, remainders, colors) and a larger number of items.
- "Show that there exist ..." or "prove that at least two ..." phrasing.
When it's effective
Pigeonhole is ideal for existence proofs — showing something must happen without needing to find a specific example. It's often the fastest route when direct construction looks painful or when the problem only asks 'must this exist,' not 'what is it.'
When it's not effective
Pigeonhole only proves existence — it never tells you what the guaranteed repeated or overlapping item actually is, and it gives no help if a problem wants an exact count rather than a yes/no guarantee.
Simple example
Problem
Show that among any 13 people, at least two must share a birth month.
Solution
There are only 12 possible birth months (the containers) and 13 people (the items). Since 13 > 12, by the pigeonhole principle at least one month must contain at least two people.
AMC-style example
Problem
Five points are placed inside a unit square (side length 1). Show that some two of them are within √2⁄2 of each other.
Solution
Divide the unit square into 4 smaller squares of side 1/2 by bisecting each side. This gives 4 containers for 5 points, so by pigeonhole, two points must land in the same small square. The farthest apart two points can be within a 1/2-side square is its diagonal, √2⁄2, which bounds their distance.