How many ways can 5 prizes be distributed among 4 boys and 3 dividers?

[Crystal037]

Homework Statement

In how many ways can 5 prizes be distributed among 4 boys when everybody can take any number of prizes.

Relevant Equations

no. of prizes=5
no. of boys=4

the first boy has 6 ways,
either he wins 0 or 1 or 2 or 3 or 4 or 5 ways
According to the first boy, the second boy also has 0 or 1 or 2 or 3 or 4 or 5 chances
According to the first and second boy, the other boy also has 0 or 1 or 2 or 3 or 4 or 5 chances.
So, the answer should be 4(either of them gets all the prizes)+4C1*3C1(First gets 4 prizes and the second gets 1) +4C1*3C1(where First gets 3 prizes and the second gets 2)+4C2*2C1(2 of them gets 1 prize each and one gets only 3 prizes)+4C2*2C1(2 of them gets 2 prizes each and one gets only 1 prize)+4C1*3C3(where one gets 2 prizes and all the other get 1 each)
=4+12+12+12+12+4
=56
But the correct answer is 1024 ways.

 

[Stephen Tashi]

C1(First gets 4 prizes and the second gets 1)

Where do you account for the First boy getting 4 prizes and the third boy getting 1 prize?

It's simpler to think of each prize chosing a boy who gets it.

 

[Crystal037]

Since, I am putting 4C1, doesn't it include all the possibilities whether its second or third or fourth

 

[Stephen Tashi]

Since, I am putting 4C1, doesn't it include all the possibilities whether its second or third or fourth

Yes, your are correct that it does, if you are not thinking of "the second" boy as being the name of one particular boy and thinking of all prizes as being identical.

Your calculation is treating the boys as being distinct, but treating the prizes as being indistinct.
For example , the partition of 5 into 3,1,1 can arise from:

Tom gets a car, a truck, and a boat, Ed gets a cat, Fred gets a dog
or
Tom gets a car, at truck, and a boat, Ed gets a dog and Fred gets a cat.

A factor 3C2 does not count those situations as being distinct. It only counts the selection of two distinct boys that receive 1 price each. It doesn't make a distinction in which prize they receive.

 

[FactChecker]

It's simpler to think of each prize chosing a boy who gets it.

@Crystal037 , It's typical in these problems that the real trick is to find the approach that leads to the simplest counting of combinations. This hint is critical. Each prize can select between 4 people with no influence from the prior selections. Look at it that way and see what you get.

 

[Crystal037]

Yes, your are correct that it does, if you are not thinking of "the second" boy as being the name of one particular boy and thinking of all prizes as being identical.

Your calculation is treating the boys as being distinct, but treating the prizes as being indistinct.
For example , the partition of 5 into 3,1,1 can arise from:

Tom gets a car, a truck, and a boat, Ed gets a cat, Fred gets a dog
or
Tom gets a car, at truck, and a boat, Ed gets a dog and Fred gets a cat.

A factor 3C2 does not count those situations as being distinct. It only counts the selection of two distinct boys that receive 1 price each. It doesn't make a distinction in which prize they receive.

But in the question it isn't written anywhere if the prizes are distinct or not

 

[Crystal037]

@Crystal037 , It's typical in these problems that the real trick is to find the approach that leads to the simplest counting of combinations. This hint is critical. Each prize can select between 4 people with no influence from the prior selections. Look at it that way and see what you get.

I fif it that way and since each price have prize will have 4 ways so 5 prizes will have 4^5=1024 ways.
But can you please tell the faults or mistakes I made in the previous approach

 

[FactChecker]

But in the question it isn't written anywhere if the prizes are distinct or not

That is true and a good reason to say that the problem statement is not very clear. If you make some reasonable assumptions, you can match their stated answer. That tells you what they really meant in the problem. Then you can make a better problem statement if you want.

 

[FactChecker]

I fif it that way and since each price have prize will have 4 ways so 5 prizes will have 4^5=1024 ways.
But can you please tell the faults or mistakes I made in the previous approach

I looked at it initially and decided that your approach would be too complicated for me. I couldn't follow exactly what you were doing and I didn't see any mention at all of the 4th boy. I cannot comment on possible errors.

EDIT: I see that the 4'th boy is determined by the prior 3, so that is not an error in counting.

 

[Crystal037]

Then if I take all the prizes not distinct then my answer would be correct? What changes then I would have to apply in the answer 4^5 to get the same for non-distinct prizes. Is it 4^5/5!

 

[PeroK]

Then if I take all the prizes not distinct then my answer would be correct? What changes then I would have to apply in the answer 4^5 to get the same for non-distinct prizes. Is it 4^5/5!

You can't just divide by 5! because if you permute the prizes you don't get different solutions. E.g.

If the first boy gets prizes A and B and the others one prize each, C, D and E, then that is one distinct solution. But, if you swap A and B you get the same distinct solution.

Your calculation assumes these are different distinct solutions.

There is, however, a neat general trick for dividing $n$ indistinguishable objects between $k$ people.

Hint: consider the n people as "boxes" into which any number of objects can be put. Imagine $n -1$ dividers between the boxes. Every solution is an arrangement of $k$ objects and $n-1$ dividers

 

[Crystal037]

You can't just divide by 5! because if you permute the prizes you don't get different solutions. E.g.

If the first boy gets prizes A and B and the others one prize each, C, D and E, then that is one distinct solution. But, if you swap A and B you get the same distinct solution.

Your calculation assumes these are different distinct solutions.

There is, however, a neat general trick for dividing $n$ indistinguishable objects between $k$ people.

