# Jar of candies: Minimum subset size to satisfy a condition

Here is a problem my son was trying to solve:

A bowl contains 100 pieces of candy: 48 green, 30 red, 12 yellow and 10 blue. They are all wrapped in a foil, so the color of no candy is visible. How many pieces should be picked at a minimum to ensure 15 candies of the same color are picked?

I could intuitively guess, it will take picking all the colors that do not satisfy 15 (12 yellow + 10 blue), and then picking 14 of each possible color (14 green + 14 red) and then one more to ensure 15.

For the life of me, I cannot find how to solve it mathematically, or to validate my answer. I feel it is somehow related to sampling without replacement, but my probability knowledge fails me.
What is the correct way to mathematically solve this?

-
The reasoning is correct, and fully mathematical. Probability is needed only for questions like "if I pick $32$ candies at random, what is the probability I will have at least $15$ of the same colour?" (This is a lot harder.) In explaining your answer, it may be useful to imagine, after you pick a bunch of candies, that you unwrap them and put them in suitably labelled boxes. labelled green, red, and so on. It is now easier to explain why $50$ may not be enough, and why $51$ is enough. –  André Nicolas Nov 22 '11 at 17:54
You can also relate this to the Pigeonhole Principle, if you want to invoke a mathematical result by name to make it seem more mathematical (it is plenty mathematical already) –  Arturo Magidin Nov 22 '11 at 20:17
@AndréNicolas, +1 for correcting me that it is Combinatorics and not probability theory. Please make it an answer (I cannot +1 comments yet) –  Clark Gable Nov 22 '11 at 20:39
add comment

## 2 Answers

The reasoning is correct, and fully mathematical. Probability is needed only for questions like "if I pick $32$ candies at random, what is the probability that I will have at least $15$ of the same colour?" (This is a lot harder.)

In explaining your answer, it may be useful to imagine, after you pick a bunch of candies, that you unwrap them and put them in boxes labelled green, red, and so on. Then we can use the sum of the number of candies in the various boxes to reason our way to a proof.

Formally, the proof consists of two parts: a) $50$ candies are not enough to ensure that we have $15$ of the same colour and b) $51$ candies are enough.

To prove a), we need only observe that the $50$ candies could consist of $14$ green, $14$ red, $12$ yellow, and $10$ blue. That was not explicitly stated in your argument, but it was implicitly there.

To prove b), observe that if we had no more than $14$ of any colour, then we could have at most $14+14+12+10=50$ candies. It follows that if the number of candies is $>50$, there will be at least $15$ of the same colour.

The two arguments a) and b) are logically quite distinct. However, they are so closely related that it is tempting (and not unreasonable) to prove a) and b) by a single piece of reasoning. In more complex situations, the arguments for "$A$ implies $B$" and "$B$ implies $A$" can be very different from each other. Indeed, the implication in one direction may be true, while the other implication is false. It is sometimes difficult to train students to distinguish between "$A$ implies $B$" and "$B$ implies $A$," since in most of the results they have seen in school, the implication runs in both directions.

-
add comment

You will need to pick 51 candies to get at least 15 of the same color. Here is the logic:

1. 15 candies will not do as all of them can be a mix of yellow, blue, red and green.

2. How many more should you pick?

If you pick 20 candies there is no guarantee that they will all be the same color as you could have picked the 10 yellow and the 10 blue. Very soon you realize that picking 22 candies will still not satisfy your condition as they can be 12 yellow and 10 blue.

3. Will picking 22 + 15 candies be enough?

No. In the worst possible scenario you could have picked 12 yellow, 10 blue and a mix of green and red for the remaining 15 candies.

4. So, point 3 suggests that you should pick at least 22 + 29 candies.

That way in the worst possible scenario you would pick: 12 yellow, 10 blue (to get to 22), 14 red, 14 green, 1 candy that is either green or red (to get to the additional 29).

-
How do we get the number 31? –  Ben Derrett Nov 22 '11 at 15:52
@Ben Think of the worst possible scenario. Suppose that you pick an additional 15 candies beyond the 22 (12 yellow and 10 blue). You may be able to get lucky and pick 15 additional red candies but there is no guarantee that you will. You may just as well pick 7 red and 8 green. Thus, the only way to guarantee that you will have 15 of the same color is to pick 31 as in the worst possible scenario you would have 14 red, 14 green and one additional candy that is either red or green. –  tards Nov 22 '11 at 15:55
Doesn't that make 29 extra candies (14+14+1)? –  Ben Derrett Nov 22 '11 at 15:59
@BenDerrett ah, right. I should stop doing arithmetic in my head! :-) –  tards Nov 22 '11 at 16:01
add comment