Results 1 to 3 of 3

Math Help - number of ways to...

  1. #1
    Newbie sonictech's Avatar
    Joined
    Apr 2008
    Posts
    6

    number of ways to...

    Friend hit me with this problem today.

    There are three children with 20 fruit (10 peaches, 4 apples, and 6 pineapples).

    How many ways can the fruit be passed out so a child has at least one of any kind of fruit?

    My approach (which is wrong) is:

    nCr(9,7)*nCr(6,4)*nCr(8,6) + nCr(12,10)*nCr(3,1)*nCr(8,6) + nCr(12,10)*nCr(6,4)*nCr(5,3)

    (AKA, front load every kid 1 peach each, plus 1 apple each, plus 1 pineapple each)

    This will count the number of ways each child is guaranteed one fruit. However it is over counting because when I front load 3 of any kind of fruit to a kid it is also re-counted in the other group when i front load another 3 fruit. Any advice how I can take out the over count?

    PS: How do I use the awesome text so I don't have to use nCr?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1
    Quote Originally Posted by sonictech View Post
    Friend hit me with this problem today.

    There are three children with 20 fruit (10 peaches, 4 apples, and 6 pineapples).

    How many ways can the fruit be passed out so a child has at least one of any kind of fruit?
    OK, so there are 3 kids, and we want to distribute 10 peaches, 4 apples and 6 pineapples among them so that each one of them has at least one of every kind of fruit.
    As you correctly said, we can immediately give 1 peach, 1 apple and 1 pineapple to each of the 3 kids, and now we have 7 peaches, 1 apple and 3 pineapples.

    We can distribute the remaining apple in 3 ways: give it to the first kid, to the second or to the third one.

    In how many ways can we distribute r indistinguishable pieces of fruit to n kids, which are of course distinguishable? It can be shown that we can do it in \binom{n+r-1}{r} ways.

    So, we can distribute 7 remaining peaches to 3 kids in \binom{3+7-1}{7}=\binom{9}{7} ways, and we can distribute 3 remaining peaches to 3 kids in \binom{3+3-1}{3}=\binom{5}{3} ways.

    To find the total number of possible distributions, we multiply the above numbers to get that the final answer is 3 \cdot \binom{9}{7} \cdot \binom{5}{3}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by sonictech View Post
    There are three children with 20 fruit (10 peaches, 4 apples, and 6 pineapples). How many ways can the fruit be passed out so a child has at least one of any kind of fruit?
    I do not agree with the posted solution. That solution solves the question assuming that each child gets at least one of each kind of fruit. But the question is about each child getting at least one of any kind of fruit.

    Without any restrictions, there are {{10+3-1}\choose {10}}{{4+3-1}\choose {4}} {{6+3-1}\choose {6}} ways to give out the fruit.

    There are {{10+2-1}\choose {10}}{{4+2-1}\choose {4}} {{6+2-1}\choose {6}} ways to give out the fruit where child A gets no fruit whatsoever. Multiply by three to account for all three children.

    But now we have counted three cases twice: cases in which one child gets all the fruit.

    {{10+3-1}\choose {10}}{{4+3-1}\choose {4}} {{6+3-1}\choose {6}} - 3{{10+2-1}\choose {10}}{{4+2-1}\choose {4}} {{6+2-1}\choose {6}} + 3.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. number of ways ?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 14th 2011, 07:39 AM
  2. Number of Ways
    Posted in the Algebra Forum
    Replies: 6
    Last Post: May 13th 2010, 11:37 PM
  3. Number of ways
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 30th 2009, 03:08 PM
  4. Replies: 4
    Last Post: April 10th 2009, 02:03 PM
  5. Replies: 10
    Last Post: April 8th 2009, 11:56 AM

Search Tags


/mathhelpforum @mathhelpforum