Let's say we have to divide 16 prizes among 3 boys such that each boy gets at least one prize i.e x+y+z =16, where x, y and z are positive integers.
Imagine 16 prizes placed one besides the other. Now we have 15 gaps in between them and to divide this into 3 parts we nee d to select any 2 two gaps from the available 15 gaps which can be done in 15C2 ways = 105 ways.
Now in the given question x, y and z are non-negative which mean a boy can recieve any number of prizes i.e 0 is also allowed. Imagining as in the above case we will have 18 (15+3)gaps from which we need to select 2 gaps which can be done in 18C2 = 153 ways.
So in general....
The number of solutions of the equation x1+x2+--------+xr = n, where x1,x2,...xr belongs to positive integers = (n-1)C(r-1)
The number of solutions of the equation x1+x2+--------+xr = n, where x1,x2,...xr belongs to non-negative integers = (n+r-1)C(r-1)
How many non – negative integral solutions are possible?
This topic has expert replies
Source: Beat The GMAT — Problem Solving |
-
sureshbala
- Master | Next Rank: 500 Posts
- Posts: 319
- Joined: Wed Feb 04, 2009 10:32 am
- Location: Delhi
- Thanked: 84 times
- Followed by:9 members
sureshbala wrote:Let's say we have to divide 16 prizes among 3 boys such that each boy gets at least one prize i.e x+y+z =16, where x, y and z are positive integers.
Imagine 16 prizes placed one besides the other. Now we have 15 gaps in between them and to divide this into 3 parts we nee d to select any 2 two gaps from the available 15 gaps which can be done in 15C2 ways = 105 ways.
Now in the given question x, y and z are non-negative which mean a boy can recieve any number of prizes i.e 0 is also allowed. Imagining as in the above case we will have 18 (15+3)gaps from which we need to select 2 gaps which can be done in 18C2 = 153 ways.
So in general....
The number of solutions of the equation x1+x2+--------+xr = n, where x1,x2,...xr belongs to positive integers = (n-1)C(r-1)
The number of solutions of the equation x1+x2+--------+xr = n, where x1,x2,...xr belongs to non-negative integers = (n+r-1)C(r-1)
you said there will be 15+3=18 gaps......where did these 3 gaps come from?....i can guess that if you add zero gift beside 1st gift then you get 16 gaps...and 2 on the extreme ends right??
then if the question had 4 variables instead of 3....like....x1+x2+x3+x4 = 16 then what?......number of gaps should be 19.....but where did these 4 extra gaps come from?....(3 can be explained as above...but what about the extra 1?)
-
GMATGuruNY
- GMAT Instructor
- Posts: 15539
- Joined: Tue May 25, 2010 12:04 pm
- Location: New York, NY
- Thanked: 13060 times
- Followed by:1906 members
- GMAT Score:790
This problem is the same as the following:Vemuri wrote:How many non � negative integral solutions are possible for the given equation?
x + y + z = 16
Ans: 153
How many ways can 16 identical chocolates be distributed among three children X, Y and Z?
Use the SEPARATOR method.
16 identical chocolates are to be separated into -- at most -- 3 groupings.
Thus, we need 16 chocolates and two separators:
OOOO|OOOOOO|OOOOOO
Each arrangement of the elements above represents one way to distribute the 16 chocolates among three children X, Y and Z:
OOOO|OOOOOO|OOOOOO = X gets 4 chocolates, Y gets 6 chocolates, Z gets 6 chocolates.
OOOOOOOO||OOOOOOOO = X gets 8 chocolates, Y gets 0 chocolates, Z gets 8 chocolates.
OOOOOOOOOOOOOOOO|| = X gets all 16 chocolates.
And so on.
To count all of the possible distributions, we simply need to count the number of ways to arrange the 18 elements above (the 16 identical chocolates and the two identical separators).
The number of ways to arrange 18 elements = 18!.
But when an arrangement includes identical elements, we must divide by the number of ways to arrange the identical elements.
The reason:
When the identical elements swap positions, the arrangement doesn't change, reducing the total number of unique arrangements.
Thus, we must divide by 16! (the number of ways to arrange the 16 identical chocolates) and 2! (the number of ways to arrange the 2 identical separators):
18!/(16! 2!) = 153.
Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.
As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.
For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.
As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.
For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3
-
ani781
- Master | Next Rank: 500 Posts
- Posts: 141
- Joined: Fri Jun 24, 2011 4:35 am
- Location: Edison
- Thanked: 12 times
- Followed by:1 members
Hi Mitch,
What does this mean exactly ?
How many non � negative integral solutions are possible for the given equation?
x + y + z = 16
I understand the way to tackle this problem now, but am not sure aabout the question... doesn't this ask to make sure x/y/z should be non negative ?
OKAY, I got it ... means that x/y/z can be 0 also... Thanka!
What does this mean exactly ?
How many non � negative integral solutions are possible for the given equation?
x + y + z = 16
I understand the way to tackle this problem now, but am not sure aabout the question... doesn't this ask to make sure x/y/z should be non negative ?
OKAY, I got it ... means that x/y/z can be 0 also... Thanka!
