1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics question

  1. Jun 8, 2014 #1
    Hello Everyone,

    There is one interesting exercise in which it is asked to solve the following problem:

    In how many ways can we distribute 20 candies among 6 children so that the youngest gets at most 2 candies?

    This is my version of the solution:

    Case 1: youngest child gets no candies, thus we have to distribute the 20 candies among 5 children, so we have C(20+5-1, 5) = 42 504

    Case 2: youngest child gets one candy, thus we give him one candy, and then we have 19 candies to distribute between the other 5 children: C(19+5-1, 5) = 33 649

    Case 3: youngest child gets two candies, so we give him two, and then we have 18 candies to distribute among the other 5 children: C(18+5-1, 5) = 26 334

    And the total comes to 42 504 + 26 334 + 33 649 = 102 487 ways to distribute the candies.

    This is the instructor's version of the solution, whose answer matches the answer in the study guide:

    You have x1 + x2 + x3 + x4 + x5 + x6 = 20
    Nw we will discuss x1, consider y1=x1-i where i is 0, 1, or 2..

    So for i=0 we still have x1=y1 and then we still have x1 + x2 + x3 + x4 + x5 + x6 = 20 now I think we can consider x1 as x1=0 is a "choice".

    To understand my point if you consider x1=1 then using you thinking we will get to x2 + x3 + x4 + x5 + x6 =19 and the answer will be C(19+5-1,19)=C(23,19) however.

    If you consider i=1 so x1=y1+1 and then the answer will be C(19+6-1,16)=C(24,19), so 6 is always kept for all cases.

    My question is: which solution is correct?
  2. jcsd
  3. Jun 8, 2014 #2
    If the candies are distinct, then your solution is correct. On the other hand, if they are identical then the instructor's version is correct.
  4. Jun 8, 2014 #3
    Adithyan, I'm probably missing some important point. Let me explain.

    Here's the solution in the study guide:

    Case one, x1=0. The youngest child gets zero candies: x1+x2+x3+x4+x5+x6=20. Now, they say, in this case we have C(20+6-1, 20) = 53,130.

    But here's my view: in this equation, we have all six x's, representing all six children. So, we are calculating the number of ways 20 candies can be distributed among the six children, including the youngest child, because x1 can vary from 0 to 20. Shouldn't we exclude x1 altogether, if it represents the youngest child who gets 0 candies?

    Case two, the youngest child gets two candies. The study guide says that we must have y1+x2+x3+x4+x5+x6=19, where y1=x1-1.

    But in this case, aren't we distributing 19 candies among six children, as opposed to 19 candies which should be distributed among five children (because one candy has already been given to the youngest child)?

    Likewise for the third case.

    Thank you :)
  5. Jun 9, 2014 #4
    I agree with you. I think the solution is incorrect. As you have pointed out, all we have to do is make three cases (i.e, x1=0, x1=1 and x1=2) and distribute the remaining chocolates to the other five kids.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook