NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/sci/math/16761

Text File | 1992-12-12 | 4.3 KB | 95 lines

Newsgroups: sci.math
Path: sparky!uunet!utcsri!utmath!hsieh
From: [e-mail] (Paul Hsieh)
Subject: Re: A Problem
Message-ID: <[e-mail]>
Organization: Department of Mathematics, University of Toronto
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Sat, 12 Dec 92 10:02:58 GMT
Lines: 84

In article <[e-mail]> [e-mail] (Ray Steiner) writes:
>[e-mail] (Ray Steiner) writes:
>
>>[e-mail] (Paul Hsieh) writes:
>
>>>(Alexander Burshteyn) writes:
>>>>Here is a nice problem, which was given, I believe, at the International High
>>>>School Student Olympiad in Australia (I'm not sure about the exact title of the
>>>>the competition, though).
>>>>
>>>>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.
>>>>
>>>>Enjoy,
>>>>
>>>>Alex Burshteyn.
>
>
>>>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.  We quickly came to the conjecture that the only possible (a,b)
>>>was (p,p^3), but this is shot down by the example (30,8).  But after further
>>>examimation of the data, Ed Dolittle saw the following:
>>>If (a,b,k) is a solution where, (a^2+b^2)/(1+a*b)=k, and a,b,k are non-negative
>>>integers, with a>=b, then so is (|a-k*b|,b,k).  Using this observation we see
>>>that if (a,b,k) is a solution then we can find a different solution (c,d,k)
>>>with c<=a, d<=b.  Applying this succesively we find that eventually one of
>>>a or b will become 0 => k = a^2 or k=b^2.  (Note that throughout, k does not
>>>change which is the important point of the procedure).  QED.
>>>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?
>>>If you tried to find examples by hand, you'd be hard pressed, as there are
>>>no non-trivial (meaning (p,p^3)-type examples) examples which are small,
>>>besides (30,8).  And seeing that reducing step, in my mind, is not at all
>>>obvious without looking at some examples.  My recollection is that very few
>>>people got this question when it appeared at the IMO and I am surprised that
>>>anyone did!  Hats off to those that did.  Anyways, that's about enough
>>>bandwidth for me,
>
>>>Paul Hsieh
>
>>But, aren't we getting away from the original problem here?
>>Neither this reply nor the previous one solves the ORIGINAL
>>problem! The infinite descent argument indeed proves that
>>a(or b) must eventually be zero, but ignores all other possible
>>values of a and b. The division argument given in another
>>post is also wrong, because of the solution (30,8). I tried
>>solving the problem by computing the discriminant of the quadratic
>>a^2-kab+(b^2-k)=0 and noting that it must be a square, but
>>this didn't lead anywhere either! Surely,  the examiners
>>who set this question must have had a simpler idea in mind!
>>Ray Steiner
>
>>--
>>[e-mail]
>
>Oops: Repost: My idea does lead somewhere after all!
>If the discriminant of the quadratic above = c^2, then we
>get
>c^2-(k^2-4)b^2= 4k.
>If k is a square, k^2-4 isn't, so if k is a square we get
>infinitely many solutions! Just replace 4k by 1, solve the
>basic Pell equation and then multiply each of c and b by 2\sqrt(k).
>So now the problem is to show: If k is not a square this
>equation has no integer solutions. If k is not a square mod 5
>this is easy! But how does one prove this in general???
>Ray Steiner
>
>--
>[e-mail]

Excuse me!  But my post _IS_ a solution to the problem.  Perhaps I did not
make it entirely clear.  Let me try again:  Let f(a,b)=(a^2+b^2)/(1+a*b).
Now if k=f(a,b), where k, a, b are integers then there exists c,d such that
k=f(c,d) and |c|<=a, and |d|<=b, by my comments above.  Notice that k has
remained the same in the reduction step.  Then, by applying this reduction
successively you will reduce one to 0.  I.e., k=f(e,0) for some e.  Plugging
this back into the original formula we see: k = e^2.  Therefore, any integers
a,b,k satisfying k=f(a,b) will require k to be a perfect square.

Q.E.D.

Paul Hsieh