Problem Solving

smanstar wrote:1. a+b+c = 20
no of positive integral solution if a>b>c ?
2 . a+b+c <= 20
no of positive integral solution ?

Hi, there. I'm happy to share my 2¢ on this.

First, just to be clear, this is NOT a possible GMAT question. This involves a lot of tedious listing out of possibilities --- there's really no elegant way to shoot directly to an answer. Almost all real GMAT Quant questions will have something elegant about them --- if you adopt the right perspective, you can shoot to the answer.
I will say: if you have any practice in Kakuro, you may find that helpful in this problem.

I will solve the first questions, and by demonstrating this, it should be clear how to get the answer to the second.

Highest number = 17
sum of the two lowest numbers = 3, which can happen in 1 way: {1, 2}

Highest number = 16
sum of the two lowest numbers = 4, which can happen in 1 way: {1, 3}

Highest number = 15
sum of the two lowest numbers = 5, which can happen in 2 ways: {1, 4} & {2, 3}

Highest number = 14
sum of the two lowest numbers = 6, which can happen in 2 ways: {1, 5} & {2, 4}

Highest number = 13
sum of the two lowest numbers = 7, which can happen in 3 ways: {1, 6} & {2, 5} & {3, 4}

Highest number = 12
sum of the two lowest numbers = 8, which can happen in 3 ways: {1, 7} & {2, 6} & {3, 5}

Highest number = 11
sum of the two lowest numbers = 9, which can happen in 4 ways: {1, 8} & {2, 7} & {3, 6} & {4, 5}

Highest number = 10
sum of the two lowest numbers = 10, which can happen in 4 ways: {1, 9} & {2, 8} & {3, 7} & {4, 6}

Highest number = 9
sum of the two lowest numbers = 11,
If both lower numbers are less than 9, this can happen in 3 ways: {3, 8} & {4, 7} & {5, 6}

Highest number = 8
sum of the two lowest numbers = 12,
If both lower numbers are less than 8, this can happen in 1 way: {5, 7}

Total number of combinations = 1+1+2+2+3+3+4+4+3+1 = 24

I won't calculate an answer for #2 right now, but the way I would go about it --- starting at the low end (lowest pair = 3, then 4 then 5, ...) for each individual pair --- say the pair {2,3), then the highest number could be anything from 4 (one above the higher number of the pair) to 15 (the number which makes the sum equal to 20). For that pair, {2, 3}, there are 12 possibilities for the highest number, and thus 12 possible triplets that meet the condition. That is an example of how I would precede: you would have to count that way for each pair, until, again, you got up to the {5, 7, 8} triplet.

Does all this make sense?

Mike

smanstar wrote:Thanks Mike for the explanation. Well for the second part I got the solution as

a+b+c+d=21 ( where d is a dummy variable and can take natural number values )

no of integral solution = 20C4 = 29070 ways

Dear smanstar,
With all due respect, I believe that is not correct --- it way over estimates. You cannot pick any numbers from 1 - 20 --- for example, if you picked the combination {13, 16, 18, 19} --- a combination allowed by the 20C4 procedure ---- then any three of those would have a sum much larger than 20. I guarantee there is absolutely no "one step" procedure that will answer this second question. It is a very long tedious calculation, through which I am loathe to go. I would take dozens of steps. No formula, no magic use of nCr is going to produce the answer.

Does that make sense?
Mike

There is a way to answer both questions without listing possibilities exhaustively, though it's well beyond what you'd ever need to do on the GMAT. If you're preparing for the GMAT, you don't need to read or understand anything below. But if you're interested in how to solve these problems:

First imagine you have 20 donuts:

O O O O O O O O O O O O O O O O O O O O

Now if we stick two partitions in the 19 spaces between the donuts, that amounts to finding three numbers that will give us a sum of 20. So for example, if we divide up the donuts as follows:

O O | O O O O O O O O O | O O O O O O O O O

then counting donuts in each region, we get 2 + 9 + 9 = 20. Since there are 19 spaces between the donuts, there are 19C2 = 171 ways to find the three positive integers a, b, c to give us a sum of 20.

Now we don't want to count nearly all of those possibilities, since we need a > b > c to be true. First, we need to rule out all of the ways two numbers could be exactly equal. Suppose a = b. Then we have 9 choices for a and b (they can be anything from 1 to 9). So if a=b, there are 9 ways to choose numbers so that a+b+c = 20. But we could also have a=c, or b=c, so there will be 3*9 = 27 to choose two equal numbers and one different number that make a+b+c = 20. We don't want to count those, so we have 171 - 27 = 144 possibilities left.

