c++11 - Three type of Balls from Bag

Question

I have a problem which sounds like this: We have a bag with balls in. There are R red balls, B blue balls and G green balls. I need to find the minimum number of extractions from the bag such that i am sure that i will have at least K balls of same colour.

Anyone can help with any idea? Or tips, etc?

Answer 1

If K>max(R,G,B) then the problem has no solution. So let's assume K <= max(R,G,B).

If you don't have any control over which ball gets extracted, you'll need at most (i.e. this is a lower bound) min(R, (K-1))+min(G, (K-1))+min(B, (K-1))+1 extractions for obvious reasons: extract K-1 red balls (or all red balls if R<K), then extract K-1 green balls (or all green balls if G<K), and finally extract K-1 blue balls (or all blue balls if B<K). Now there is at least one ball remaining---because max(R,G,B)>=K by assumption---and when we extract it we have K balls of the same color. (This is clearly the worst case.)

You obviously need at least K extractions (this is the best case).

Since you tagged the question with probability, maybe you can only extract a ball chosen uniformly at random. In that case we can talk of the expected number of extractions needed before we end up with K balls of the same color. This is an interesting question.