Question

There are 20 black, 15 white, 12 green, 12 red, 9 blue and 2 yellow candies in a box. How many candies should you take (without looking at them) to be sure that you have at least 3 candies the same color?

Answer 1

Answer:  13

=============================================================

Explanation:

The best case scenario is that you get 3 of the same color in a row on the first three attempts. The lower bound is 3.

However, we have to consider the worst case scenario when we want to guarantee something like this, without looking at the candies we selected.

Consider the case of something like this sequence:

1. black
2. white
3. green
4. red
5. blue
6. yellow
7. black
8. white
9. green
10. red
11. blue
12. yellow
13. black

As you can see above, I've listed the colors in the order presented by your teacher. I pick one candy at a time. Once I reach yellow, I restart the cycle. In slots 1, 7 and 13, we have a black candy selected. This example shows that we must make 13 selections to guarantee that we get at least 3 candies of the same color (that color being black). The order of the candies selected doesn't matter. We could easily use any other color except yellow to do this example. The black candy just happened to be the first listed, so I went with that.

Note how we have 6 unique colors in the set {black, white, green, red, blue, yellow}. If we pick 2 candies of each color, then we've selected 6*2 = 12 candies so far. That 13th candy (some color other than yellow) is guaranteed to be a color we already selected; therefore, we'll be guaranteed to have 3 of the same color. We won't know what color it is but we will know we have a match like this.

For more information, check out the Pigeonhole Principle.