Pigeonhole Principle
More items than boxes forces at least one box to hold two.
What is it?
If items go into boxes with , some box contains at least items.
Why is it useful?
It proves existence claims ("there must be two…") that interviewers use as quick logic puzzles.
When should you think of it?
Use it when asked to show something must happen, or for the minimum draws that guarantee a result.
Think of this method when…
- "Prove that there must be…" or "guarantee"
- Minimum number of draws to ensure a pair
- Points in a region and a distance bound
- More objects than categories
Core idea
Choose the boxes cleverly; then count.
Step-by-step playbook
- 1Decide what the pigeons and holes are.
- 2Make the holes small enough that two pigeons in one hole gives the claim.
- 3Count pigeons versus holes.
Worked example
Worked example
Show that among any 5 points in a unit square, two are at distance at most .
- 1
Split the square into four squares (holes).
- 2
Five points in four squares: two share a square, whose diagonal is the largest possible distance.
- Answer: Two points lie within
Common mistakes
- Choosing holes too large for the conclusion.
- Confusing a guarantee (worst case) with a probability.
Would you use this method?
A drawer has socks in 3 colors. How many must you draw to guarantee a matching pair?
Practice this method
4 QuantSolve questions are tagged with this method.
Practice this method