Hint: consider the n people as "boxes" into which any number of objects can be put. Imagine $n -1$ dividers between the boxes. Every solution is an arrangement of $k$ objects and $n-1$ dividers

But I am considering all the prizes to be same i.e A is same as B is same as C is same as D is same as E

 

[PeroK]

But I am considering all the prizes to be same i.e A is same as B is same as C is same as D is same as E

Yes, but you were dividing the number with distinct prizes by 5!. That's a mistake.

 

[Crystal037]

Yes, but you were dividing the number with distinct prizes by 5!. That's a mistake.

So by what factor should I divide if I am not considering the prizes to be distinct

 

[PeroK]

So by what factor should I divide if I am not considering the prizes to be distinct

It doesn't work that way. The answers are 56 and 1024, which isn't a multiple of the fomer.

Your 56 is the correct answer and I think others have checked your working. But, I gave you more than a hint of a quick, general way to do these problems in post #11.

 

[Crystal037]

How come you got the answer 56 and I didn't understood what the word divider is supposed to mean in post 11

 

[PeroK]

How come you got the answer 56 and I didn't understood what the word divider is supposed to mean in post 11

Suppose you want to divide 5 objects into 3 boxes say. Then every solution looks something like:

XX | XX | X

That's two objects in the first box, two in the second and one in the third. There is a 1-1 correspondence therefore between solutions and arrangements of 5 X's and 3 |'s (dividers). And you may know how to count the numbver of such arrangements.

 

[Stephen Tashi]

I didn't understood what the word divider is supposed to mean in post 11

Imagine we have 5 blocks with the symbol "|" printed on them. We also have 5 blocks with the symbol "P" written on them. We arrange the blocks in a row with the condition that the first and last block in the row must have a "|" on it.

This produces patterns like:
|PPP|P||P|
That pattern can be matched to the situation:
First boy gets 3 prizes, Second boy gets 1 prize, Third boy gets zero prizes, Fourth boy gets 1 prize.

You can think of the symbol "|" as a physical wall or "divider". The dividers create 4 rooms.

Instead of thinking about dividing indistinguishable prizes among distinguishable boys, think about arranging the blocks in a row.

One way to think about arranging the blocks is to imagine starting with the arrangement
"| - - - - - - - -|" where the "-" represents a space that is to be filed by a single block.

An arrangement is determined by selecting 3 of the 8 places to put a block with a "|" and filling the rest of the spaces with blocks that have a "P". We can select 3 of the distinguishable 8 spaces in 8C3 = 56 ways.

You can finds lots of articles on the internet that discuss visualizing combinatorial problems in terms of "balls in cells" or "stars and bars". In my browsing today, I didn't find any that I liked as explanations! A typical summary of results is:
http://cns-web.bu.edu/~eric/EC500/attachments/ON(2d)LINE(20)READINGS/ballsinboxe.pdf

 

[Crystal037]

So, the number of ways of distributing the prize
1) If the prizes are distinguishable:
no. of prizes, ways of choosing them WAYS OF ARRANGING THEM TOTAL
I II III IV
5 * 5C5 0 ------ 0 ----- 0 *4 4
4 * 5C4 1 *1C1 0 ----- 0 *4*3 60
3 * 5C3 1 *2C1 1 ------ 0 *4*3 240
3 * 5C3 2 ----- 0 ------ 0 *4*3 120
2 * 5C2 2 *3C2 1 ----- 0 *4*3 360
2 *5C2 1 *3C1 1 *2C1 1 *4 240
__________
1024
2) If the prizes were non-distinguishable:
then the combination factors will be divided, only arrangement factor will remain since the boys are still distinguishable.
4+ 12+12+12+12+4=56

 

[PeroK]

So, the number of ways of distributing the prize
1) If the prizes are distinguishable:
no. of prizes, ways of choosing them WAYS OF ARRANGING THEM TOTAL
I II III IV
5 * 5C5 0 ------ 0 ----- 0 *4 4
4 * 5C4 1 *1C1 0 ----- 0 *4*3 60
3 * 5C3 1 *2C1 1 ------ 0 *4*3 240
3 * 5C3 2 ----- 0 ------ 0 *4*3 120
2 * 5C2 2 *3C2 1 ----- 0 *4*3 360
2 *5C2 1 *3C1 1 *2C1 1 *4 240
__________
1024
2) If the prizes were non-distinguishable:
then the combination factors will be divided, only arrangement factor will remain since the boys are still distinguishable.
4+ 12+12+12+12+4=56

I would do:

For distinguishable prizes, each solution is defined by the boy who takes each prize. If we label the boys 1-4, then a typical solution is:

11431

Which means that the first, second and fifth prizes went to boy 1; the third prize to boy 4; and the fourth prize to boy 3.

This creates a 1-1 correspondence between solutions and five digit numbers composed of the digits 1-4.

And, there are $4^5 = 1024$ of those.

For the indistinguishable prizes I would do $\binom{8}{3} = 56$, using the technique as described above.

 

[Crystal037]

What do you mean a typical solution is 11431 and why did you take 8C3. There are no 8 prizes to choose 3 from. I did this to get 1024

 

[PeroK]

What do you mean a typical solution is 11431?

11431

Which means that the first, second and fifth prizes went to boy 1; the third prize to boy 4; and the fourth prize to boy 3.

 

[PeroK]

why did you take 8C3. There are no add prizes to choose 3 from

5 prizes, 4 boys, 3 dividers. Each solution is an arrangement of the prizes and dividers.