Teacher is playing a game with his students. He is having $k$ red balls. Each of his student is either having a red or black ball. $M$ students have red balls and $N$ students have black balls.
Now each student come one by one randomly to teacher.

  • If student has red ball, the teacher keeps the red ball.
  • If student has black ball then teacher give a red ball to student.

  • If at any time teacher run out of red ball when student with black
    ball comes to him, then teacher looses.

  • If teacher successfully gave red ball to every student arriving to him with black ball, then teacher wins.

Now what is the probability that the teacher wins?

I tried to solve for this by using the following trivial conclusions:

It is clear that if N <= k, then teacher always wins.

For N > k, let R and B be event the student with red ball and student with black ball respectively, visits the teacher. So some string is formed by the visit sequence eg BBBRRBBB... then for any prefix P, if Number of R's + k < Number of B's, then teacher looses.

But unable to solve the problem. Need help.

  • $\begingroup$ Also, Teacher always loses if $k+M<N$ $\endgroup$ – Jean-Sébastien Feb 7 '13 at 19:40

As noted above, if $N\leq k$ then teacher always wins, and if $k+M<N$ then he always loses. Let us be in a position where the teacher wins with probability $p\in(0,1)$. Then I think $p$ is given by $$ p=\frac{\displaystyle\sum_{j=0}^{\min(k,M-N+k)}{N\choose k-j}{M\choose N-k+j} }{\displaystyle{N+M \choose N}}. $$ The reasonning is as follow:

  • You need at least $N-k$ red balls before the $k+1^{th}$ black balls. Hence the first $N$ students must have at most $k$ black balls. There may not be such a number of black balled students, this is why we have the $\min$ function in the sum. The quantity $M-N+k$ represents the remaining red balls after the mandatory $N-k$ we need.

  • For each of these configuration, you need to permute the remaining students. The ${M\choose N-k+j}$ factor those that.

  • There are obviously ${N+M \choose N}$ ordering of the student.


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.