Math Problem....

This is a discussion on Math Problem.... within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Hie everybody.... This Problem drive me very crasy; before I will write the problem, I will tell you the answer ...

  1. #1
    Registered User
    Join Date
    Apr 2002
    Posts
    249

    Question Math Problem....

    Hie everybody....

    This Problem drive me very crasy;

    before I will write the problem, I will tell you the answer is not as easy as I thought... it needs a lot of writing to get the right answer.

    and this is the problem
    Code:
      problem
    
    How many ways are there to distribute five identical penciles and
     eight different notebooks 
    amonge five poor math students,
     in case that each student getting at least 
    one pencil and one notebook?
    OK think about it and give me an answer.
    C++
    The best

  2. #2
    Registered User
    Join Date
    Sep 2002
    Posts
    137
    32768
    http://uk.geocities.com/ca_chorltonkids

  3. #3
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    problem

    How many ways are there to distribute five identical penciles and
    eight different notebooks
    amonge five poor math students,
    in case that each student getting at least
    one pencil and one notebook?
    Hmm, it was some time ago I read discrete mathematics... but I'll try .

    The 5 pencils can only be distributed in 1 way since they are identical, and have the same amount as the students.

    The placement of the eight books can be split into 3 parts, as shown in the figure.

    In part 1, the books can be distributed in 8! ways. But since the order of the books isn't important in column 5, you must divide by 4! so you get 8! / 4!. Also note that the fifth column can be in any of the five students, so multiply that by 5.
    You get (8! / 4!) * 5.

    In part 2, the books can be distributed in 8! ways. But the order of the books isn't important in the two last columns so you have to divide by 2! and 3!. You get 8! / (2! * 3!). The last two columns can be in any of the five students, so you have to multiply by 5 * 4 (the last column can be in any of the 5, the second last can be in any of the 5 minus the one the last one is in, giving 4).
    You get (8! / (2! * 3!)) * (5 * 4).

    In part 3, the books can be distributed in 8! ways. But the order of the books isn't important in the three last columns, so you have to divide by 2! three times. You get (8! / (2! * 2! * 2!)). The last three columns can be in any of the five students, so you have to multiply by 5 * 4 * 3.
    You get (8! / (2! * 2! * 2!)) * (5 * 4 * 3).

    Then sum all those:

    (8! / 4!) * 5 +
    (8! / (2! * 3!)) * (5 * 4) +
    (8! / (2! * 2! * 2!)) * (5 * 4 * 3)

    You might want to shorten that expression:
    8! * ((5 / 24) + (10 / 6) + (15 / 2))

    And the final result:
    378000

    There .
    Last edited by Magos; 11-02-2002 at 03:13 PM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  4. #4
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Oops, forgot to attach the image
    Attached Images Attached Images  
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  5. #5
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    I'd like to try:

    The pencils don't have to be considered.

    First, give every student one book each; this can be done in 8*7*6*5*4 = 6720 ways

    Then, distribute the remaining three books. Ways to do this: 5*5*5 = 125

    Total number of distributions : 6720 * 125 = 840000

    Not the same answer as Magos

    ***

    Lets try to simplify the problem; with three books and two students , the answer is 12 (use pen and paper).

    My algorithm gives:
    *Every student one book : 3*2 = 6 ways
    *Distribute the remaining 1 books : 2 ways
    *answer is 12, correct

    Magos' algorithm gives:
    (only one part to consider)
    *3! ways, but order of the books in column 2 isn't important, so divide with 2!
    *answer is 3!/2! = 3, wrong

    Is my solution better, or even correct? I'm not sure, I can't find the flaw in neither mine nor Magos' algorithm.


    (Edit) This is not correct... (/Edit)
    Last edited by Sang-drax; 11-03-2002 at 06:37 AM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  6. #6
    Registered User
    Join Date
    Sep 2002
    Posts
    137
    How many different combinations of letters are there in a one letter word?

    26 e+1 = 26

    two letter word = 26 e +2 = 676
    ...
    ...

    With 8 different books and only 5 students shouldn't that just therefore be
    8 e+5 = 32768

    I don't know, just a stab in the dark. If I'm wrong can someone explain why.

    [edit]
    I figured out a hole in my method, it doesn't take into account that fact that the books can't be used more than once.
    Shouldn't that therefore mean that there are less than 32768 though?
    Which would give a figure different to everyones
    [/edit]
    Last edited by crag2804; 11-02-2002 at 05:45 PM.
    http://uk.geocities.com/ca_chorltonkids

  7. #7
    Green Member Cshot's Avatar
    Join Date
    Jun 2002
    Posts
    892
    >> Total number of distributions : 6720 * 125 = 840000

    EDIT - I think you're right.

    EDIT#2 - Hehe, made me edit again. I knew my original reasoning was correct
    Maybe I should hit those math books again...nah
    Last edited by Cshot; 11-03-2002 at 11:22 PM.
    Try not.
    Do or do not.
    There is no try.

    - Master Yoda

  8. #8
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    I havn't done a problem like this in a long time, but here goes.

    Because each of the pencils is indentical they may effectivly
    be eliminated from the problem. Therefore
    8 * 7 * 6 * 5 * 4 * (5 choose 3)
    This follows because for the first student there are 8 books
    the next student 7 books to choose from. The final 3 aren't constrained so we have 5 choose 3.
    This equals 67200.

  9. #9
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Sang Dang's answer is correct. I solved the problem without
    reading it

  10. #10
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Sang-drax, there should only be 6 different ways to distribute 3 books to 2 students. Say you have a red, green, and blue notebook then the combos are:

    R GB
    GB R
    G BR
    BR G
    B RG
    RG B

    Your method counts "R GB" as being different than "R BG"

  11. #11
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Sang-drax
    Lets try to simplify the problem; with three books and two students , the answer is 12 (use pen and paper).

    My algorithm gives:
    *Every student one book : 3*2 = 6 ways
    *Distribute the remaining 1 books : 2 ways
    *answer is 12, correct

    Magos' algorithm gives:
    (only one part to consider)
    *3! ways, but order of the books in column 2 isn't important, so divide with 2!
    *answer is 3!/2! = 3, wrong

    Is my solution better, or even correct? I'm not sure, I can't find the flaw in neither mine nor Magos' algorithm.
    Sorry, but you can only distribute 3 books to 2 students in 6 ways, as shown in the picture below. And my algorithm gives that answer, not yours. You forgot to multiply by 2, since the "two-book-column" can be in any of the two students.
    (3! / 2!) * 2 = 3! = 6

    Sang Dang's answer is correct. I solved the problem without
    reading it.
    No it's not, as shown above!
    Attached Images Attached Images  
    Last edited by Magos; 11-03-2002 at 05:41 AM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  12. #12
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by crag2804
    How many different combinations of letters are there in a one letter word?

    26 e+1 = 26

    two letter word = 26 e +2 = 676
    ...
    ...

    With 8 different books and only 5 students shouldn't that just therefore be
    8 e+5 = 32768

    I don't know, just a stab in the dark. If I'm wrong can someone explain why.

    [edit]
    I figured out a hole in my method, it doesn't take into account that fact that the books can't be used more than once.
    Shouldn't that therefore mean that there are less than 32768 though?
    Which would give a figure different to everyones
    [/edit]
    When you try to solve this problem using combinations of letters, you don't take in account that:

    A B | C

    Isn't the same as:

    A | B C

    (| separates the two columns)
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  13. #13
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by Nick
    Therefore 8 * 7 * 6 * 5 * 4 * (5 choose 3)
    This follows because for the first student there are 8 books
    the next student 7 books to choose from. The final 3 aren't constrained so we have 5 choose 3.
    This equals 67200.
    If we take your algorithm and use it in the case with 2 students and three books (which we knows the answer of), you get:

    3 * 2 * (2 choose 1) =
    3 * 2 * (2! / (1! * (2 - 1)!)) =
    3 * 2 * 2! =
    3 * 2 * 2 =
    12

    Which isn't the correct answer...
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  14. #14
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Originally posted by Magos
    Sorry, but you can only distribute 3 books to 2 students in 6 ways, as shown in the picture below. And my algorithm gives that answer.
    Yes, your answer is correct.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  15. #15
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Totally missed that.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 10:22 AM
  2. Help!!c problem in math
    By feelsunny in forum Tech Board
    Replies: 2
    Last Post: 10-06-2007, 03:35 AM
  3. math problem
    By Chaplin27 in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 06-09-2005, 02:37 PM
  4. math problem
    By unixOZ in forum Linux Programming
    Replies: 4
    Last Post: 10-19-2002, 12:17 AM
  5. Little math problem
    By Thantos in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 10-27-2001, 07:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21