3
$\begingroup$

I have a simple problem that a high school student could easily solve, but my high school maths classes are far...

Here is my problem:

  • I have 8 holes that I must fill with 6 balls. EDIT: Each hole can only contain one ball after this step.

    | | | | | | | | |

Obviously, 2 holes will be empty. Here is an example of a possible configuration:

| 0 | 0 | 0 |   | 0 |   | 0 | 0 |

There are $\dbinom{8}{6}$ possible permutations: 28 possibilities (if I'm right until here...).

  • Then, let say I randomly put 10 more balls in holes where there is already a ball. But a hole with only one ball is totally possible (see column 7). EDIT: the empty columns play no role.

Here is an example, starting from the previous configuration:

| 0 |   |   |   |   |   |   |   |
| 0 |   |   |   | 0 |   |   | 0 |
| 0 | 0 | 0 |   | 0 |   |   | 0 |
| 0 | 0 | 0 |   | 0 |   | 0 | 0 |

The total number of balls is 16. How many possible configurations are there ? My problem is that I must respect this two steps procedure: I first fill 6 holes out of 8, and then I fill the not empty holes with 10 more balls. No form of order has to be respected.

Could you give me a hand please ?

$\endgroup$
  • 1
    $\begingroup$ Not sure the rules are clear. In step one, is it ok to put all $6$ balls in a single hole? $\endgroup$ – lulu May 3 '16 at 12:38
  • 1
    $\begingroup$ Hint:- if two combinations differ in the first step, then they cannot become equal in the second. - in the second step: do the two empty columns play a role? Then compute the number of different configurations you can achieve, out of any combination you had in the first step... $\endgroup$ – b00n heT May 3 '16 at 12:39
  • $\begingroup$ Sorry, I didn't mention that. In the first step, a hole can only contain one ball. And also, no, the empty columns don't play a role. But I let them because I might want to repeat the 2 steps process once again, but that's for later. See my edits. $\endgroup$ – Rififi May 3 '16 at 13:15
3
$\begingroup$

This process is equivalent to: First choose k coordinates out of n (which can be done $C(n,k)$ ways). Then, add one ball to each of the $k$ originally chosen coordinates (which can be done $1$ way). Then, stick r balls into these k coordinates (which is the number of non-negative solutions to $x_1+\ldots+x_k = r$, which by stars and bars is $C(r+k-1,k-1)$; $x_i$ is the number of balls you're adding to the $i$-th selected coordinate, when you order the coordinates from left to right).

These steps are independent, so the number of ways to do this is the product of the ways to do each step, which is $C(n,k) C(r+k-1,k-1)$.

In your case, $n=8,k=6,r=10$.

$\endgroup$
  • $\begingroup$ Couldn't this also be done by stars and bars with 16 balls and 6 buckets, then just add in randomly the 2 empty buckets? $\endgroup$ – jdods May 3 '16 at 13:19
  • $\begingroup$ It seems crystal clear to me, thank you. One question thought: if a supplementary hole appears between step 1 and step 2, does the number of permutations equals to $C(n, k)C(r + k, k)$ ? $\endgroup$ – Rififi May 3 '16 at 13:33
  • $\begingroup$ What do you do with the supplementary hole? In the original formulation, you can switch steps 2 and 3 and get equivalent results. $\endgroup$ – Batman May 3 '16 at 13:59
  • $\begingroup$ This supplementary hole is empty, but this particular one can be filled like the 6 containing 1 ball. So after my step 1, I have 10 balls I can put into 7 holes: 6 of these 7 holes contain 1 ball, and the last hole is empty. $\endgroup$ – Rififi May 3 '16 at 16:41

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.