Problem 21 · 1994 AJHSME
Hard
Counting & Probability
pigeonhole
A gumball machine contains 9 red, 7 white, and 8 blue gumballs. The least number of gumballs a person must buy to be sure of getting four gumballs of the same color is
Show answer
Answer: C — 10.
Show hints
Hint 1 of 2
'To be SURE' means it has to work even on your unluckiest day. So picture the meanest possible streak — how long can the machine keep you from ever getting four of one color?
Still stuck? Show hint 2 →
Hint 2 of 2
The worst it can do is hand you three of every color. Count those, then take one more — that next gumball has nowhere to hide.
Show solution
Approach: worst case, then one more
- Build the unluckiest run: 3 red, 3 white, 3 blue = 9 gumballs, and STILL no color has four. This is the most you can hold without a four-of-a-kind.
- The very next (10th) gumball is red, white, or blue — whichever it is, that color jumps to four. So 10 guarantees it.
- Notice the colors had 9, 7, 8 in stock — plenty to spare, so those numbers were a distraction; all that mattered was '3 colors.' This is the pigeonhole idea: to FORCE k of some category among c categories, survive the worst case of (k−1) in each, then add 1 → c(k−1)+1. Here 3(3)+1 = 10.
Mark:
· log in to save