## Friday, April 17, 2015

### Singapore Mathematics Olympiad: Techniques of Counting Problem

In a bag there are 120 green marbles, 80 blue marbles, 80 yellow marbles and 20 purple marbles. All the marbles are identical except for the colors. If you close your eyes, and pick marbles from the bag, what is the minimum number of marbles that you must pick in order to be sure of having at least two marbles that are of the same color?

If you have a strong foundation in probability and techniques of counting, you should be able to give the answer off the top of your head!

If we have $n$ distinguishable colors of marbles in our collection, (*provided the total of each color of marbles is greater than $n$), then the minimum number of marbles that we must pick in order to have at least two similar color of marbles is $n+1$.

Let’s say we have no luck and the first 4 marbles we picked are of 4 different colors, then regardless of what color of marble that we will get from the fifth draw, we will get two marbles that are of the same color. So the answer is 5.

You might argue, what if we have a bit of luck and we picked green marbles on the first and second draw, since green marbles are aplenty (120 out of the 300)? That means the minimum number of marbles that we must pick to have at least two similar color of marbles is 2.

No, one cannot rely on luck in this, what we want is certainty. The result that is determined by nothing but purely luck is weak. In the world of techniques of counting and probability, one should discard the result if luck is one of the factor that determines it.