BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

combination sum - help please

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Master | Next Rank: 500 Posts
Posts: 231
Joined: Thu Apr 12, 2007 2:45 am
Thanked: 5 times
Followed by:1 members

combination sum - help please

by winnerhere » Wed Aug 26, 2009 2:14 am
How many ways can 5 distinct donuts be distributed to 3 guys such that each guy gets atleast one donut.

P.S: For similar donuts we can use x+y+z=5 and solve it(4c2) - here it is distinct donuts.
Top
Source: — Problem Solving |
Senior | Next Rank: 100 Posts
Posts: 73
Joined: Tue Aug 11, 2009 2:30 am
Thanked: 2 times
GMAT Score:720

by shanrizvi » Wed Aug 26, 2009 6:16 am
I read a similar question somewhere else. What I don't understand is how it makes a difference if the doughnut is similar or distinct?

What difference would it make? The question doesn't give us any information about the type of doughnuts or whether each guy must have a certain type. Distinct or similar, the question says that each guy must get at least one doughnut. The solution will be the same.

Imagine you have 6 doughnuts of different types in front of you and you have to split them among 3 people in such a way that each get at least one. Unless they have preferences, the fact that the doughnuts are distinct won't matter as long as everyone gets at least one doughnut. Can anyone correct me if I am wrong?
Top
Senior | Next Rank: 100 Posts
Posts: 73
Joined: Tue Aug 11, 2009 2:30 am
Thanked: 2 times
GMAT Score:720

by shanrizvi » Wed Aug 26, 2009 6:22 am
Sorry. I think I get your point now.
I think it will be 4C2*5!
Top
Senior | Next Rank: 100 Posts
Posts: 65
Joined: Fri Jul 24, 2009 11:47 am
Thanked: 5 times

by rish » Wed Aug 26, 2009 7:41 am
shanrizvi wrote:Sorry. I think I get your point now.
I think it will be 4C2*5!
Can you please explain ?
Top
Senior | Next Rank: 100 Posts
Posts: 64
Joined: Sat Aug 01, 2009 3:13 am
Thanked: 5 times
Followed by:1 members
GMAT Score:740

by mohitsharda » Wed Aug 26, 2009 9:51 am
rish wrote:
shanrizvi wrote:Sorry. I think I get your point now.
I think it will be 4C2*5!
Can you please explain ?
When the objects are distinct, then the relative placement (or distribution in this case) will matter.
eg. five mangoes a,b,c,d,e... distribute between two people P and Q.
case1: P gets a,b and Q gets c,d,e.
case2: P gets a,c and Q gets b,d,e.
These are 2 different cases.

If the objects are similar, then the relative placement doesnt matter.
Eg. five similar mangoes a,a,a,a,a... two people P and Q:-
case1: P gets a,a and Q gets a,a,a
case2: P gets a,a and Q gets a,a,a

These are same... as all are similar and cannot be distinguished.
MS
Top
Master | Next Rank: 500 Posts
Posts: 231
Joined: Thu Apr 12, 2007 2:45 am
Thanked: 5 times
Followed by:1 members

by winnerhere » Thu Aug 27, 2009 11:28 pm
shanrizwi,

there is flaw in your logic.First let me explain that and then I will get into the right solution

donut1 donut2 donut3 donut4 donut5

donut2 donut1 donut3 donut4 donut5

there are different arrangements.

Now when i split it like for three persons

(donut1 donut2) (donut3 donut4) (donut5)

(donut2 donut1) (donut3 donut4) (donut5)

U can find that it they are not unique solutions.

Solution :

3 persons can be given 5 donuts in 2 ways

case 1:
1 2 2 (this can be arranged in three ways - 122,221,212)

case2:
1 1 3 (similarly 113,131,311)

Now we can use normal permutation method

case 1:

5c1 * 4c2 * 2c2 * 3= 90 ways

5c1 * 4c1 * 3c3 * 3 = 60 ways

so total 150 ways
Top
Post new topic Post Reply
• Page 1 of 1