December 2009
—————————
In my December diary I posed the following brain-teaser from the 2009 China Girls Mathematical Olympiad:
Show that there are only finitely many triples (a, b, c) of positive integers satisfying the equation abc = 2009(a + b + c)
—————————
Solution
Wolog (sorry: that's math-speak for "without loss of generality") we may assume
a ≥ b ≥ c.
So b ⁄ a ≤ 1 and
c ⁄ a ≤ 1.
But the original equality can be rewritten as
bc = 2009 (1 + b ⁄ a + c ⁄ a)
We have just shown that the parenthesis on the right-hand side is ≤ 3. Therefore
bc ≤ 6027.
Since we are dealing with whole numbers here, it follows that only a finite number of (b, c) is
possible.
And since the original equality is linear in a, it can be rewritten to show a uniquely in terms of
b and c.
It follows that only a finite number of a is possible. Q.E.D.
[Actually a = 2009 (b + c) ⁄ (bc − 2009), but I wouldn't give extra points for writing this out. For proof purposes, it's sufficient to note that there is some expression giving a single a for each (b, c). Note also that from this expression for a it follows that bc ≥ 2010, so we have both lower and upper bounds for bc: 2010 ≤ bc ≤ 6027. The lower bound is attained several times, but the highest value I could find for bc was 4,920, corresponding to the first row of the table below.]
What is the actual number of possible (a,b,c)? A fast bit of VB coding came up with 258, listed below … but I don't guarantee this sort of thing. And if anyone can tell me how to get the number 258 (or whatever it is) with pure reasoning, I'd be most interested to hear.
I note before leaving this problem how mathematical intuition can sometimes lead one astray. Seeing that sum and that product, my mind immediately flew to the geometric and arithmetic means, the first of which, by a well-known theorem, cannot exceed the second. I then wasted several minutes — nothing to me, but perhaps fatal in an exam situation — fiddling with that theorem. All it gives you is lower bounds for abc and a + b + c, thus:
Since, by the aforementioned theorem, (abc) 1 ⁄ 3 ≤ (a + b + c) ⁄ 3, I can
• substitute for a + b + c:
2009 × 3 ×(abc) 1 ⁄ 3 ≤ abc
which boils down to abc ≥ 6027 3 ⁄ 2
• substitute for abc:
2009 (a + b + c) ≤ (a + b + c)3 ⁄ 27
which boils down to a + b + c ≥ 542431 ⁄ 2
So abc ≥ 467,899 and a + b + c ≥ 233. Which is kind of interesting, but no help towards solving the problem.