Combinatorics

This topic has expert replies
Newbie | Next Rank: 10 Posts
Posts: 2
Joined: Sun Jul 05, 2015 6:13 pm

Combinatorics

by Grothen » Sun Jul 05, 2015 6:16 pm
How can i distribute 16 apples among 4 children such that everyone gets at least 3 apples ?

Master | Next Rank: 500 Posts
Posts: 363
Joined: Sun Oct 17, 2010 3:24 pm
Thanked: 115 times
Followed by:3 members

by theCEO » Sun Jul 05, 2015 7:05 pm
Grothen wrote:How can i distribute 16 apples among 4 children such that everyone gets at least 3 apples ?
Hi Grothen,

If everyone has to have at least 3 apples, it means 3 x 4 = 12 apples should be distributed to the 4 children.
Therefore we are left with 16 - 12 = 4 apples to assign to the 4 children.

The rephrased question is "How can I distribute 4 apples among 4 children?"

4 apples can be broken down as follow:
1,1,1,1 - each child get one apple
1,1,2 - 2 children get 1 each and 1 child gets 4
2,2 - 2 children get 2 apples
3,1 - one child gets 3 apples and one child gets 1 apples
4 - one child gets 4 apples

Find all the possibilties for the choices above.

1,1,1,1 - each child get one apple : (4x3x2x1)/(4x3x2x1)=1 way
1,1,2 - 2 children get 1 each and 1 child gets 4 : (4x3x2)/(2*1)=12 ways
2,2 - 2 children get 2 apples : (4x3)/(2x1) = 6ways
3,1 - one child gets 3 apples and one child gets 1 apples : (4x3)=12 ways
4 - one child gets 4 apples = 4/1=4 ways

Add possibilities: 1+12+12+6+4 = 35ways

Newbie | Next Rank: 10 Posts
Posts: 2
Joined: Sun Jul 05, 2015 6:13 pm

by Grothen » Sun Jul 05, 2015 7:48 pm
Thanks for the explanation.I used the separator method after rephrasing the question. I get confused when i start analyzing the possibilities the way you did. What if i want to distribute n different objects among r groups such that everyone gets at least k objects.

User avatar
MBA Admissions Consultant
Posts: 2279
Joined: Fri Nov 11, 2011 7:51 am
Location: New York
Thanked: 660 times
Followed by:266 members
GMAT Score:770

by Jim@StratusPrep » Sat Jul 11, 2015 4:45 am
Just a side note, this is a bit beyond what the GMAT will test you on. The only reason I mention this is that you would be better served mastering foundational skills than studying random uses that won't be tested. It is a common problem that I see with GMAT hopefuls.
GMAT Answers provides a world class adaptive learning platform.
-- Push button course navigation to simplify planning
-- Daily assignments to fit your exam timeline
-- Organized review that is tailored based on your abiility
-- 1,000s of unique GMAT questions
-- 100s of handwritten 'digital flip books' for OG questions
-- 100% Free Trial and less than $20 per month after.
-- Free GMAT Quantitative Review

Image

Master | Next Rank: 500 Posts
Posts: 363
Joined: Sun Oct 17, 2010 3:24 pm
Thanked: 115 times
Followed by:3 members

by theCEO » Sat Jul 11, 2015 5:00 am
theCEO wrote:
Grothen wrote:How can i distribute 16 apples among 4 children such that everyone gets at least 3 apples ?
Hi Grothen,

If everyone has to have at least 3 apples, it means 3 x 4 = 12 apples should be distributed to the 4 children.
Therefore we are left with 16 - 12 = 4 apples to assign to the 4 children.

The rephrased question is "How can I distribute 4 apples among 4 children?"

4 apples can be broken down as follow:
1,1,1,1 - each child get one apple
1,1,2 - 2 children get 1 each and 1 child gets 4
2,2 - 2 children get 2 apples
3,1 - one child gets 3 apples and one child gets 1 apples
4 - one child gets 4 apples

Find all the possibilties for the choices above.

1,1,1,1 - each child get one apple : (4x3x2x1)/(4x3x2x1)=1 way
1,1,2 - 2 children get 1 each and 1 child gets 4 : (4x3x2)/(2*1)=12 ways
2,2 - 2 children get 2 apples : (4x3)/(2x1) = 6ways
3,1 - one child gets 3 apples and one child gets 1 apples : (4x3)=12 ways
4 - one child gets 4 apples = 4/1=4 ways

Add possibilities: 1+12+12+6+4 = 35ways
Here is an alternative way to solve the question "How can I distribute 4 apples among 4 children?"
We can use the formula [(n+r-1)C(r-1)] where n = number of appples, r = number of children

[(n+r-1)C(r-1)] = (4+4-1)C(4-1)= 7C3 = (7X6X5)/(3X2X1) = 35

Master | Next Rank: 500 Posts
Posts: 363
Joined: Sun Oct 17, 2010 3:24 pm
Thanked: 115 times
Followed by:3 members

by theCEO » Sat Jul 11, 2015 5:07 am
Grothen wrote:Thanks for the explanation.I used the separator method after rephrasing the question. I get confused when i start analyzing the possibilities the way you did. What if i want to distribute n different objects among r groups such that everyone gets at least k objects.
Another way to solve is to use the formula [((n-(r*k))+r-1)C(r-1)]

In the posted question this will be:
[((n-(r*k))+r-1) C (r-1)]
(16-4*3)+4-1 C (4-1)
7C3 = (7X6X5)/(3X2X1) = 35