Problem 13 · AMC 8 Stretch
Core
Counting & Probability
pigeonholeextreme-cases
A bin holds a mix of 3 kinds of apples. A customer wants 3 apples of the same kind. What is the smallest number of apples they must grab to be guaranteed 3 of the same kind (and show that one fewer might not be enough)?
Show answer
Answer: 7 apples
Show hints
Hint 1 of 4
Think about the worst luck. How many apples could you grab while still avoiding 3 of any one kind?
Still stuck? Show hint 2 →
Hint 2 of 4
With 3 kinds, the worst case is 2 of each kind. How many apples is that?
Still stuck? Show hint 3 →
Hint 3 of 4
That worst case is \(2 \times 3 = 6\) apples with no kind reaching 3 — so 6 can fail.
Show solution
Approach: Pigeonhole / worst case — 3 kinds as boxes
- Use the 3 kinds as 3 boxes. To dodge getting 3 of a kind, each box can hold at most 2 apples.
- The most apples grabbed that way is \(2 \times 3 = 6\) (exactly 2 of each kind) — so 6 apples might not give 3 of a kind.
- Grab a 7th apple: now 7 apples in 3 boxes, and \(7 = 2\times 3 + 1\), so some box must hold at least 3.
- That's 3 of the same kind, guaranteed, so \(7\) is the smallest number that always works.
Mark:
· log in to save