home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 17050 < prev    next >
Encoding:
Internet Message Format  |  1992-12-16  |  3.2 KB

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