# 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?

• There are some very detailed analyses of this problem here searchable with the words 'IMO 1988'. – zyx Sep 4 '13 at 7:48
• mathoverflow.net/questions/250172/… – individ May 12 '17 at 4:40

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

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

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

Not quite a proof to the original IMO problem, but there definately is a very easy way to compute all possible answers. Also it demonstrates that here, Vieta jumping is basically just using symmetry to jump between the two solutions of the good old quadratic formula.

Nothing complicated below, but I haven't seen this explanation anywhere else.

Suppose: $${{a^2+b^2} \over {1+ab}} = c$$ Then using the quadratic formula to solve b (and a little rewriting) gives: $$b = {ac \pm \sqrt {a^2 (c^2-4) + 4c} \over 2}$$ Using this we can compute all answers for any given c. Eg: assume c = 4. Then we get: $$b = {a \cdot 4 \pm \sqrt {a^2 \cdot 12 + 16} \over 2}$$ We know that a = 0 will always provide a solution. That gives us: $$a = 0 \Rightarrow b = {{0 \cdot 4\pm \sqrt {0 \cdot 12 + 16}} \over 2} = 2 \Rightarrow (a,b) = (0,2)$$ But because of the symmetry, if (0,2) is a solution, then (2,0) must also be a solution. And since the quadratic formula has 2 solutions, it will produce another solution. $$a = 2 \Rightarrow \space b = {{2 \cdot 4 \pm \sqrt {4 \cdot 12 + 16}} \over 2} = 0 \space or \space 8 \Rightarrow (a,b) = (2,8)$$ $$a = 8 \Rightarrow \space b = {{8 \cdot 4 \pm \sqrt {64 \cdot 12 + 16}} \over 2} = {32 \pm 28\over 2} = 2 \space or \space 30 \Rightarrow (a,b) = (8,30)$$ $$a = 30 \Rightarrow \space b = {{30 \cdot 4 \pm \sqrt {900 \cdot 12 + 16}} \over 2} = {120 \pm 104\over 2} = 8 \space or \space 112 \Rightarrow (a,b) = (30,112)$$ Same can be done for c = 9, 16, 25, etc.

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.

• But what about for example $b=8,a=30,k=4$ ? Clearly we don't have : $k=b^2$ or $a=b^3$. But nevertheless we have : $\enspace \frac{8^2+30^2}{8.30+1}=4$.. – Rutger Moody Jun 30 '17 at 12:42
• Oh yes, you are right. Thank you for that, I will look into this question more and will edit my answer. – Shrenik Jul 5 '17 at 8:53

Let the following sequence of polynomials \begin{equation*} P_1(n)\,=\,n\,,\,\, P_2(n)\,=\,n^3,\ldots, P_{k+2}(n)\,=\,\frac{P^2_{k+1}(n)-n^2}{P_k(n)}, \,\,\,k\in\mathbb N, \end{equation*} which in fact have the following general formula $$P_m(n)\,=\,\sum_{r=0}^{\left[\frac{m-1}{2}\right]} (-1)^r\,\left( \begin{array}{c} \!m\!-\!r\!-\!1\! \\ r \end{array} \right) \,n^{2m-4r-1}. \label{polunomial}$$ Then one can show the following: If $a,b$ are positive integers with $b\ge a$, such that $$\frac{a^2+b^2}{1+ab}=k$$ is also an integer, then $k$ is a perfect square, i.e., $k=n^2$, and there exists an $m\in\mathbb N$, such that $$a=P_m(n)\quad\text{and}\quad b=P_{m+1}(n).$$

The answer to this question is based on the method of Vieta Jumping.Graphing the given equation on a graph will give us hyperbolas with a certain pattern in solutions. Wikipedia have a page related to this topic.

First, in Excel, I put the numbers in a column, and then arranged the equation in 3 columns based on the formula, and I realized that some of the remaining were zero, and then I became interested in the subject, and it took about 8 hours to realize that for all the real numbers, equation can be correct. If “r” is integer we can find integer numbers as like as “a” and “b” that Makes equation can be correct. If r is a real number we can find real numbers as like as “a” and “b” that Makes equation can be correct. Prove that for any real number such as “r”
We can make this equation r^2=(a^2+b^2 )/(ab+1 ) that a,b∈R (a^2+b^2 )/(ab+1 ) =A For the all of real numbers as “a” a ∈ R a^2=a^2 ①
a^4+1 = a^4+1 ⟹ (a^4+1)/(a^4+1 )=1 ② ① & ②⟹ a^2=a^2 (a^4+1 )/(a^4+1 )= (a^6+a^2 )/(a^4+1 ) = (a^2+a^6 )/(a(a^3 )+1) = B IF (A=B) ⟹ (a^2+b^2 )/(ab+1 ) = (a^2+a^6 )/(a(a^3 )+1) (If (m )/(n ) = (x )/y ⟹ my= nx) ⟹ (a^2+b^2) * ( a(a^3 )+1)=( ab+1) * ( a^2+a^6) a^6+a^2+a^4 b^2+b^2= a^3 b+a^7 b+a^2+a^6 a^4 b^2+b^2=a^3 b+a^7 b ⟹b^2 (a^4+1)=a^3 b(a^4+1)

b^2=a^3 b ⟹ {(b=0 ⟹ a^2/1=a^2 and the A is true for all of real numbers)/(b≠0 ⟹b=a^3 for all of real number )

We know that the set of real numbers is closed with multiplication Then we can make equation (r^2 = (a^2+b^2 )/(ab+1 ) ) for every real number Therefore for all integer numbers we can find two integer numbers that can make equation. If we select r from each set the other numbers must select from same set.