Finally, those possibilities are all of the ways to add three numbers a, b and c to get 20. We only want to count the ways when a, b and c are in decreasing order. There are 3! = 6 different orders you can put a, b and c in, and only 1 of those orders is decreasing, so in only 1/6 of the ways we've counted are a, b and c in decreasing order. So the answer is 144/6 = 24.

The second question is also far too hard for the GMAT, but if you look back at the first step in the solution above, where I divided up the donuts, you can use the same method to answer the question. Fortunately we don't need a, b and c to be in any particular order in the second question. So if we want a+b+c to be exactly equal to 20, the number of choices we can make is 19C2, as I explained above. Similarly, if we need a sum of exactly 19, the number of choices would be 18C2, and so on. So the answer is just:

2C2 + 3C2 + 4C2 + 5C2 + ... + 18C2 + 19C2.

That's a messy calculation unless you know some math that you would absolutely never need to know on the GMAT. Each of the terms in the sum is what is known as a 'triangular number', and there's a formula to find the sum triangular numbers; the sum of the first n triangular numbers is (n+2)C(3) = (n+2)(n+1)(n)/6. We've written the first 18 triangular numbers down (2C2 is the first triangular number, so 19C2 is the 18th), so the sum of the above is 20*19*18/6 = 1140.

Ian Stewart wrote: The second question is also far too hard for the GMAT, but if you look back at the first step in the solution above, where I divided up the donuts, you can use the same method to answer the question. Fortunately we don't need a, b and c to be in any particular order in the second question. So if we want a+b+c to be exactly equal to 20, the number of choices we can make is 19C2, as I explained above. Similarly, if we need a sum of exactly 19, the number of choices would be 18C2, and so on. So the answer is just:

2C2 + 3C2 + 4C2 + 5C2 + ... + 18C2 + 19C2.

That's a messy calculation unless you know some math that you would absolutely never need to know on the GMAT. Each of the terms in the sum is what is known as a 'triangular number', and there's a formula to find the sum triangular numbers; the sum of the first n triangular numbers is (n+2)C(3) = (n+2)(n+1)(n)/6. We've written the first 18 triangular numbers down (2C2 is the first triangular number, so 19C2 is the 18th), so the sum of the above is 20*19*18/6 = 1140.

I have a question for Ian. First, though, let me make clear to all readers: everything we are discussing is well beyond GMAT math. By all means, read and ask questions if you are interested, but please do not think you need to know any of this for the GMAT.

Ian ---
First of all, I want to compliment you on a very elegant approach. You dispatched with the first question much more efficiently than did I.

I have some questions about the second question --- it's true that, in the second question, we no longer have the requirement that a > b > c, so we now can have repeated values {e.g. 1 + 1 + 4 = 6, 2 + 2 + 2 = 6, etc.) But, presumably, we still are looking for combinations, and therefore we would not count {1 + 2 + 3 = 6} and {3 + 2 + 1 = 6} as two different possibilities. Even though there's not a strict requirement that the numbers be in descending order, still, we have to divide to eliminate redundancy.

This is very tricky because, within each triangular number, the redundancy shows up differently for different partition possibilities --- consider triplets that add to 6 ---- 5 spaces between the numbers, so 5C2 = 10

the combination {1, 2, 3} shows up 3! = 6 different ways

the combination {1, 1, 4} shows up 3 different ways

the combination {2, 2, 2} shows up only 1 way

For that one, although we count 10 possibilities of where the partitions can fall, but there are only three distinct combinations of three numbers that add to six.

It's not clear to me there's a quick way to calculate this without going through all the cases one at a time. What do you think?

With great respect,
Mike

Mike@Magoosh wrote: I have some questions about the second question --- it's true that, in the second question, we no longer have the requirement that a > b > c, so we now can have repeated values {e.g. 1 + 1 + 4 = 6, 2 + 2 + 2 = 6, etc.) But, presumably, we still are looking for combinations, and therefore we would not count {1 + 2 + 3 = 6} and {3 + 2 + 1 = 6} as two different possibilities.

I think, if you're asked a question like How many different solutions are there to the equation x+y=3 if x and y must be positive integers?, the most natural way to interpret the question is to find all ordered pairs (x, y) where x+y = 3. So I'd consider the answer to be two; x can be either 1 or 2, and y can be 2 or 1, respectively. So I didn't interpret the second question in the OP as a 'combinations problem' - which was convenient, since it made the solution easier.

If instead you wanted to answer the question "how many distinct unordered sets of three positive integers have a sum of at most 20?", I'm almost certain that would be a very tedious question to solve, or at least I don't see an elegant solution. I suppose you could adapt the approach I used for the first question in the OP to get a formula for each possible sum, but there are annoying complications - for example, for some sums, like 15, all three numbers can be equal, whereas for other sums they cannot. So I agree solving that kind of question would require you to separate out at least a few different cases, which wouldn't be fun to even try.