5
$\begingroup$

We have a bag full of many balls (let's say n balls). We cannot see inside of the bag but we are certain that only a certain number of them are blue (let say r). If we want to randomly choose half of the total balls in the bag, what is the probability that we have selected all of the blue balls in our sample?

choosing <code>n/2</code> from <code>n</code> balls

Here is how I think of this. If the number of balls in the bag are much larger than the number of blue balls. I can think of all blue balls as one single package and group other balls in groups with the same size. Then the prroblem reduces to: what is the probablity of selecting the blue package among the selection of half of the total groups which is equal to:

$${(m-1)\over ^m C_{m/2}} = {{m\over 2}! {m\over 2}!\over m \times (m-2)!}$$

where m is the number of groups. This converges to the exact solutiuon when m is big. But I'm still uncertain about the exact solutiuon of this problem. I appreciate you sharing your thoughts and comments.

enter image description here

$\endgroup$

migrated from stackoverflow.com May 31 '17 at 19:40

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Interesting title to see in HNQ... $\endgroup$ – Dmitry Kudriavtsev Jun 1 '17 at 5:23
5
$\begingroup$

This can be reduced to a combinatorics problem. Let's make it a little more general.

Suppose you have $n$ balls, of which $r$ are blue. You select $k,$ where $k > r.$

What are the total number of ways you can select $k$ balls out of $n?$

Then, what are the total number of ways you can select $k$ balls out of $n,$ where $r$ of the $k$ balls are necessarily the blue balls?

Divide the latter answer by the former, and you have your answer.

CLARIFICATION: The answer is easy if in the second part you think of all blue balls as a single package. Then to the latter point, suppose we have already selected this blue package. What is the other possible combinations? The answer would be choosing k-r (not k, because we have already selected all r blue balls and put it aside) from n-r remaining balls. In summary the probability that we have selected all of the blue balls in our k sample is equal to

$${^{n-r}C_{k-r}\over ^n C_k} = {(n-r)! k! \over (k-r)! n!}$$. For the special case of k=n/2 we have

$${^{n-r}C_{{n\over 2}-r}\over ^n C_{n\over 2}} = {(n-r)!{n\over 2}!\over ({n\over 2} -r)! n!}$$

enter image description here

$\endgroup$
  • $\begingroup$ I think that's the right approach. I added the mathematical expression based on the idea of considering all the blue balls as a single package which has a unified identity. I'll fix the expression in the question too. $\endgroup$ – turtle May 31 '17 at 21:22
6
$\begingroup$

It's a typical brain teaser. Invert the question: what is the probability that none of the blue balls are scooped out of the bag?

All of a sudden it's easy to answer! $$\frac{n-r}{n}\frac{n-r-1}{n-1}\dots\frac{n-m+1-r}{n-m+1}=\frac{(n-m)!(n-r)!}{n!(n-r-m)!}$$

You pull the first ball, and it's not blue. How likely it is? $\frac{n-r}{n}$ So, you keep pulling them until you got $m$ balls out, and none of the blue balls showed up yet. And you get the answer above, which is also the answer to the original question where $m=n/2$. thanks to @Bridgeburners comment

Here's why this works. The original problem is formulated in terms of the balls that were pulled (chosen) from the bag: we want all the blue balls out. It's shown in the picture below.

![enter image description here

However, the next picture shows that the answer got to be the same in terms of the inverted problem about all balls being red, i.e. none of the balls being blue. ![enter image description here So, if the question is about probability of all $r$ blue balls being chosen in the group of $k$ balls, then it's equivalent to a question about probability of $m=n-k$ balls being left in the bag after $k$ balls are removed from it. Hence, in terms of the $k$ balls out the same answer can be written as: $$\frac{k!(n-r)!}{n!(k-r)!}$$

To summarize, the solution is very simple and intuitive if you re-formulate the problem in terms of the unchosen balls being all red.

$\endgroup$
  • $\begingroup$ I like this answer but let me think about it $\endgroup$ – turtle May 31 '17 at 20:05
  • $\begingroup$ @Dr.Manhattan, sure, but on the interview the dudes who ask these types of questions want you to answer them in a minute or so while distracting you with a chatter :) $\endgroup$ – Aksakal May 31 '17 at 20:06
  • 1
    $\begingroup$ If anytime you notice the dude who ask this type of questions prefers a quick answer over a right answer, RUN. Because that's a shi**y company and toxic workplace. By the way, negative $$(n/2 - r)$$ should not be allowed in your final expression, because it is the factorial argument. But, it IS completely allowed by the problem (however the answer must turn out zero, in this case). $\endgroup$ – turtle May 31 '17 at 20:40
  • 1
    $\begingroup$ One minus the probability of getting no blue balls in your selection is the probability of getting any number of blue balls in your selection, not necessarily all of them. Think of the set of mutually exclusive states. The probability of all possible events must sum to one. $\endgroup$ – Bridgeburners May 31 '17 at 20:53
  • $\begingroup$ @Bridgeburners, no blue balls pulled from a bag means that all of them are in the bag. $\endgroup$ – Aksakal May 31 '17 at 20:58

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.