home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / 16730 < prev    next >
Encoding:
Text File  |  1992-12-11  |  3.6 KB  |  81 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!bgsuvax!steiner
  3. From: steiner@andy.bgsu.edu (Ray Steiner)
  4. Subject: Re: A Problem
  5. Message-ID: <Bz46J8.8s4@andy.bgsu.edu>
  6. Organization: Bowling Green State University B.G., Oh.
  7. References: <101376@netnews.upenn.edu> <1992Dec11.035049.25067@math.toronto.edu> <Bz3uyJ.5ny@andy.bgsu.edu>
  8. Date: Fri, 11 Dec 1992 21:33:07 GMT
  9. Lines: 70
  10.  
  11. steiner@andy.bgsu.edu (Ray Steiner) writes:
  12.  
  13. >hsieh@math.toronto.edu (Paul Hsieh) writes:
  14.  
  15. >>(Alexander Burshteyn) writes:
  16. >>>Here is a nice problem, which was given, I believe, at the International High
  17. >>>School Student Olympiad in Australia (I'm not sure about the exact title of the
  18. >>>the competition, though).
  19. >>>
  20. >>>Prove that if, for some non-negative integers A and B, we have that
  21. >>>(A^2 + B^2) / ( 1 + AB)  is an integer, then it is a square of an integer.
  22. >>>
  23. >>>Enjoy,
  24. >>>
  25. >>>Alex Burshteyn.
  26.  
  27.  
  28. >>Actually, this appeared on an IMO question a few years ago.  Just for fun some
  29. >>of us at U(T) tried solving the question from scratch (without looking up the
  30. >>solution somewhere).  But we cheated by running a computer program for ages to
  31. >>find examples.  We quickly came to the conjecture that the only possible (a,b)
  32. >>was (p,p^3), but this is shot down by the example (30,8).  But after further
  33. >>examimation of the data, Ed Dolittle saw the following:
  34. >>If (a,b,k) is a solution where, (a^2+b^2)/(1+a*b)=k, and a,b,k are non-negative
  35. >>integers, with a>=b, then so is (|a-k*b|,b,k).  Using this observation we see
  36. >>that if (a,b,k) is a solution then we can find a different solution (c,d,k)
  37. >>with c<=a, d<=b.  Applying this succesively we find that eventually one of
  38. >>a or b will become 0 => k = a^2 or k=b^2.  (Note that throughout, k does not
  39. >>change which is the important point of the procedure).  QED.
  40. >>Now, I enjoy doing problems as much as the next guy, but the question I have,
  41. >>is:  How in the heck is someone supposed to see this under contest conditions?
  42. >>If you tried to find examples by hand, you'd be hard pressed, as there are
  43. >>no non-trivial (meaning (p,p^3)-type examples) examples which are small,
  44. >>besides (30,8).  And seeing that reducing step, in my mind, is not at all
  45. >>obvious without looking at some examples.  My recollection is that very few
  46. >>people got this question when it appeared at the IMO and I am surprised that
  47. >>anyone did!  Hats off to those that did.  Anyways, that's about enough
  48. >>bandwidth for me,
  49.  
  50. >>Paul Hsieh
  51.  
  52. >But, aren't we getting away from the original problem here?
  53. >Neither this reply nor the previous one solves the ORIGINAL
  54. >problem! The infinite descent argument indeed proves that
  55. >a(or b) must eventually be zero, but ignores all other possible
  56. >values of a and b. The division argument given in another
  57. >post is also wrong, because of the solution (30,8). I tried
  58. >solving the problem by computing the discriminant of the quadratic
  59. >a^2-kab+(b^2-k)=0 and noting that it must be a square, but
  60. >this didn't lead anywhere either! Surely,  the examiners
  61. >who set this question must have had a simpler idea in mind!
  62. >Ray Steiner
  63.  
  64. >-- 
  65. >steiner@andy.bgsu.edu
  66.  
  67. Oops: Repost: My idea does lead somewhere after all!
  68. If the discriminant of the quadratic above = c^2, then we
  69. get 
  70. c^2-(k^2-4)b^2= 4k.
  71. If k is a square, k^2-4 isn't, so if k is a square we get 
  72. infinitely many solutions! Just replace 4k by 1, solve the
  73. basic Pell equation and then multiply each of c and b by 2\sqrt(k).
  74. So now the problem is to show: If k is not a square this
  75. equation has no integer solutions. If k is not a square mod 5
  76. this is easy! But how does one prove this in general???
  77. Ray Steiner
  78.  
  79. -- 
  80. steiner@andy.bgsu.edu
  81.