2019 AMC 10A Problem 4

P1-10~2 minPrint

Sets, Estimation & Miscellaneous Consider the largest/smallest element or boundary case Pigeonhole principle

A box contains $28$ red balls, $20$ green balls, $19$ yellow balls, $13$ blue balls, $11$ white balls, and $9$ black balls. What is the minimum number of balls that must be drawn from the box without replacement to guarantee that at least $15$ balls of a single color will be drawn $?$

Show solution without answering

Key insight

Build the worst draw with no 15 of a color: 14 of each big color plus every small-color ball, 75 in all. One more forces it.

Solution

"Guarantee" means you must plan for the unluckiest possible draw. So first ask: how many balls can you draw and still not have $15$ of any one color? Then one more ball is the answer.

Big colors. Red ( $28$ ), green ( $20$ ) and yellow ( $19$ ) each have at least $15$ balls. You can take up to $14$ of each without reaching $15$ : $3 \cdot 14 = 42$ balls.
Small colors. Blue ( $13$ ), white ( $11$ ) and black ( $9$ ) have fewer than $15$ balls, so you can never reach $15$ of these. You can take all of them: $13 + 11 + 9 = 33$ balls.
Unluckiest draw. $42 + 33 = 75$ balls, and still no color has $15$ .
One more ball. After those $75$ , every ball left in the box is red, green or yellow, and each of those colors already has $14$ drawn. So ball number $76$ makes some color reach $15$ .

So $75$ balls are not enough, and $76$ always are.

The answer is $\boxed{\textbf{(B)}\ 76}$ .

Why this works

This is the pigeonhole idea: build the largest draw that avoids the goal, then add one. The key detail is that each color can give at most the smaller of $14$ and the number of balls it has. Choice (D), $84 = 6 \cdot 14$ , is what you get if you forget that the small colors run out early.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Ask how many balls can be drawn while avoiding $15$ of any one color. Each color can contribute at most $14$ balls, but a color with fewer than $14$ balls can only contribute all of them:

red, green, yellow: $14$ each, total $42$ ;
blue $13$ , white $11$ , black $9$ : total $33$ .

So $42 + 33 = 75$ balls can be drawn with no color reaching $15$ . This is the maximum such draw, so once $76$ balls are drawn, some color must appear at least $15$ times (the only colors with room to grow are red, green and yellow, and one of them gets a $15$ th ball).

The answer is $\boxed{\textbf{(B)}\ 76}$ .

Review in the AoPS books

Intermediate Counting & Probability, Chapter 2: Sets and Logic (§2.2, §2.3)
Intermediate Counting & Probability, Chapter 5: The Pigeonhole Principle
Prealgebra, Chapter 7: Ratios, Conversions, and Rates (§7.4)