1988 IMO Question Six

Using no more than high school algebra, here’s how to solve the infamous question 6 from the 1988 International Mathematics Olympiad.

Motivation

This problem has a reputation for being one of the hardest, and perhaps the hardest, IMO problem of all time. And you can solve it only using high school algebra. Struggling through and understanding the solution will do several really cool things for you, but will take time, so motivation is essential.

First, you’ll understand that you can help advance mathematics. I spent several days solving this problem, whereas in the competition they have 4 and a half hours for 3 questions. But I’m not amazing at mathematics — I’m an undergraduate economist. I do maths for fun, and I didn’t give up. You don’t need to be a genius to be a good mathematician. If you work hard, you will be able to solve really hard problems and, maybe one day that will be solving hard research problems. In real life, it doesn’t matter if you are slower than the super geniuses, because there aren’t enough super geniuses to go round. We need ordinary people to work hard and solve problems. Rome wasn’t built in a day, and nor was it built by one person!

Second, you’ll get a taste for what mathematicians do when approaching a problem and the language they use. Normally it takes well into an undergraduate degree to see this because the material is advanced. I have made my solution so that it uses no more than algebra — that’s right, no dreaded calculus or anything! — so that it’s accessible. The solution is then broken down into these things called ‘Lemmas’ and ‘Colloraries’. Lemmas are when we solve a smaller sub-problem which will help solve the big problem. Corollaries are when we look at some implications of using the Lemmas.

The way mathematicians lay things out makes sense. The idea is that we break everything into manageable steps so I, as the problem-solver, can make incremental progress and so you, the reader, can understand every step of the proof. If you can’t understand it, give it a good 10 minutes or so, get pen and paper, and try and figure it out. Ask me in the comments if you’re still stuck, and I’ll reply to you or update my solution to improve the exposition.

Manageable steps is the reason why everyone can work hard and get good at math. If you can’t solve the problem, you play around and solve smaller, perhaps relevant, statements.

I’ll leave exercises throughout. It’s upto you whether or not to use them. If you do use them and work through them, you’ll understand the solution better. If you are stuck on one go back to it a bit later if you aren’t making any progress.

Statement of the problem

IMO proof 1988, question 6

Prove that if x, a, b are all integers then x is a square. For instance, a = 3, b = 27, x = 9 works. So does a = 125, b = 3120, x = 25

Exercise 1. Can you find any other examples of three integers which work? Can you spot any patterns?

Lemma 1

Solutions are paired. Finding one of a pair enables you to find the other.

Imagine you have a list (or ‘set’) of all pairs of integers (x, a).

Doing some algebra, we can see

Exercise 2. Can you work out how I got some or all of these results?

Now we whittle it down to all pairs of integers such that

is a square. Checking the potential even and odd pairings of x and a we can work out that that b will be an integer. (As we are just checking even and odd parities, below I only look at where oddness or evenness results after an operation)

Exercise 3. Why is the square root of an odd number odd? Why is the square root of an even number even? Why is an even number divided by two guaranteed to be an integer?

If we find an (x, a, b) that works, all we need is (x, a) to deduce both values of b which work for those values of x and a. This is because of the +/- in the formula we found for b.

Lemma 2: The Magical Step

There are no solutions where a < 0 and b > 0 (or vice-versa).

This isn’t immediately obvious at all. To start off with, we will rephrase the question. Eyeballing the equation and flipping signs appropriately, you will notice that this is the same as there being positive integers (x, a, b) such that

