IMO 1988, problem 6

In 1988, IMO presented a problem, to prove that $k$ must be a square if $a^2+b^2=k(1+ab)$, for positive integers $a$, $b$ and $k$. I am wondering about the solutions, not obvious from the proof. Beside the trivial solutions a or $b=0$ or 1 with $k=0$ or $1$, an obvious solution is $a=b^3$ so that the equation becomes $b^6+b^2=b^2(1+b^4)$ . Are there any other solutions?

Solution 1:

This is a famous problem, here is one of the solutions that I like the most that I read it in a book previously, but later in a topic on here I realized the importance of the problem (The credit goes to T. Andreescu & R. Gelca If I remember it correctly, but I'm not sure, since 11 individuals in that year solved this problem and I'm not sure about their solutions):

Solution: Suppose that $\displaystyle \frac{a^2+b^2}{a.b+1}=x$ We want to prove that for every non-negative integer pairs $(\alpha,\beta)$ with the property that $\displaystyle \frac{\alpha^2+\beta^2}{\alpha\beta+1}=x$ and $\alpha \geq \beta$ the pair that minimizes $\alpha+\beta$ must imply $\beta=0$. If that happened, then $x=\alpha^2$. So, suppose that $(\alpha,\beta)$ is such a pair that minimizes $\alpha+\beta$ but $\beta>0$. then we can obtain the equation $y^2 - \beta xy + \beta^2 -x =0$ from $\displaystyle \frac{y^2+\beta^2}{y\beta+1}=x$. This equation has $\alpha$ as one of its roots and since the sum of the roots is $\beta x$, the other root must be $\beta x - \alpha$. Now if we prove that $0 \leq \beta x - \alpha < \alpha$ then we're done because this contradicts the minimality of $(\alpha,\beta)$

$x = \displaystyle \frac{\alpha^2+\beta^2}{\alpha\beta+1}<\frac{2\alpha^2}{\alpha \beta} = \frac{2 \alpha}{\beta} \implies \beta x-\alpha < \alpha$

and it's also possible to show that $\beta.x - \alpha \geq 0$ but honestly I don't remember that part of the proof and I leave it to you. That completes the proof.

(Also check that wikipedia link provided by pre-kidney).

Solution 2:

The technique for this type of problem is called "Vieta root jumping". On the wikipedia page describing this technique, this very problem is used as an example. See here.

Of course there are many more solutions; we can enumerate them by flipping repeatedly and using symmetry. For example, your solution $(b, b^3)$ is the result of flipping $(b,0)$ when $k=b^2$. But if we flip around $b^3$ instead, we get the new solution $(b^5-b, b^3)$.

Indeed, $$x^2-b^5x+(b^6-b^2)=(x-b)(x-b^5+b)$$ so we also have $$b^6 + (b^5-b)^2 = b^2(1 + b^3(b^5-b))$$

Solution 3:

All solutions can be written as: $$ \text{if $n$ is even:}\enspace a_n= { \sum\limits_{i=0}^{{n\over{2}}} {(-1)^{i+{n\over{2}}}{{n\over{2}}+i\choose {n\over{2}}-i}g^{4i+1}}} \\ \text{if $n$ is odd:}\enspace a_n= \sum\limits_{i=0}^{{n-1\over{2}}} (-1)^{i+{n-1\over{2}}}{1+{n-1\over{2}}+i \choose {n-1\over{2}}-i}g^{4i+3} \implies \\ {{a_n}^2+{a_{n+1}}^2\over{a_na_{n+1}+1}}=g^2\\ $$ Or also: $$ a_n={g{\bigg({g^2+\sqrt{g^4-4}\over{2}}\bigg)}^n\over{\sqrt{g^4-4}}} - {g{\bigg({g^2-\sqrt{g^4-4}\over{2}} \bigg)}^n\over{\sqrt{g^4-4}}} \\ $$

see here for complete solution

Solution 4:

Supposing that

$$ \frac{a^2 + b^2}{ab + 1} = k$$ then

$$ a^2 - a(kb) + (b^2 - k) = 0 $$

So using quadratic formula gives: $$ a = \frac{kb \pm \sqrt{k^2b^2 -4(b^2 -k)}}{2}$$

The solutions are when $k = b^2 $ and thus $a= kb = b^3$

So $$ b = 1 , a = 1 , k= 1$$ $$b = 2 , a = 8, k = 4$$

$$ b= 3, a= 27, k = 9 $$ and so on....

There are other ways of getting more solutions than these such as b = 8, a = 30 and k = 4 where k is not $b^2$ or $a = b^3$ and of course the zero one. I have not yet found a way to find more solutions than this.