wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> (a^2+b^2)/(ab+1)
        
(Message started by: BNC on Jun 10^th, 2004, 6:29pm)

Title: (a^2+b^2)/(ab+1)
Post by BNC on Jun 10^th, 2004, 6:29pm

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 = (a²+b²)/(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?

Title: Re: (a^2+b^2)/(ab+1)
Post by towr on Jun 11^th, 2004, 12:50am

::[hide]
(x, x³, x²) or (x³, x, x²)
[/hide]::

Title: Re: (a^2+b^2)/(ab+1)
Post by BNC on Jun 11^th, 2004, 12:56am

1. That's not a proof!

2. You get partial credit. It doesn't cover, e.g., the triplet (8,30,4).

Title: Re: (a^2+b^2)/(ab+1)
Post by towr on Jun 11^th, 2004, 2:30am

I suppose it would have been too simple if that was the only sort of triple..
::[hide]I only found (8,2,4) to being with, and just guessed at the pattern (x³, x, x²) and after filling it in it worked..[/hide]::

Title: Re: (a^2+b^2)/(ab+1)
Post by Barukh on Jun 11^th, 2004, 4:28am

Excellent puzzle, BNC!

2. Conjecture:
[smiley=square.gif][hide]
For every integer t, define a sequence {s_n} as follows: s₀ = 0; s₁ = t; s_n = t²s_n-1 - s_n-2. Then, triple (s_n, s_n+1, t²) satisfies the condition of the problem.

The conjecture is that these sequences cover all the cases.
[/hide][smiley=square.gif]

Of course, it’s not a proof… ::)

Title: Re: (a^2+b^2)/(ab+1)
Post by BNC on Jun 11^th, 2004, 5:30am

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).

Title: Re: (a^2+b^2)/(ab+1)
Post by THUDandBLUNDER on Jun 18^th, 2004, 6:46pm

Let t = (a²+b²) / (ab+1) be a positive integer.
And, as a = b => t = 1, WLOG let a > b

Then a² - tba + b² - t = 0.......[1]

If the roots of this quadratic in a are a₁ and a₂ then
a₁ + a₂ = tb........[2]
a₁a₂ = b² - t.......[3]

Hence, if (a₁, b) is a solution, then so is (tb - a₁, b)

And from [3], if a₁ > b then a₂ < b

We thus get a strictly decreasing sequence {s_n} of integers given by
s₀ = a₁
s₁ = b
s₂ = tb - a₁
.................
..................
...................
s_k = ts_k-1 - s_k-2

Title: Re: (a^2+b^2)/(ab+1)
Post by Barukh on Jun 19^th, 2004, 2:13am

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? ;D

By the way, the problem wasn't at IMO98, it was at IMO88.

Title: Re: (a^2+b^2)/(ab+1)
Post by BNC on Jun 19^th, 2004, 2:21am

on 06/19/04 at 02:13:25, Barukh wrote:

By the way, the problem wasn't at IMO98, it was at IMO88.

Sorry, typo... :(

Title: Re: (a^2+b^2)/(ab+1)
Post by BNC on Jun 22^nd, 2004, 4:34am

on 06/19/04 at 02:13:25, Barukh wrote:

What were all those number theorists and other experts thinking? ;D

How does it show t to be a perfect square?

Title: Re: (a^2+b^2)/(ab+1)
Post by THUDandBLUNDER on Jun 22^nd, 2004, 5:55am

on 06/22/04 at 04:34:34, 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
s_k² + s_k+1² / 1 + s_ks_k+1 = t for k = 0,1,2,3....

If s_k+1 = 0 for some value of k, then t = s_k²
Assume that there is NO k such that s_k+1 = 0
Then, as the sequence is strictly decreasing, there must exist two consecutive terms which are of opposite sign.
Thus (a²+b²) / (ab+1) must be either infinite (if ab = -1) or negative (if ab < -1), contradicting the condition that t > 0