I was doing the GMATPrep CAT test #1 and came up to this question on the Math section:



Can anyone propose a quick and generic solution that uses some number theory tricks? - I searched the forum and found a trick but it works only for odd powers which is not the case with this question. The trivial solution is to use brute force to find the three numbers but this does not seems reasonable, considering the time constrains - what if instead of 75 the question asked for 7832?

Thanks in advance for your hints/solutions![/i]

Ross -

Don't worry, you won't face this same question with with 7832 instead of 75. There are ways to do this quickly if being implemented on a computer, but that doesn't mean the arithmetic isn't impossible to do in two minutes by hand! In general all positive integers except those that leave a remainder of 7 when divided by eight can be expressed as the sum of the squares of 3 positive integers. So for example,75 leaves a remainder of 5 when divided by 8, so it works, but 63 would not. I think this was proved by Gauss, but it is really, really beyond the scope of the GMAT.

The easiest way to approach this is by process of elimination with a little number theory. The perfect squares that are small than 75 are: 1,4,9,16,25,36,49,64. Now the number theory: Since 75 is odd, either 1 or 3 of the perfect squares must be odd. So EEO or OOO only. EOO or EEE would have an even sum.

Now, it's just a process of elimination. Start with 64 - do any of the remaining possibilities sum to 11? Nope. 64 is out. Next try 49. Can you choose two of the remaining perfect squares to sum to 26? Yes! 25 and 1. So we have 49+25+1 = 75. The question asks for the sum of the numbers, not the squares, so the answer is 7+5+1 = 13.

excellent.

note the different elements of the solution:
* understanding perfect squares and being able to list them quickly
* understanding and applying the theory of odds and evens to narrow down the choices
* guess and check

--

it's important to realize that 'guess and check' is not some forbidden fruit. indeed, you may get problems on which guess and check is far and away the best way - or even the only way - to get the solution; most commonly, such problems will, like this one, require a smattering of theory / number properties to get the solutions down to the point where there's not an overwhelming quantity of guessing and checking to do.

ironically, you're absolutely right about your not being able to solve the problem with 7832: the smallish numbers in the problem can actually be taken as an endorsement of the guess-and-check technique (at least once you've used the number properties to narrow the choices a bit).