Distributing black and white marbles...

**gusztav** · January 4th 2009, 07:40 AM

There are six identical white marbles and eight identical black marbles. In how many ways can we give these marbles to 3 boys, if every boy must get at least one marble, and we don't necessarily have to give them all of the marbles?

This problem should be solved using the inclusion-exclusion principle.

***

I tried to solve this by defining three sets $A_1, A_2, A_3$ where each set $A_i$ contains all the possible marble combinations (or sets of marbles) $i$ -th boy can get, and then counting the number of ordered triples $(x,y,z)$ where $x \in A_1, y \in A_2, z \in A_3$ . However - this approach is wrong, because with the sets thus defined it's possible to have a triplet $(x,y,z)$ representing the first boy getting e.g. 8 black marbles, second boy getting 7 black marbles and third boy 6 black marbles, which is not possible as there are only 8 black marbles...

So I'd be immensely grateful for any help/hints/insights you might have

**Laurent** · January 4th 2009, 10:46 AM

Originally Posted by gusztav

There are six identical white marbles and eight identical black marbles. In how many ways can we give these marbles to 3 boys, if every boy must get at least one marble, and we don't necessarily have to give them all of the marbles?

This problem should be solved using the inclusion-exclusion principle.

"Inclusion-exclusion" means counting too many ways of giving the marbles, and then substracting those that are irrelevant (and possibly iterating this process to find the number of irrelevant ways).

The idea in "counting too many ways" is to reduce to simpler combinatorics.

In your problem, you could first find in how many ways at most six white marbles can be given to 3 boys, if the boys may get any number of marbles (possibly 0). Then the same for 8 black ones.
At that moment, you should know in how many ways at most 6 white and 8 black marbles can be given to 3 boys, if the boys may get any number of marbles.

By doing this, we count a few cases too many: we need that each boy gets at least one marble, so we should substract the cases when (at least) a boy gets no marble. You should compute the number of such cases.

I let you try that. Don't hesitate asking for help if you're stuck.

**gusztav** · January 9th 2009, 06:52 AM

Originally Posted by Laurent

In your problem, you could first find in how many ways at most six white marbles can be given to 3 boys, if the boys may get any number of marbles (possibly 0). Then the same for 8 black ones.

OK, so I'll try:

In how many ways can we give at most six indistinguishable white marbles to three boys?

If we give them 0 marbles, there is only 1 way to do that.

If we are to give them 1 marble, there are 3 ways to give it to any of the three boys.

If we want to give 2 marbles to 3 boys, the number of ways to do that is equivalent to the number of ways in which we can distribute 2 indistinguishable balls among 3 distinguishable boxes, which is $\binom{3-1+2}{2}$ .

