The title of this post is a nod to Terry Tao’s four mini-polymath discussions, in which IMO questions were solved collaboratively online. As the beginning of what I hope will be a long exercise in gathering data about how humans solve these kinds of problems, I decided to have a go at one of this year’s IMO problems, with the idea of writing down my thoughts as I went along. Because I was doing that (and doing it directly into a LaTeX file rather than using paper and pen), I took quite a long time to solve the problem: it was the first question, and therefore intended to be one of the easier ones, so in a competition one would hope to solve it quickly and move on to the more challenging questions 2 and 3 (particularly 3). You get an average of an hour and a half per question, and I think I took at least that, though I didn’t actually time myself.
What I wrote gives some kind of illustration of the twists and turns, many of them fruitless, that people typically take when solving a problem. If I were to draw a moral from it, it would be this: when trying to solve a problem, it is a mistake to expect to take a direct route to the solution. Instead, one formulates subquestions and gradually builds up a useful bank of observations until the direct route becomes clear. Given that we’ve just had the football world cup, I’ll draw an analogy that I find not too bad (though not perfect either): a team plays better if it patiently builds up to an attack on goal than if it hoofs the ball up the pitch or takes shots from a distance. Germany gave an extraordinary illustration of this in their 7-1 defeat of Brazil.
I imagine that the rest of this post will be much more interesting if you yourself solve the problem before reading what I did. I in turn would be interested in hearing about other people’s experiences with the problem: were they similar to mine, or quite different? I would very much like to get a feel for how varied people’s experiences are. If you’re a competitor who solved the problem, feel free to join the discussion!
If I find myself with some spare time, I might have a go at doing the same with some of the other questions.
What follows is exactly what I wrote (or rather typed), with no editing at all, apart from changing the LaTeX so that it compiles in WordPress and adding two comments that are clearly marked in red.
Problem Let be an infinite sequence of positive integers. Prove that there exists a unique integer such that
The expression in the middle is not an average. If we were to replace it by an average we would have the second inequality automatically.
Proof discovery technique.
Try looking at simple cases. Here we could consider what happens when , for example. Then the inequality says
Here we automatically have the first inequality, but there is no reason for the second inequality to be true.
Putting those observations together, we see that the first inequality is true when , and the second inequality is “close to being true” as gets large, since it is true if we replace by in the denominator.
If the inequality holds for a unique , then a plausible guess is that the first inequality fails at some and if is minimal such that it fails, then both inequalities are true for . I shall investigate that in due course, but I have another idea.
It is clear that WLOG . Can we now choose in such a way that we always get equality for the second inequality? We can certainly solve the equations, so the question is whether the resulting sequence will be increasing.
We get , so I’d better set and then continue constructing a sequence.
So , , , and so on. Thus all the with are equal, which they are not supposed to be. This feels significant.
Out of interest, what happens to the inequalities when we (illegally) take the above sequence? We get , so we get equality on both sides except when when we get .
Proof discovery technique.
Try to disprove the result.
Proof discovery subtechnique.
Try to find the simplest counterexample you can.
An obvious thing to do is to try to make the inequality true when and when . So let’s go. Without loss of generality , . We now need .
For we need . That can be rearranged to , exactly contradicting what we had before.
That doesn’t solve the problem but it looks interesting. In particular, it suggests rearranging the first inequality in the general case, to
That’s quite nice because the right hand side is a genuine average this time.
Actually, if getting an average is what we care about, we could also rearrange the first inequality by simply multiplying through by , which gives
I think it is time to revisit that guess, in order to try to prove at least that there exists a solution. So we know that the first inequality holds when , since all it says then is that . Can it always hold? If so, then again WLOG and , and after that we get , , etc.
Let’s write and for . Then we have , , , etc. We also require .
Let’s set . Now the first condition becomes but . Is that possible?
Is it possible with equality? WLOG . Then we have , , , etc.
I’m starting to wonder whether the integer must be something like 1 or 2. Let’s think about it. We know that . If then we have our . Suppose instead that . Then , so . Now if then we are again done, so suppose that .
But since , we can simply insert in between the two. Why can’t we continue doing that kind of thing? Let me try.
If , then , so we can insert in between the two.
I seem to have disproved the result, so I’d better see where I’m going wrong. I’ll try to construct a sequence explicitly. I’ll take , . I need , so I’ll take . Now I need , so I’ll take . Now I need , so I’ll take .
I don’t seem to be getting stuck, so let me try to prove that I can always continue. Suppose I’ve already chosen . Then the condition I need is that
By induction we already have that , from which it follows that and therefore that . We may therefore find between these two numbers, as desired.
You idiot Gowers, read the question: the have to be positive integers.
Fortunately, the work I’ve done so far is not a complete waste of time. [The half-conscious thought in the back of my mind here, which is clearer in retrospect, was that the successive differences in the example I had just constructed were getting smaller and smaller. So it seemed highly likely that using the same general circle of thoughts I would be able to prove that I couldn’t take the to be integers.]
Here’s a trivial observation: if the second inequality fails, then . So if , then . How long can we keep that going with positive integers? Answer: for ever, since we can take .
Never mind about that. I want to go back to an earlier idea. [It isn’t obvious what I mean by “earlier idea” here. Actually, I had earlier had the idea of defining the as below, but got distracted by something else and ended up not writing it down. So a small part of the record of my journey to the proof is missing.] It is simply to define and for . Then for if the first inequality holds we have
So each new is less than the average of the up to that , and hence less than the average of the before that . But that means that the average of the forms a decreasing sequence. That also means that the are bounded above by , something I could have observed ages ago. So they can’t be an increasing sequence of integers.
I’ve now shown that the first inequality must fail at some point. Suppose is the first point at which it fails. Then we have
The second inequality tells us that exceeds the average of , which implies that it exceeds the average of . That gives us the inequality
So now I’ve proved that there exists an integer such that the inequalities both hold. It remains to prove uniqueness. This formulation with the ought to help. We’ve picked the first point at which is at least as big as the average of . Does that imply that is at least as big as the average of ? Yes, because is at least as big as that average, and is bigger than . In other words, we can prove easily that if the first inequality fails for then it fails for , and hence by induction for all .