Exercise 4. Can you understand why this is true? (Hint. let a* be < 0 and x* 3/2, we will get unbounded growth, by pinging back and forth, using our improved bound on a to increase the bound on b, and then use the increased bound on b to increase the bound on a! But this is a contradiction. After all, a and b are finite, but by repeating our procedure we have also shown they are greater than any finite number.

Lemma 3

a,b ≥ root x for all positive integer solutions.

Suppose our arch-nemesis handed us (x, a) such that

Is an integer, and a < root x. Then we write the following as a solution

However, by assumption

This is a contradiction, using lemma 2! After all, we’d have found a solution with a > 0 and b < 0.

Thus both a,b ≥ root x

Lemma 4: The Magical Step revisited

One of a,b < x or one of the paired solutions has one of a*,b* < x

Start with b.

Thus, by assumption, we can deduce

Why? Suppose it were less than x. Then we would be done, as we would have a paired solution with b < x, which is what we wanted.

Now we want to find a suitable lower bound for that horrible square root expression. We have to be quite cunning, to make the inequality tight enough, but not so tight as to lose generality. For x >= 3, we can safely write

Exercise 8. Try and understand why the above inequalities hold.

This allows us to write

As both a and b are greater than x, we also get (by using the same logic with variable names switched)

Thus a > 2x, b > 2x.

But now we can repeat this procedure!!!!!

And we will also be able to deduce that b > 4x. We can repeat this forever. This means there are no solutions, as the lower bound for both a and b can be made arbitrarily large.

Exercise 9. That was hard. Reflect for a bit on why the logic works if you are unsure. Re-read the lemma again now and in a few hours or tomorrow.

Lemma 5

For each solution where neither of a, b root x. One of a and b is less than x by Lemma 4. Let’s say it’s a, which gives us the following inequality.

We find a solution b* such that

By the magical lemma, this is a contradiction, or b* = 0, which gives an easy set of cases to verify. (Alternatively, you could use the inequality above to show that there are no integer solutions in the range ax-2a/x and xa which work, as the only option is xa — 1, which can be checked by hand).

Corollary 1

For each solution (x, a, b) there is an implied solution where a = root x or b = root x.

We know that there is an implied solution where one of a or b is 0 by lemma 2.

We can easily see that solutions where a < 0 and b < 0 are mirrored in solutions where a > 0 and b > 0, as the negative signs cancel.

So we look at positive integer solutions. By lemma 3 there are no solutions where one of a or b is less than root x. (This used lemma 2).

Now we get onto lemma 4. This told us that, given a solution triple (x, a, b) one out of a*, b*, a, b was < x, where a* and b* are the paired or ‘implied’ solutions. Thus, suppose we found all solutions with one of a or b < x had x being a square. Then this would be true for all solutions where both a and b >= x, as x remains the same when we observe the a* and b* this solution is paired with.

Lemma 5 told us that this was indeed true. And so we are done. Can you see how to classify all the solutions? That’s coming next!!

Reflections and thoughts

That was hard. I find it hard sometimes to remember why a bit worked! If you have made it this far, you should feel proud, even if you understand just 10% of what happened. I always feel a bit baffled when I first encounter some hard maths, and it’s only over a long amount of pondering that I ‘get it’.

Exercise 10. Reflect on how well you understood the solution. Spend some time thinking about the bits you found hard, re-read them, write stuff out by hand on paper, ask questions in the comments. If you remember, read through the solution in a few days again, and then in a week or so, and see if you understand more of it.

Math is something to be taken slow. It takes time to digest and understand fully. I often spent days or even weeks mulling over a hard problem.

Free Math Resources

Khan Academy — website with Math, Science and coding, all free. Goes from basics right up to some university level stuff.

3Blue1Brown — Math educator. He creates amazing animated videos to help give an intuitive understanding of math.

Art of Problem Solving — range of math problems, especially competition math.

Past International Maths Olympiad Problems — these are hard. They’re fun to attempt, but be willing to spend a long time working on one.

Dexter’s Notes — Lecture notes and practice sheets from the Cambridge Mathematics Tripos. This is HARD! Not recommended for beginners. Part IA means first year undergraduate, Part IB means second year undergraduate, Part II is third year undergraduate, Part III is fourth year undergraduate / Master’s student.

MIT Opencourseware — Resources, practice exercises and exams from MIT.

I’m a mathematics and philosophy enthusiast, who studies economics at Cambridge University. You can contact me in the comments or via my facebook page. If you want some guidance in how to improve in math, I’d be glad to help!

Edit: 28.08.2020 I’m just updating this article to say I have now succeeded in switching to maths. Yay 🙂