home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!mcsun!uknet!acorn!eoe!jrickard
- From: jrickard@eoe.co.uk (John Rickard)
- Newsgroups: sci.math
- Subject: Re: A Problem
- Message-ID: <1477@eouk12.eoe.co.uk>
- Date: 16 Dec 92 20:10:25 GMT
- References: <1992Dec11.035049.25067@math.toronto.edu>
- Organization: EO Europe Limited, Cambridge, UK
- Lines: 56
- X-Newsreader: TIN [version 1.1 PL6]
-
- Paul Hsieh (hsieh@math.toronto.edu) wrote:
- : (Alexander Burshteyn) writes:
- : >Here is a nice problem [...]
- : >Prove that if, for some non-negative integers A and B, we have that
- : >(A^2 + B^2) / ( 1 + AB) is an integer, then it is a square of an integer.
- ...
- : Actually, this appeared on an IMO question a few years ago. Just for fun some
- : of us at U(T) tried solving the question from scratch (without looking up the
- : solution somewhere). But we cheated by running a computer program for ages to
- : find examples.
- [Description of how proof was found omitted.]
- : Now, I enjoy doing problems as much as the next guy, but the question I have,
- : is: How in the heck is someone supposed to see this under contest conditions?
-
- Well, I could describe how I found it the other evening. I'd glimpsed
- Paul Hsieh's message, and though I tried to ignore it I'm sure it
- helped me; nevertheless, I think it's plausible that somebody could
- find it this way under contest conditions.
-
- Omitting some approaches I tried that didn't lead anywhere, my
- thoughts went roughly:
-
- We have A^2 + B^2 = C(1+AB). Let's look at some solutions. C=1 is
- uninteresting. Assuming the problem is right, C must be a square,
- so look at C=4. Then A^2+B^2=4(1+AB). Taking this mod 4 shows A
- and B are both even; say A=2A', B=2B'. Then A'^2 - 4A'B' + B'^2 =
- 1. This suggests A'/B' must be close to a root of x^2 - 4x + 1 = 0;
- the larger root of this (let's assume A >= B) is (calculate...)
- 2+sqrt(3), which is about 3.732. We need A'/B' slightly bigger than
- this; the continued fraction approximations are most likely; it's
- obvious that some good approximations are 4/1 and 15/4.
- (Calculate...) Indeed, (8,2) and (30,8) are solutions. So how does
- the continued fraction go?
-
- 2+sqrt(3) = 3 + 1/((1+sqrt(3))/2)
- = 3 + 1/(1 + 1/(1+sqrt(3)))
-
- so if a/b is one approximation then the next but one (we need
- overestimates so we're only in alternate approximations) is
- 3+1/(1+1/(a/b - 1)), which is (4a-b)/a. Putting a/b = 30/8 gives
- 112/30, and (calculate...) (112,30) is indeed a solution; it's
- looking very good. Now try to prove that all solutions (with C=4
- still) are like this (I'm familiar with similar arguments that show
- that (eg) all solutions of 2x^2 = y^2 + 1 come from the continued
- fraction, which makes the argument easier for me to find); inverting
- the map a/b |-> (4a-b)/a gives a/b |-> b/(4b-a), so we want to check
- that if (a,b) is a solution then (b,4b-a) is also one, which should
- be smaller. Make a guess at the generalization that for general C,
- if (a,b) is a solution then so is (b,Cb-a) - (calculate...) and it's
- true! Since C must obviously be a square if A or B is zero, this
- gives a proof of the theorem, if I write it all down neatly and hide
- all traces of how I found it. (There are some minor details left,
- such as showing that (b,Cb-a) is indeed smaller in some sense than
- (a,b).)
-
- -- John Rickard
-