Printable View
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
OK think about it and give me an answer.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?
:o
32768
Hmm, it was some time ago I read discrete mathematics... but I'll try :).Quote:
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?
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 :).
Oops, forgot to attach the image :o
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)
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]
>> 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
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.
Sang Dang's answer is correct. I solved the problem without
reading it:)
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"
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.Quote:
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.
(3! / 2!) * 2 = 3! = 6
No it's not, as shown above!Quote:
Sang Dang's answer is correct. I solved the problem without
reading it.
When you try to solve this problem using combinations of letters, you don't take in account that:Quote:
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]
A B | C
Isn't the same as:
A | B C
(| separates the two columns)
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:Quote:
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.
3 * 2 * (2 choose 1) =
3 * 2 * (2! / (1! * (2 - 1)!)) =
3 * 2 * 2! =
3 * 2 * 2 =
12
Which isn't the correct answer...
Yes, your answer is correct.Quote:
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.
Totally missed that.
Hi everybody ...
I just came back from my trip... it is very nice to see all these answers... Thanx for everybody ...
I was in Getty Musiam , and I advice you all to visit it http://www.getty.edu it was a nice long tirp...
I will read your answers now, as I will add some more tomorrow , thanx for everybody.
I hope that you like this problem. (I can get you more if you want.)
thanx again
Your Solution is realy right , but in part three you need to div by 3! , because the problem in part III is selection , but in the first 2 part is P arranging ...Quote:
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
so the last answere would be like this
(8! / 4!) * 5 +
(8! / (2! * 3!)) * (5 * 4) +
(8! / (2! * 2! * 2!)*3!) * (5 * 4 * 3)
and that is it ....
thanx again.
I do the same thing in all 3 cases, so I don't see why you would also divide by 3! in the last case ???
8! is the 8 distributed books
(2! * 2! * 2!) is divided cause in each 2-book pile, the books can be arranged in 2 ways which doesn't matter, therefore divide by 2 three times.
(5 * 4 * 3) is the distribution of the book piles. The first pile can be placed in any of the five students. The second pile can be placed in any of the 4 remaining students. The last pile can be placed in any of the 3 remaining students.
Why do you divide by 3! ???
when I solve it in the class , I solve it in this way...
we have 5 students ... e1 , e2, ... e5
so we have
e1 + e2 + e3+ e4+ e5 = 8
ei is one one the student 1 =<ei =<5 and i>=1
g(x) = ( x + xpwr2 + .... + xpwr8)pwr5
= (x+( x pwr2)/2! + .... (x pwr8)/8!) pwr5
= ( ( e pwrx) -1) pwr5
= [e pwr(5x)] - [c(5,1) e pwr 4x] + ... -.... +[pc(5,4) e pwr x ]-1
= c(5,0) SEGMA 5 (x pwr 8) / 8! - c(5,1) SEGMA 4 (x pwr 4 )/4! +... -..... -1
= {SEGMA [ 5 pwr 8 - C(5,1) 4 pwr 8 + C(5,2) 3 pwr 8 - C(5,3) 2 pwr 8 + C(5,4) 1 pwr 8 ] x pwr8 / 8! }-1
A8 = 5 pwr8 - C(5,1) 4 pwr 8 + C(5,2) 3 pwr 8 - C(5,3) 2 pwr 8 + C(5,4) 1 pwr 8
count the answer, and once you have it , look at the last answer and devid it by 3! you will find that the resuts sound be the same.
as I told you ... the way that you solve it is more programming than what I did ( which is great , because you are a good programmer and you have a great future in that ) but you forgot that in the part III you need to select not to destribute ... and that is why you need to devid by 3!.
I hope that you understand my poor English.
Again. I would like to say ... that your way is a very computerizad way and ( I - should use it because I am a programmer - ) but you need to devid by 3! for the last part to get the right answer for your solution.
thanx again;)