2
$\begingroup$

This is a real life problem, which I'm turning into balls just to make it easier to understand.

Suppose balls can be numbered from 1 to 12.

Suppose I have 10 boxes. Each box has 3 distinct balls, distributed at random.

A valid combination is if I can find, from those 10 boxes and taking 1 ball from each, a combination where all balls have distinct numbers (i.e. there are (12,10) valid combinations).

Here are some examples, to make it more concrete:

  • Box 1 has (1,2,3), Box 2 has (2,3,4), Box 3 has (3,4,5)... Box 10 has (10,11,12). This is the best case scenario, I can easily make valid combinations such as (1,2,3,4,5,6,7,8,9,10); (1,2,3,..,9,11); and so on
  • Box 1 has (1,2,3), Box 2 has (1,2,3), Box 3 has (1,2,3), Box 4 has (1,2,3). This is the worst case scenario, as I can't find any valid combination. I will always have to repeat 1, 2 or 3.

I would like to know what is the probability of finding scenarios that yield valid combinations from such a setup. In other words - given a scenario of 10 box with 3 distinct balls in each, what is the probability that from those 10 boxes I can find at least one valid combination (it doesn't matter if there is more than 1 valid combination).

Here's a potential approach:

The universe of potential combinations: A = C(12,3)^10

The cases where numbers repeat and I get an invalid scenario:

B = C(12,9) * C(9,3)^10

Probability is then 1 - B/A.

$\endgroup$
7
  • $\begingroup$ Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or closed. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. $\endgroup$ Jan 21, 2021 at 10:28
  • $\begingroup$ Thanks for the reply; I think the question is precise (i.e. all info is there), and I don't have further thoughts on the problem (I'm really stuck on even how to approach it); I started to think I should even try the brute force approach, but I suppose there is an analytical solution to this problem (I'm really rusty at maths). $\endgroup$
    – dpp
    Jan 21, 2021 at 10:37
  • $\begingroup$ I do not think the problem is clearly state either. On one hand you say, there are balls numbered $1$ to $12$. Then you say $3$ distinct balls in each of the $10$ boxes. That makes it $30$ balls. On what basis, these $30$ balls are numbered? Random? $\endgroup$
    – Math Lover
    Jan 21, 2021 at 10:41
  • $\begingroup$ Yes, I mentioned distributed at random there; the only restriction is that within each box, the balls are distinct. $\endgroup$
    – dpp
    Jan 21, 2021 at 10:48
  • $\begingroup$ I added 2 examples for best and worst case; and I refined the question to the probability of finding scenarios that yield valid combinations. Thanks for the feedback! $\endgroup$
    – dpp
    Jan 21, 2021 at 10:57

1 Answer 1

1
$\begingroup$

Consider a simpler case: 4 boxes and balls numbered from 1 to 6. We still put 3 balls in each box. I have chosen this case, since it is possible to write out all combinations and check corresponding probabilities.

For each box, we now have $6\choose3$ possible combinations.

In the first box, we can select any ball, yielding a probability of 1. For the second box, we have two options to select a valid ball (i.e. a ball not selected previously):

  • A box without the ball that we already selected. The total number of possibilities for this case are ${1\choose0}{5\choose3}$. ${1\choose0}$ specifies the number of balls we select from the previously selected balls. ${5\choose3}$ specifies the number of combinations of choosing three balls from the remaining five that have not been selected previously. The probability of selecting a valid ball is 1, since the previously selected ball is not in the box.
  • A box with the ball that we already have selected. Out of the $6\choose3$ possibilities, ${1\choose1}{5\choose2}$ have the already selected ball. Selecting a valid ball has a probability of $\frac{2}{3}$.

Thus, selecting a valid ball from the second box is given by $\frac{1\times {1\choose0}{5\choose3} + \frac{2}{3}\times{1\choose1}{5\choose2}}{6\choose3} = \frac{5}{6}$.

For the third box, we have the following cases:

  • A box without the previously selected balls: ${2\choose0}{4\choose3}$ possibilities. The probability of selecting a valid ball is 1.
  • A box with one previously selected ball: ${2\choose1} {4\choose2}$. The probability of selecting a valid ball is $\frac{2}{3}$.
  • A box with two previously selected balls: ${2\choose2}{4\choose1}$ possibilities, with a probability of $\frac{1}{3}$ of not selecting a previously selected ball.

For the third box, the probability of selecting a valid ball is consequently: $\frac{1 \times {2\choose0}{4\choose3} + \frac{2}{3} \times {2\choose1} {4\choose2} + \frac{1}{3}\times {2\choose2}{4\choose1}}{6\choose3} = \frac{4}{6}$.

For the fourth box, we have the following cases:

  • No previously selected balls: ${3\choose0}{3\choose3}$ possibilities. We have a probability of 1 of selecting a valid ball.
  • One previously selected ball: ${3\choose1}{3\choose2}$. Corresponding probability is $\frac{2}{3}$.
  • Two previously selected balls: ${3\choose2}{3\choose1}$. Corresponding probability is $\frac{1}{3}$.
  • Three previously selected balls: ${3\choose3}{3\choose0}$. Corresponding probability is 0.

For the fourth box, the probability of selecting a valid ball is thus given by: $\frac{1 \times {3\choose0}{3\choose3} + \frac{2}{3}\times {3\choose1}{3\choose2} + \frac{1}{3} \times {3\choose2}{3\choose1} + 0 \times {3\choose3}{3\choose0}}{6\choose3} = \frac{3}{6}$.

We thus find the probability of valid combinations for this scenario as follows: $\text{P(selected balls are distinct)} = \frac{6}{6}\times\frac{5}{6}\times\frac{4}{6}\times\frac{3}{6} = \frac{\frac{6!}{(6-4)!}}{6^4}$.

This pattern also arises in your scenario. In your scenario, we find a probability of: $\text{P(Selected balls are all distinct)} = \frac{\frac{12!}{(12-10)!}}{12^{10}}\approx 0.003868$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .