2010 AMC 10B Problem 3

P1-10~1 minPrint

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

A drawer contains red, green, blue, and white socks with at least 2 of each color. What is the minimum number of socks that must be pulled from the drawer to guarantee a matching pair?

Show solution without answering

Key insight

Four colors means you can pull four socks that are all different. The fifth sock has to match one of them.

Solution

"Guarantee" means the answer must work even with the worst possible luck. So imagine the unluckiest draw.

With bad luck, the first four socks could be one red, one green, one blue and one white. That is four socks and still no pair. So $4$ socks are not enough.
Now pull a fifth sock. It has to be red, green, blue or white, and each of those colors is already in your hand. So the fifth sock always makes a pair.
The drawer has at least $2$ of each color, so a pair of any color really can happen.

Four socks might fail, and five never fail, so the answer is $5$ .

The answer is $\boxed{\textbf{(C)}\ 5}$ .

Why this works

For a "guarantee" question, first build the biggest draw that still fails (one sock of each color), then add one more. With $4$ colors that is $4 + 1 = 5$ . This idea is called the pigeonhole principle: $5$ socks going into $4$ color "boxes" means some box gets two.

Concise solution

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

Think about the worst case. With four colors available, it is possible to draw four socks that are all different: one red, one green, one blue, one white. So four socks do not guarantee a pair.

Once a fifth sock is drawn, there are only four colors for five socks, so two of them must share a color. This is the pigeonhole principle with the colors as the "holes."

Hence $5$ socks are needed, and the answer is $\boxed{\textbf{(C)}\ 5}$ .

Review in the AoPS books

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