1. Not finding help here? Sign up for a free 30min 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 - can't really identify the problem

  1. Jan 6, 2012 #1
    1. The problem statement, all variables and given/known data
    In how many ways can 24 cans of Fanta and 24 cans of Cola be distributed among five thirsty students so that each student may
    (a) at least two cans of each variety? (2p)
    (b) at least two cans of a variety, at least three cans of the other variety? (3p)


    2. Relevant equations



    3. The attempt at a solution
    I have a hard time understanding what kind of combinatorics problem it is.

    2 types of cans confuses me since I can't figure out how to formulate it as a generating function problem.

    If it was 48 cans of the same and everyone should have at least 2 I could do:
    c1 + c2 +c3 + c4 + c5 = 48, where c1=c2=c3=c4=c5=(x^2+x^3+...+x^n)

    Using normal combinatorics seems impossibly hard if I'm not missing something obvious.

    I also thought maybe I could give everyone 2 of each first:
    (24 nCr 2) * (24 nCr 2) * (22 nCr 2) * (22 nCr 2) down to 16 = A but then what about the rest?
     
    Last edited: Jan 6, 2012
  2. jcsd
  3. Jan 6, 2012 #2

    ehild

    User Avatar
    Homework Helper
    Gold Member

    This problem is kind of combinations with repetition, but more complicated. According to the usual scheme, imagine that 5 boxes lined up represent the students and you need to distribute first one kind of cans and then the other kind.
    In case a., each students need to have two cans of each kind, you put those four cans into each box, and then you have 14 cans of both Cola and Fanta to be distributed.

    Can you answer question a now?


    ehild
     
  4. Jan 7, 2012 #3
    I thought that at first but then I wasn't sure if how I distributed them mattered or not.

    But the rest still seems very complicated.

    I could give the first student 28 cans and the rest 0 then 14 of one, 13 of the other or 13 of one and 14 of the other and one of the others get one and the rest none and so on.

    Maybe I can put this as some sort of sums of products?
     
  5. Jan 7, 2012 #4
    If I first hand out two of each kind to everyone then I have 2*14 left.

    Then I can distribute the rest like this:

    5^14 * 5^14 = 5^28 = approx 3.73*10^19

    Correct?
     
  6. Jan 7, 2012 #5

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Imagine you have 5 boxes aligned on a shelf and you put cans of Cola into the boxes. The boxes (or rather the right walls of the boxes) represent the students, A, B, C, D, E. I draw only seven cans and the question is how many arrangement of the cans exist among the boxes, I mean, among the students. I show two such arrangements. In the first case student A gets 1 can of Cola, student B gets 2 cans, C:3, D:0, E: 1. In the second case it is: A: 1, B:0 C:4, D:1, E:1.
    Look at the picture: You see two different sequences - permutations - of 5 blue lines and 7 red dots. The last element is always a blue line. So you permute 4 lines and 7 dots. How many permutations are possible? The dots are all equivalent and so are the lines.
    When you distributed the cans of Cole, you do the same with Fanta....

    ehild

    .
     

    Attached Files:

  7. Jan 7, 2012 #6

    ehild

    User Avatar
    Homework Helper
    Gold Member

    No, you have only 14 cans of one kind. If you gave 3 cans to one student, the next one can not have more then 11, and if he gets 11, the others have zero.

    ehild
     
  8. Jan 7, 2012 #7
    so (5+14-1 nCr 5)^2?
     
  9. Jan 7, 2012 #8
    If I read the problem correctly, you end up giving all 24 cans to the students.

    Why not just count the ways this can be done?

    first you must hand two cans to each, as they must receive at least two cans.

    Then figure out how to distribute the remaining 18 among three students.

    label them 1, 2 and 3.

    1 gets zero, figure how many ways 2 and 3 can be given the eighteen.
    1 gets one, figure how many ways 2 and 3 can get the seventeen.

    keep going..

    and going..

    until ..

    1 gets eighteen cans, figure out how many ways 2 and three can get zero cans.

    it's not really that hard to find the total number. After a few terms you may see a pattern.

    Add all the ways up. That takes care of the distribution of the fanta. Then do the same thing for the distribution of coke.

    The events between distribution of coke and distribution of fanta are disjoint. What rule would you then use?
     
  10. Jan 7, 2012 #9

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Almost correct. Check it with 5 students and 1 can.

    ehild
     
    Last edited: Jan 7, 2012
  11. Jan 7, 2012 #10

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Read the problem carefully... there are five students, and all of them get at least two cans of each variety.

    ehild
     
  12. Jan 7, 2012 #11
    I don't get it. (5+1-1 nCr 5) = 1, I assume that's not how you mean? But I don't get what you mean since (I assume) all cans must always be distributed.
     
  13. Jan 7, 2012 #12

    ehild

    User Avatar
    Homework Helper
    Gold Member

    I mean an other problem with one can of Cola, just to check your formula. You can distribute the single can five ways among the students. You need to use the formula (5+1-1 nCr4 )= 5!/(4! 1!) =5

    In the original problem, you have the permutations of 14+5-1 elements, 14 red dots and 5-1 =4 blue lines. All the red dots are indistinguishable and so are the blue lines.


    ehild
     
    Last edited: Jan 7, 2012
  14. Jan 8, 2012 #13
    Binomial[5 + 14 - 1 , 5-1]^2 = 9363600 ?
     
  15. Jan 8, 2012 #14

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Correct. And I hope it is the answer for question a.

    ehild
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics - can't really identify the problem
  1. Combinatorics problem (Replies: 7)

  2. Combinatorics problem (Replies: 7)

  3. Combinatorics problem (Replies: 2)

  4. Combinatorics problems (Replies: 8)

Loading...