4
$\begingroup$

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?

  • 0
    @AndréNicolas, +1 for correcting me that it is Combinatorics and not probability theory. Please make it an answer (I cannot +1 comments yet)2011-11-22

2 Answers 2

1

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.

5

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).

  • 0
    @BenDerrett ah, right. I should stop doing arithmetic in my head! :-)2011-11-22