Two men, each placing one ball in five out of ten boxes

There are 10 boxes and each box can hold any number of balls. A man having 5 balls randomly puts one ball in each of the arbitrary chosen five boxes. Then another man having five balls again puts one ball in each of the arbitrary chosen five boxes. The probability that there are ball(s) in at least 8 boxes. Assuming all boxes and balls are identical. Both men can choose any arbitrary box.

My attempt:

I was really not able to pull through the solution. What I thought was to let the first man choose five boxes by $^{10}C_5$, and put the balls in those 5 boxes each. There is $1$ way to do that.

Now the second man comes and chooses his 5 boxes and put each ball in those 5 boxes. It can be done in $^{10}C_5 * 1$

Now these are the following ways the boxes can be filled: $$1 1 1 1 1 1 2200$$ $$1111111120$$ $$1111111111$$

Now I am not able to understand how to apply combinatorics and find the number of ways these conditions can happen. Please correct me if I was wrong in my attempt at the solution.

I will approach the problem $\require{enclose}\enclose{horizontalstrike}{\text{two}}$ three different ways, and show that the answer arrived at is the same in both ways. In doing so, I hope to highlight what is good and what is incorrect about the other posted answers.

Method 1:

We allow ourselves to imagine each box as having a label, yet the balls as continuing to be unlabelled. The people themselves can't see the labels, so this in no way affects the probabilities involved but it will be convenient for us in defining our sample space.

We take as our sample space the ways in which the balls are distributed after each person places their five balls into the boxes. Each way is indeed equiprobable by assumption. There are $\binom{10}{5}\binom{10}{5}$ number of ways of accomplishing this.

Each of these ways can be seen as a string of ten characters taken from $a$'s, $b$'s, $c$'s, and $x$'s such that the number of $a$'s plus the number of $c$'s is equal to five and the number of $b$'s is equal to the number of $a$'s. The locations of the $a$'s represent those boxes in which only the first man placed a ball, $b$'s represent the boxes in which only the second man placed a ball, $c$'s represent the boxes in which both men placed a ball, and $x$'s represent empty boxes. Again, the set of strings satisfying these conditions are in direct bijection with the outcomes in our sample space.

To count the number of "good" outcomes, i.e. those in which at least eight boxes have balls in them (i.e. at most two are empty), we look to count the strings as described above such that there are two, one, or zero $x$'s.

• Two $x$'s will imply that there are $3$ $a$'s, $3$ $b$'s, two $c$'s and two $x$'s. There are $\binom{10}{3,3,2,2}=\binom{10}{3}\binom{7}{3}\binom{4}{2}\binom{2}{2}=\frac{10!}{3!3!2!2!}$ number of ways in which this can occur. (note: this is in contradiction with both zzcnick's and anonymous's answers, they seem to have not taken into account that the person who placed each ball is relevant to the probability using this sample space)

• One $x$ will imply that there are $4$ $a$'s, $4$ $b$'s, one $c$ and one $x$. There are $\binom{10}{4,4,1,1}=\binom{10}{4}\binom{6}{4}\binom{2}{1}\binom{1}{1}=\frac{10!}{4!4!1!1!}$ number of ways this can occur.

• Zero $x$'s will imply that there are $5$ $a$'s, $5$ $b$'s, and zero $c$'s and $x$'s. There are $\binom{10}{5,5}=\binom{10}{5}$ number of ways in which this can occur.

Adding these favorable cases together and taking the ratio with the number of outcomes in our sample space we get the probability:

$$\dfrac{\binom{10}{3,3,2,2}+\binom{10}{4,4,1,1}+\binom{10}{5,5}}{\binom{10}{5}\binom{10}{5}}=\frac{31752}{63504}=\frac{1}{2}$$

Method 2:

