The Pigeonhole Principle: Your First Move on Most Olympiad Problems
If n+1 pigeons sleep in n holes, one hole is crowded — and that single sentence wins a shocking number of olympiad problems. Here is how to spot the pigeons hidden inside a statement.
Olympiad Desk · Core Learning
What you will take away
- Restate every problem as "objects" and "boxes" before doing anything else
- The hard part is choosing the boxes — the counting is usually one line
- Extended form: with n boxes, some box holds at least ceil(total / n) objects
- Works on sums, remainders, distances and dates, not just literal holes
The pigeonhole principle is the cheapest powerful tool in olympiad mathematics. It needs no algebra, no diagram and no clever substitution — only a decision about which objects are pigeons and which are holes.
Step 1 — Find the boxes
Almost every pigeonhole problem hides its boxes in a remainder, a range or a partition. Ask three questions: what are the objects being counted, what natural buckets do they fall into, and how many buckets are there compared with the number of objects?
- Remainders mod m → m boxes
- A closed interval split into n equal parts → n boxes
- A set of friends partitioned by "how many friends" → deg + 1 boxes
- Strings over an alphabet of size a with length L → a^L boxes
Step 2 — Turn the conclusion into a formula
Olympiad statements rarely say "two are equal". They say "there exist two of them whose difference is divisible by seven", which is exactly "two objects land in the same remainder class mod 7". Translate the conclusion into box-speak before you start counting; the translation usually reveals the boxes.
Step 3 — Check the inequality, then write it up
A complete solution names the objects, names the boxes, shows k > n, and states the conclusion. Three sentences. Examiners give full credit for the right boxes, so spend your time there rather than on decoration.
Worked problems
- 1
Show that among any 13 integers there are two whose difference is divisible by 12.
Show hint
The divisibility condition is a statement about remainders, and there are only 12 possible remainders mod 12.
Show solution
Take the 12 remainder classes mod 12 as boxes and the 13 integers as pigeons. With 13 pigeons in 12 boxes, two integers a and b share a remainder, so a − b ≡ 0 (mod 12).
Answer: Two of the 13 integers leave the same remainder mod 12, hence their difference is divisible by 12.
- 2
Eight friends sit around a table. Prove that two of them have the same number of friends present at the table.
Show hint
The possible friend counts are 0, 1, …, 7 — that is 8 values for 8 people, so you need one more observation before counting.
Show solution
The counts 0 and 7 cannot both occur: if someone knows nobody, nobody can know everybody. So the 8 people only use 7 possible counts (either 0–6 or 1–7). By pigeonhole, two people share a count.
Answer: The 8 friend-counts are drawn from only 7 possible values, so two coincide.
