Problem 16 · 2005 AMC 8
Easy
Logic & Word Problems
pigeonhole
A five-legged Martian has a drawer full of socks, each of which is red, white or blue, and there are at least five socks of each color. The Martian pulls out one sock at a time without looking. How many socks must the Martian remove from the drawer to be certain there will be 5 socks of the same color?
Show answer
Answer: D — 13.
Show hints
Hint 1 of 2
'To be certain' means plan for the unluckiest draw possible. Ask: what's the most socks you could hold and still not have 5 of any one color?
Still stuck? Show hint 2 →
Hint 2 of 2
This is the pigeonhole idea: pile each color as high as it can go without hitting the target (4 each), then the very next sock is forced to push some color over.
Show solution
Approach: pigeonhole — build the worst case, then add one
- Imagine the meanest possible luck: 4 red, 4 white, 4 blue. That's 12 socks and still no color has reached 5.
- There's nowhere left to hide — the 13th sock must be a 4th color's... no, must be the 5th of some color. So 13 guarantees it.
- Why this transfers: for 'how many to guarantee' problems, find the largest haul that fails the goal (here 3×4 = 12), then add 1. The five legs in the story are pure distraction — only the three colors matter.
Mark:
· log in to save