Continuing from Morgan's observation, we may approach this via conditional probability. After the first person has picked his five boxes to place his balls, we may arbitrarily call those the first five boxes in our minds from left to right. The remaining empty boxes from left to right will be labeled as being the second five boxes. Again, the people with the balls can't see the labels on the boxes, so this in no way affects the probabilities, it is just a convenient way for us to organize our thoughts. With those as the first five boxes, the question is simply how many of the second person's balls go into the first five boxes versus the empty five boxes.

Our sample space then is described as the number of ways in which the people place the balls according to these labels. We can see that there are only $\binom{10}{5}$ ways, a much smaller sample space than before, but despite that this will still be an equiprobable sample space so we may use counting techniques.

We count how many favorable outcomes there are by again breaking into cases based on how many of the second person's balls were placed into already filled boxes.

• Only two were put into the first five boxes while three in the second five. There are $\binom{5}{2}\binom{5}{3}$ ways in which this occurs.

• Only one was put into the first five boxes while four in the second five. There are $\binom{5}{1}\binom{5}{4}$ ways in which this occurs.

• None were placed in the first five boxes. There are $\binom{5}{0}\binom{5}{5}$ ways in which this occurs.

Adding these favorable cases together and taking the ratio with the number of outcomes in our sample space we get the probability:

$$\dfrac{\binom{5}{2}\binom{5}{3}+\binom{5}{1}\binom{5}{4}+\binom{5}{0}\binom{5}{5}}{\binom{10}{5}} = \frac{100+25+1}{252}=\frac{126}{252}=\frac{1}{2}$$

Method 3: Very similar to method two, except we appeal to symmetry.

Recognize that the probability that at least eight boxes are filled is equivalent to the probability that at least three of the second person's balls are placed into empty boxes after the first person has placed his balls.

Recognize that this is equivalent to the probability that given five red boxes and five blue boxes that a person picking five boxes picks mostly red boxes. Recognize that this is then equivalent to the probability that he picks mostly blue boxes.

Recognize now that the probability of success is equal to the probability of failure, and thus the probability of success is equal to $\frac{1}{2}$ by the law of total probability.

• Thanks you so much sir! I understood well and thoroughly. Thank you once again. :) – Ishaan Nov 13 '16 at 5:52
• I'm confused as to why this received two downvotes with no explanations as to why. If it was because it was a large wall of text, I don't apologize for that. Scroll to whichever method you prefer and read only that one. Otherwise, I can't find anything worth changing. – JMoravitz Nov 14 '16 at 6:58

By way of enrichment here is an approach using generating functions. The generating function for this problem is

$$f(u, x, y) = \left(u + x+y+xy\right)^{10}.$$

The variable $u$ marks empty boxes. We get for the total number of outcomes

$$[x^5] [y^5] f(1, x, y) = [x^5] [y^5] (1+x)^{10} (1+y)^{10} \\ = {10\choose 5}^2 = 63504.$$

Now we are interested in the coefficients on $[u^0]$ (no empty box), $[u^1]$ (one empty box) and $[u^2]$ (two empty boxes). We extract these coefficients by writing

$$f(u, x, y) = \sum_{q=0}^{10} {10\choose q} u^q \left(-1 + (1+x)(1+y)\right)^{10-q}.$$

This yields for $[u^0]$

$$[x^5][y^5] \sum_{p=0}^{10} {10\choose p} (-1)^{10-p} (1+x)^p (1+y)^p \\ = \sum_{p=0}^{10} {10\choose p} (-1)^{10-p} {p\choose 5}^2 \\ = 252.$$

This is of course ${10\choose 5}$ as with no empty box every box contains one ball and hence it remains to choose the location of the five balls from the first round. Continuing we get for $[u^1]$

$$10 [x^5][y^5] \sum_{p=0}^{9} {9\choose p} (-1)^{9-p} (1+x)^p (1+y)^p \\ = 10 \sum_{p=0}^{9} {9\choose p} (-1)^{9-p} {p\choose 5}^2 \\ = 6300.$$

Finally we have for $[u^2]$

