Problem 1 · AMC 8 Stretch
Core
Logic & Word Problems
Counting & Probability
consider-extreme-casesaccount-for-all-possibilitiespattern-recognition
In a fairy tale, a hero must collect golden hairs from a devil's head. The devil's grandmother is blind, so she pulls hairs out at random. The devil has \(5\) hairs in all, and \(3\) of them are golden. How many hairs must the blind grandmother pull to be sure she has at least one golden hair? Then think bigger: the devil has \(x\) hairs, \(y\) of which are golden. How many hairs must be pulled to be sure of getting at least \(z\) golden hairs? (Here \(z \le y \le x\), and all are whole numbers.)
Show answer
Answer: 3 hairs in the small case; (x−y)+z hairs in general
Show hints
Hint 1 of 4
The word 'sure' is the key. You can't count on getting lucky. Ask yourself: what is the unluckiest possible order in which the hairs could come out?
Still stuck? Show hint 2 →
Hint 2 of 4
Pretend the grandmother has the worst luck in the world: she keeps grabbing only the non-golden hairs first. With \(5\) hairs and \(3\) golden, how many hairs are NOT golden?
Still stuck? Show hint 3 →
Hint 3 of 4
Once every non-golden hair is gone, the very next pull MUST be golden. There are \(5-3=2\) non-golden hairs, so after pulling those \(2\), the next pull (the 3rd) is guaranteed golden.
Show solution
Approach: Worst-case (pigeonhole-style) reasoning
- 'Sure' means it must work even with the worst luck: every non-golden hair comes out first. There are \(5-3=2\) non-golden hairs.
- So in the worst case the first 2 pulls are both non-golden; then only golden hairs are left, so the 3rd pull must be golden. She must pull \(2+1=3\) hairs.
- General case: there are \(x-y\) non-golden hairs. In the worst case she pulls all \(x-y\) of them first and gets no gold; after that every remaining hair is golden.
- To collect \(z\) golden hairs she pulls \((x-y)+z\) hairs. Check with \(x=5, y=3, z=1\): \((5-3)+1=3\), which matches. (This is the same idea behind pigeonhole problems.)
Mark:
· log in to save