More pigeons than holes means two pigeons share a hole. The interview trick is choosing the right pigeons and holes.
Method · Pigeonhole
Intro
BenFrantzDale, edited by McKay, CC BY-SA 3.0 · CC-BY-SA-3.0 / GFDL · Wikimedia Commons
If you have more pigeons than holes, some hole gets at least 2 pigeons. Olympiad-flavored but interview-direct: many counting problems collapse the moment you spot the right partition into boxes. The formula is trivial — $n+1$ pigeons in $n$ boxes — so the entire skill is finding the boxes.
✓ Intro · expand
Try first (productive failure)
Before the worked example: spend 60 seconds taking your best shot at this.
A guess is fine — being briefly wrong about a problem makes the explanation
land harder when you read it. This appears once per tutorial; skip
if you already know the trick.
60s
✓ Try first · expand
Worked example
A drawer holds socks of 3 different colors mixed together. How many socks must you pull out (without looking) to guarantee that at least 2 of them are the same color?
✓ Worked example · expand
Practice 1 of 3Type a fraction, decimal, or expression — mathjs parses it.
✓ Practice · expand
Reflection
In your own words, what makes pigeonhole problems hard or easy? What was the “box” in the last problem — and what made it less obvious than “color” or “month”?