$$45 [x^5][y^5] \sum_{p=0}^{8} {8\choose p} (-1)^{8-p} (1+x)^p (1+y)^p \\ = 45 \sum_{p=0}^{8} {8\choose p} (-1)^{8-p} {p\choose 5}^2 \\ = 25200.$$

We thus have for the result

$$\frac{252+6300+25200}{63504} = \frac{1}{2}.$$

Addendum. We can ask about the number of configurations with $m$ empty boxes when we have two rounds of $n$ balls being distributed into $2n$ boxes. We obtain for the generating function

$$f(u, x, y) = \left(u + x+y+xy\right)^{2n}$$

which we write as

$$f(u, x, y) = \sum_{q=0}^{2n} {2n\choose q} u^q \left(-1 + (1+x)(1+y)\right)^{2n-q}.$$

We thus obtain for the coefficient on $[u^m]$

$${2n\choose m} [x^n][y^n] \sum_{p=0}^{2n-m} {2n-m\choose p} (-1)^{2n-m-p} (1+x)^p (1+y)^p \\ = {2n\choose m} \sum_{p=n}^{2n-m} {2n-m\choose p} (-1)^{2n-m-p} {p\choose n}^2.$$

Now to simplify this note that

$${2n-m\choose p} {p\choose n} = \frac{(2n-m)!}{(2n-m-p)! n! (p-n)!} = {2n-m\choose n} {n-m\choose p-n}$$

and we thus obtain

$${2n\choose m} {2n-m\choose n} \sum_{p=n}^{2n-m} {n-m\choose p-n} (-1)^{2n-m-p} {p\choose n} \\ = {2n\choose m} {2n-m\choose n} \sum_{p=0}^{n-m} {n-m\choose p} (-1)^{n-m-p} {p+n\choose n}.$$

Using the Egorychev method we have

$${p+n\choose n} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{p+n} \; dz$$

and we get for the sum

$${2n\choose m} {2n-m\choose n} (-1)^{n-m} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \sum_{p=0}^{n-m} {n-m\choose p} (-1)^p (1+z)^p \; dz \\ = {2n\choose m} {2n-m\choose n} (-1)^{n-m} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} (1-(1+z))^{n-m} \; dz \\ = {2n\choose m} {2n-m\choose n} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} z^{n-m} \; dz \\ = {2n\choose m} {2n-m\choose n} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{n} \; dz \\ = {2n\choose m} {2n-m\choose n} {n\choose m}.$$

We can confirm these with a simple Maple script up to about $n=7$ which goes as follows:

with(combinat);

GFENUM :=
proc(n)
option remember;
local res, c1, c2, empty, filled;

res := 0;

for c1 in choose(2*n, n) do
for c2 in choose(2*n, n) do
filled := {op(c1), op(c2)};
empty := 2*n-nops(filled);

res := res + u^empty;
od;
od;

res;
end;

GFX :=
proc(n)
m=0..n);
end;


E.g. we get for $n=6$ the OGF

$$924\,{u}^{6}+33264\,{u}^{5}+207900\,{u}^{4}+369600\,{u}^{3} \\+207900\,{u}^{2}+33264\,u+924.$$

Each of the three conditions you present represents a different way to fill the ten boxes with a different amount of balls so that at least 8 boxes have one ball.

In the first case, you have two boxes with two balls, two boxes with zero balls, and six boxes with one ball. If you labelled the ten boxes, you are then looking for the amount of ways to choose 2 boxes to have two balls, 2 boxes to have zero balls, and 6 boxes to have one ball. Solving for this case gives:

\begin{align*} {10\choose2}{10 - 2 \choose 2}{10 - (2 + 2) \choose 6} = {10\choose2}{8\choose2}{6\choose6} = \frac{10!}{2! * 2! * 6!} \end{align*}

Repeat this for your remaining two cases, and you will have all the ways to arrange the balls in the ten boxes so that you have at least 8 boxes with 1 ball.