Combinatorics
This topic has expert replies
-
- Master | Next Rank: 500 Posts
- Posts: 363
- Joined: Sun Oct 17, 2010 3:24 pm
- Thanked: 115 times
- Followed by:3 members
Hi Grothen,Grothen wrote:How can i distribute 16 apples among 4 children such that everyone gets at least 3 apples ?
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
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.
- Jim@StratusPrep
- 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
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
-- 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
-
- Master | Next Rank: 500 Posts
- Posts: 363
- Joined: Sun Oct 17, 2010 3:24 pm
- Thanked: 115 times
- Followed by:3 members
Here is an alternative way to solve the question "How can I distribute 4 apples among 4 children?"theCEO wrote:Hi Grothen,Grothen wrote:How can i distribute 16 apples among 4 children such that everyone gets at least 3 apples ?
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
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
Another way to solve is to use the formula [((n-(r*k))+r-1)C(r-1)]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.
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