Results 1 to 5 of 5

Math Help - Distributing black and white marbles...

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1

    Distributing black and white marbles...

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by gusztav View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1

    Distributing...

    Quote Originally Posted by Laurent View Post
    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

    Quote Originally Posted by Laurent View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by gusztav View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1
    Thanks a million, Laurent!

    Your post has been most helpful and illuminating.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Choosing 5 balls from 10 black, 20 white, 40 red.
    Posted in the Statistics Forum
    Replies: 4
    Last Post: June 11th 2011, 12:36 PM
  2. A urn contain N white
    Posted in the Statistics Forum
    Replies: 3
    Last Post: December 30th 2009, 08:17 PM
  3. Problem: the black and white pebbles
    Posted in the Math Puzzles Forum
    Replies: 2
    Last Post: May 6th 2009, 04:35 AM
  4. white noise/iid
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 2nd 2009, 05:56 PM
  5. colring strips of paper black and white
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: May 24th 2008, 04:44 PM

Search Tags


/mathhelpforum @mathhelpforum