Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have $2n$ balls labeled $1, 2, \ldots, 2n$, and two boxes, Box $1$ and Box $2$. I take $n$ of the balls at random without replacement and place them in the Box $1$. I take the remaining $n$ balls and place them in the Box $2$. I take the two smallest-numbered balls from each box. What is the probability that I end up with balls $1, 2, 3$ and $4$?

I'm trying this for small values of $n$ but am struggling to see the pattern. It is the probability $$ 1-P(\text{any 3 of balls 1,2,3,4 in the same box})-P(\text{all balls 1,2,3,4 in same box}) .$$ I'm having trouble finding the formula form here. Thanks!

Ok this part is more complicated. I have 3n balls and 3 boxes. I take n of the balls at random w/out replacement and place them in Box 1. I take n of the remaining 2n balls at random w/out replacement and put them in Box 2. I take the remaining n balls and put them in Box 3. I then take the smallest-numbered ball from each box and then the smallest-numbered ball among the balls remaining. What is the probability that I end up with balls 1,2,3,4?

So this time, it is okay to have two of Balls 1,2,3,4 in the one of boxes because he will take the smallest and come back for the next smallest. So I'm thinking that it is $\binom{4}{3}$ * ($\binom{3}{1}$$\binom{3n-3}{n-1}$)/$\binom{3n}{n}$ *($\binom{2}{1}$$\binom{2n-2}{n-1}$)/$\binom{2n}{n}$

I'm not sure if I need that first factor of $\binom{4}{3}$ though. Thanks!

share|cite|improve this question
Your analysis is right. The probability of a two-two split is (somewhat) easier to get at directly than via the "complement" method that you suggest, but that will work too. – André Nicolas Oct 5 '11 at 8:30
up vote 4 down vote accepted

Edit: Initially, we left out some details, since the question was homework. Now that time has passed, we add a few lines to give a complete answer.

When we take the two "smallest" balls from each box, we get the set $\{1,2,3,4\}$ precisely if $2$ of the $4$ smallest balls are in Box 1 (and therefore the other $2$ are in Box 2). So we need to find the probability that exactly $2$ of the $4$ smallest balls are in Box 1.

In deciding which balls go into Box 1, we have $\binom{2n}{n}$ choices. The problem specifies that these are all equally likely.

Now we count the number of choices in which exactly $2$ of our $4$ smallest balls end up in Box 1. Which $2$ of these $4$ will it be? These $2$ balls can be chosen from the $4$ in $\binom{4}{2}$ ways. For each way of deciding which of the $4$ smallest balls Box 1 will have, the remaining balls for Box 1 can be chosen in $\binom{2n-4}{n-2}$ ways.

Thus the number of "good" ways to choose the balls in Box 1 is equal to $\binom{4}{2}\binom{2n-4}{n-2}$. It follows that the required probability is $$\frac{\binom{4}{2}\binom{2n-4}{n-2}}{\binom{2n}{n}}.$$

After obtaining the above expression for the probability, we may want to "simplify." Or not. There is a lot of cancellation, since $(2n)!=(2n)(2n-1)(2n-2)(2n-30(2n-4)!$ and $n!=n(n-1)(n-2)!$. We end up with the following expression for the probability: $$\frac{3n(n-1)}{2(2n-1)(2n-3)}.$$

Comment: When I first read the problem, I thought that after the initial assignment of balls to Box 1 and Box 2, $2$ balls are chosen at random from each box, and we want the probability these give us the set $\{1,2,3,4\}$. That modified problem is not hard to solve once we have solved the original problem.

share|cite|improve this answer
any comments as to my solution is right or wrong @nicolas ? – Bhargav Oct 5 '11 at 7:56
@168335: When $n=2$ the probability is clearly $1$. That is not what your formula gives. – André Nicolas Oct 5 '11 at 8:11
Thank you! This makes total sense. It is much simpler than my complement analysis! – caligirl11 Oct 6 '11 at 4:50
You could use the same idea to find the probability none of the $4$ is in Box 1 (which is same as probability all $4$ are) and also the probability exactly one is in Box 1 (which is same as probability three are). The various expressions will have similar shape to my probability of exactly two, with minor differences of detail. Then you can add up, subtract from $1$. Same idea, more work. – André Nicolas Oct 6 '11 at 5:04
There is another part that I added that is more tricky. – caligirl11 Oct 6 '11 at 17:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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