Often, when looking through solutions of difficult olympiad problems, one would wonder, how are you supposed to come up with something like that? The steps are numerous and each one seems to be the work of a wizard…
One book that I like is Solving Mathematical Problems – A Personal Perspective by Terrence Tao. It’s a problem book, but one that’s slightly different from the others. Instead of merely giving a solution to its problems, it gives some insight on the mathematician’s thoughts as he solves the olympiad problem, such that the steps seem reasonable and logical
Here I’m going to attempt dissecting a recent contest problem I encountered (from the Tournament of Towns contest a few weeks ago) in the style of Tao.
On a circular track, cyclists start in the same direction at the same time, all at different but constant speeds. No three cyclists meet at the same time. If two cyclists are at the same position on the track, we say they meet. Prove that by the time every pair of cyclists have met at least once, each cyclist has had at least meetings.
The problem seems confusing, with so much seemingly unrelated information. We can always start by drawing a picture:
This doesn’t seem to help that much. A circle suggests that the formula for the circumference – might come into play, but looking at the rest of the problem, this seems unlikely, because the problem (especially the result we try to prove) is combinatorial, not geometric.
Let’s go back and look at what we’re given. First, all of the cyclists have constant velocity. So we can write the constant velocities of each of the cyclists as . We are also given that all of the velocities are different. Then why not simplify things for ourselves by ordering the cyclists in order of increasing velocity, that is, ? At the same time, we’ll label the cyclists according to their velocities, so we have .
What else are we given? The number of cyclists is even, and no three cyclists meet at the same time. As there doesn’t seem to be much we can do to make use of these conditions, we can leave them aside for now.
Now if the length of the track is , then each cyclist goes around the track every units of time. The event only really ends when every pair of cyclists have met at least once – when does this happen? If we look at any two cyclists – and with being the faster cyclist – the two have a velocity difference of . Therefore cyclists and will meet every units of time.
But it isn’t over until this happens for every pair of cyclists – might be very large; in other words could be very small. Since we ordered in increasing velocity, the smallest value for should be between two adjacent cyclists. If we let be the smallest , then
Furthermore, we can now say that the event ends at time (from the start).
It seems that we are getting somewhere. But we haven’t really touched the point we’re trying to prove, that each cyclist has had meetings at this point. Let’s look at pairs of adjacent cyclists. If and are adjacent, then we know by definition that they must meet at least once in the time .
But what about non-adjacent cyclists? If and are separated by exactly one cyclist, , then and . Adding the two together gives , so they meet at least once every units of time. Equivalently, they meet at least twice in the time .
It follows that any pair of cyclists and meet at least every units of time, so they meet at least times in the course of the event.
We’re on home stretch here. How can use this new information to show that every cyclist has had meetings? Let’s look at any arbitrary cyclist, . In the event, he meets at least times with , at least times with , at least times with , and so on.
So the total number of times he meets is
All we have to do now is simplify:
since and are consecutive integers and their product must be positive. This concludes the proof.