And, because the number of ways in which we can distribute k (indistinguishable) marbles among n (different) boys is $\binom{n-1+k}{k}$ , it finally follows that we can distribute 6 white marbles among 3 boys in $\sum_{k=0}^{6}\binom{3-1+k}{k}=\sum_{k=0}^{6}\binom{2+k}{k}=84$ ways (if I'm not mistaken).

Similarly, we can distribute 8 black marbles among the three boys in $\sum_{k=0}^{8}\binom{2+k}{k}=165$

Originally Posted by Laurent

At that moment, you should know in how many ways at most 6 white and 8 black marbles can be given to 3 boys, if the boys may get any number of marbles.

Would it be correct to say that the maximum number of ways we can distribute, first, at most six white marbles, and then, at most eight black marbles, is 84*165=13860 ?

If it is correct, then we have the following problem: we must ultimately find the number of ways of distributing 6 white and 8 black marbles to the 3 boys in such a way that every boy gets at least 1 marble (presumably, either black or white), but there is also the condition that we do not have to distribute all of the marbles we got.

Therefore, we must give away at least 3 marbles (either black or white) -so that every boy gets one- and at most all 14 marbles.

I know we should subtract some quantities from the total number of distributions (13860), but am not really sure how precisely to go about that...

Many thanks for any help!

**Laurent** · January 11th 2009, 05:29 AM

Originally Posted by gusztav

OK, so I'll try:

In how many ways can we give at most six indistinguishable white marbles to three boys?
(...)
it finally follows that we can distribute 6 white marbles among 3 boys in $\sum_{k=0}^{6}\binom{3-1+k}{k}=\sum_{k=0}^{6}\binom{2+k}{k}=84$ ways (if I'm not mistaken).

Similarly, we can distribute 8 black marbles among the three boys in $\sum_{k=0}^{8}\binom{2+k}{k}=165$

This is correct. This can also be obtained quicklier: Suppose we want the number of possibilities to give at most $n$ indistinguishable marbles to $p$ boys. This is easily seen to be equivalent to adding $p$ "sticks" to the sequence $1,\ldots,n$ : the sticks split the sequence according to the number of marbles given to the boys. For instance, if p=3 and n=4, "1|23||4" means giving 1 marble to the first boy, 2 to the second, and no marble to the third. "|||1234" means giving no marble to any boy. "1|2|3|4" means giving 1 to each of them. "1234|||" means giving four marbles to the first, and none to the others. Etc.
Now, we can compute directly the number of possibilities: this is the number of locations of the $p$ sticks among the $N+p$ positions ( $N$ for the numbers, $p$ for the sticks).
Finally, the number of ways to give at most $p$ marbles to $n$ boys is ${n+p\choose p}$ . You can check it gives the same answers as yours.

Would it be correct to say that the maximum number of ways we can distribute, first, at most six white marbles, and then, at most eight black marbles, is 84*165=13860 ?

Yes, it is. That was the point of this first computation: there is no correlation between the black and white marbles for the moment, so we just have to multiply the numbers of possibilities.

If it is correct, then we have the following problem: we must ultimately find the number of ways of distributing 6 white and 8 black marbles to the 3 boys in such a way that every boy gets at least 1 marble (presumably, either black or white), but there is also the condition that we do not have to distribute all of the marbles we got.

Therefore, we must give away at least 3 marbles (either black or white) -so that every boy gets one- and at most all 14 marbles.

I know we should subtract some quantities from the total number of distributions (13860), but am not really sure how precisely to go about that...

Like I wrote in my first post, 13860 is the number of possibilities where each boy gets any number of marbles, so you must substract the number of possibilities where (at least) a boy gets no marble. Then the remainder will be the number of possibilities where every boy gets at least one marble. And this is what we need.

So we must find how to give at most 6 white and 8 black marbles to 3 boys, in such a way that at least one of the boys gets no marble (of any colour).

This can be done by inclusion-exclusion again: as a summary, we want to distribute the marbles with the restriction $(\geq 1,\geq 1,\geq 1)$ . We can write schematically (the order of the indices is not important): $(\geq 1,\geq 1,\geq 1)=(\ast,\ast,\ast)-(0,\ast,\ast)+(0,0,\ast)-(0,0,0)$ where $\ast$ means " $\geq 0$ ". This can be described in words, like counting too many cases and substracting the superfluous terms, but this becomes somewhat painful to write...

In a more rigorous way, if $A_i$ is the set of the possibilities where the boy $i$ ( $\in\{1,2,3\}$ ) gets at least one marble, then we want the cardinality of $A=A_1\cap A_2\cap A_3$ . To that aim, we write, using inclusion-exclusion principle, and denoting by $\Omega$ the set of the possibilities without restriction (so that $|\Omega|=13860$ ) and by $A^c$ the complement of a set $A$ in $\Omega$ :
$|A| = |\Omega|-|A^c|=|\Omega|-|A_1^c\cup A_2^c\cup A_3^c|$
$=|\Omega| - (|A_1^c|+|A_2^c|+|A_3^c|)+(|A_1^c\cap A_2^c|+|A_1^c\cap A_3^c|+|A_2^c\cap A_3^c|)-|A_1^c\cap A_2^c\cap A_3^c|$
Due to the symmetry, the formula becomes:
$|A|=|\Omega| - 3 |A_1^c| + 3 |A_1^c\cap A_2^c | - |A_1^c\cap A_2^c\cap A_3^c|$ .
This is exactly what I wrote above with $\ast$ and $0$ : $A_1^c=(0,\ast,\ast)$ (the contrary to $A_1$ is: the first boy gets no marble), and so on.

So you are reduced to computing the cardinality of:
- first $A_1^c=(0,\ast,\ast)$ . This is just like $|\Omega|$ but with only 2 boys getting the marbles, so this is ${6+2\choose 2}{8+2\choose 2}$ .
- then $A_1^c\cap A_2^c=(0,0,\ast)$ . This is just giving marbles to only one boy, so this is ${6+1\choose 1}{8+1\choose 1}=7\times 9$ .
- finally $(A_1^c\cap A_2^c\cap A_3^c)=(0,0,0)$ . This is just giving no marble to the boys, so this is 1.

I assumed you knew the inclusion-exclusion formula; otherwise there must be good references on the internet. This is a generalization of $|A\cup B|=|A|+|B|-|A\cap B|$ to three (or more) subsets.

**gusztav** · January 11th 2009, 07:51 AM

Thanks a million, Laurent!

Your post has been most helpful and illuminating.

Thread: Distributing black and white marbles...

LinkBack

Thread Tools

Display

Distributing black and white marbles...

Distributing...

Similar Math Help Forum Discussions

Choosing 5 balls from 10 black, 20 white, 40 red.

A urn contain N white

Problem: the black and white pebbles

white noise/iid

colring strips of paper black and white

Search Tags