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

In summary: 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.
  • #1
Crystal037
167
7
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.
 
Physics news on Phys.org
  • #2
Crystal037 said:
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.
 
  • Like
Likes Delta2 and FactChecker
  • #3
Since, I am putting 4C1, doesn't it include all the possibilities whether its second or third or fourth
 
  • #4
Crystal037 said:
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.
 
  • #5
Stephen Tashi said:
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.
 
  • #6
Stephen Tashi said:
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
 
  • #7
FactChecker said:
@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
 
  • #8
Crystal037 said:
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.
 
  • #9
Crystal037 said:
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.
 
  • #10
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!
 
  • #11
Crystal037 said:
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
 
  • #12
PeroK said:
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
 
  • #13
Crystal037 said:
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.
 
  • #14
PeroK said:
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
 
  • #15
Crystal037 said:
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.
 
  • #16
How come you got the answer 56 and I didn't understood what the word divider is supposed to mean in post 11
 
  • #17
Crystal037 said:
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.
 
  • #18
Crystal037 said:
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
 
  • Like
Likes Crystal037 and PeroK
  • #19
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
 
  • #20
Crystal037 said:
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.
 
  • #21
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
IMG_20190916_191733.jpg
 
Last edited:
  • #22
Crystal037 said:
What do you mean a typical solution is 11431?

PeroK said:
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.
 
  • #23
Crystal037 said:
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.
 

What is the difference between permutations and combinations?

Permutations and combinations are both ways of arranging a set of objects. However, permutations involve arranging all the objects in a specific order, while combinations do not take into account the order of the objects.

How many ways can a set of objects be arranged using permutations or combinations?

The number of possible arrangements using permutations or combinations depends on the number of objects in the set. For permutations, the number of arrangements is equal to the factorial of the number of objects. For combinations, the number of arrangements is equal to the number of combinations of objects, which can be calculated using the choose formula.

When is it appropriate to use permutations versus combinations?

Permutations are used when the arrangement of objects is important, such as in a password or a combination lock. Combinations are used when the order of objects does not matter, such as in a lottery or a committee selection.

How can I calculate permutations and combinations using a calculator or computer program?

Most scientific calculators have a built-in function for calculating permutations and combinations. You can also use spreadsheet programs like Microsoft Excel or Google Sheets to easily calculate permutations and combinations. There are also many online calculators and computer programs specifically designed for these calculations.

Are there real-life applications of permutations and combinations?

Yes, permutations and combinations have many practical applications in fields such as statistics, computer science, and cryptography. They are used to analyze data, solve problems, and create secure systems, among other things.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
16
Views
494
Replies
27
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
945
  • Precalculus Mathematics Homework Help
Replies
4
Views
602
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
2
Replies
59
Views
4K
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
11
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
790
Back
Top