2
$\begingroup$

A bag contains $a$ red balls, $b$ green balls and $c$ blue balls. We can take balls out of bag without knowing which one we choose (blindfolded). We do not replace the balls back in bag, we simply take balls out. What are the minimum number of balls we should choose so that we have $k$ balls of same color?

Eg: If the bag contains $2$ red, $2$ green, and $2$ blue and $k=2$ then we need to choose minimum $4$ balls out of bag such that $2$ balls are of same color. But if $k=1$, we just need to choose $1$ ball.

$\endgroup$
  • $\begingroup$ That means you should have superpower to chooSe k balls exactly of the same colour and $a_1,b_1,c_1\geq k$ $\endgroup$ – Archis Welankar Apr 2 '16 at 15:59
  • $\begingroup$ @JimmyR. EDITED.we have to take minimum balls out of box such that k balls are of same color.I gave an example there. $\endgroup$ – satyajeet jha Apr 2 '16 at 16:05
5
$\begingroup$

I will suppose, that at least one of $a, b, c$ is at least $k$, otherwise it is impossible to have $k$ balls of the same color. Then the answer is $\min(a, k - 1) + min(b, k - 1) + min(c, k - 1) + 1$. You can think of it the follwing way: in the worst case one can take $min(a, k - 1)$ red balls, $min(b, k - 1)$ green balls and $min(c, k - 1)$ blue balls and still not have k balls of the same color. Then adding any ball will guarantee $k$ balls of the same color.

$\endgroup$
  • $\begingroup$ Can we solve this problem using binomial coefficient or some other way of combinatorics ? $\endgroup$ – satyajeet jha Apr 2 '16 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.