Author |
Topic: (a^2+b^2)/(ab+1) (Read 14785 times) |
|
BNC
Uberpuzzler
Gender: 
Posts: 1732
|
 |
(a^2+b^2)/(ab+1)
« on: Jun 10th, 2004, 6:29pm » |
 Quote  Modify
|
After deciding not to attempt adaptation after 2AM, I post this interesting question in it's original form here (it's 4AM...). If I had to choose, I'd place it in "hard" (see background below).
Let a and b be positive integers , such that t = (a2+b2)/(ab+1) is an integer.
Show that t is also a perfect square.
For extra credit, characterise all triplets (a,b,t).
background
This problem is from IMO98 (so yes, it's solution is available on the web -- not sure about the "extra").
The problem selection committee (6 members, including G. Szekeres), who always try to solve the problems themselvs in order to get first-hand impression about the difficulty of the problem, couldn't solve it.
The committee then presented the problem to several number theory experts, asking them to solve it in 6 hours. They failed.
Finally, it was decided to use the problem in the 2nd day of the olympics (when the contestants have 4.5 hours to solve 3 questions). Out of ~200 participants that year, 11 solved the problem.
So, yes, I'd say it is "hard".
Or is it?
|
|
 IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #1 on: Jun 11th, 2004, 12:50am » |
Quote Modify
|
::
(x, x3, x2) or (x3, x, x2)
::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #2 on: Jun 11th, 2004, 12:56am » |
Quote Modify
|
1. That's not a proof!
2. You get partial credit. It doesn't cover, e.g., the triplet (8,30,4).
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #3 on: Jun 11th, 2004, 2:30am » |
Quote Modify
|
I suppose it would have been too simple if that was the only sort of triple..
::I only found (8,2,4) to being with, and just guessed at the pattern (x3, x, x2) and after filling it in it worked..::
|
| « Last Edit: Jun 11th, 2004, 2:31am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #4 on: Jun 11th, 2004, 4:28am » |
Quote Modify
|
Excellent puzzle, BNC!
2. Conjecture:
[smiley=square.gif]
For every integer t, define a sequence {sn} as follows: s0 = 0; s1 = t; sn = t2sn-1 - sn-2. Then, triple (sn, sn+1, t2) satisfies the condition of the problem.
The conjecture is that these sequences cover all the cases.
[smiley=square.gif]
Of course, it’s not a proof… 
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #5 on: Jun 11th, 2004, 5:30am » |
Quote Modify
|
Briliant!
The solution I had requires using a couple of special cases, which your conjecture covers!
Now, all you have left is the proof (and, offcourse, the original problem's solution).
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #6 on: Jun 18th, 2004, 6:46pm » |
Quote Modify
|
Let t = (a2+b2) / (ab+1) be a positive integer.
And, as a = b => t = 1, WLOG let a > b
Then a2 - tba + b2 - t = 0.......[1]
If the roots of this quadratic in a are a1 and a2 then
a1 + a2 = tb........[2]
a1a2 = b2 - t.......[3]
Hence, if (a1, b) is a solution, then so is (tb - a1, b)
And from [3], if a1 > b then a2 < b
We thus get a strictly decreasing sequence {sn} of integers given by
s0 = a1
s1 = b
s2 = tb - a1
.................
..................
...................
sk = tsk-1 - sk-2
|
| « Last Edit: Jun 19th, 2004, 3:47am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #7 on: Jun 19th, 2004, 2:13am » |
Quote Modify
|
Yes, that's it! ... And the conjecture is correct.
Once you see the solution, it looks so simple, doesn't it? 
What were all those number theorists and other experts thinking? 
By the way, the problem wasn't at IMO98, it was at IMO88.
|
|
IP Logged |
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #8 on: Jun 19th, 2004, 2:21am » |
Quote Modify
|
on Jun 19th, 2004, 2:13am, Barukh wrote:| By the way, the problem wasn't at IMO98, it was at IMO88. |
|
Sorry, typo... 
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #9 on: Jun 22nd, 2004, 4:34am » |
Quote Modify
|
on Jun 19th, 2004, 2:13am, Barukh wrote:What were all those number theorists and other experts thinking?
|
|
How does it show t to be a perfect square?
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: (a^2+b^2)/(ab+1)
« Reply #10 on: Jun 22nd, 2004, 5:55am » |
Quote Modify
|
on Jun 22nd, 2004, 4:34am, BNC wrote:
How does it show t to be a perfect square? |
|
I was afraid you would ask that.
Well, if we relax the condition that a,b > 0 (provided t > 0), we have
sk2 + sk+12 / 1 + sksk+1 = t for k = 0,1,2,3....
If sk+1 = 0 for some value of k, then t = sk2
Assume that there is NO k such that sk+1 = 0
Then, as the sequence is strictly decreasing, there must exist two consecutive terms which are of opposite sign.
Thus (a2+b2) / (ab+1) must be either infinite (if ab = -1) or negative (if ab < -1), contradicting the condition that t > 0
|
| « Last Edit: Jun 22nd, 2004, 11:43am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print