[Solved] Three type of Balls from Bag

Question

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.

Accepted Answer

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.