Solving Mathematical Problems (TOT 2010 Senior, P2)

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.

The Problem

On a circular track, 2n 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 n^2 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 – C = \pi d 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 2n cyclists as v_1, v_2, \cdots, v_{2n}. 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, v_1 < v_2 < \cdots < v_{2n}? At the same time, we’ll label the cyclists according to their velocities, so we have C_1, C_2, \cdots, C_{2n}.

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 d, then each cyclist goes around the track every \frac{d}{v} 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 – C_i and C_j with C_j being the faster cyclist – the two have a velocity difference of v_j - v_i. Therefore cyclists C_i and C_j will meet every \frac{d}{v_j-v_i} units of time.

But it isn’t over until this happens for every pair of cyclists – \frac{d}{v_j-v_i} might be very large; in other words v_j - v_i could be very small. Since we ordered v_1, v_2, \cdots, v_{2n} in increasing velocity, the smallest value for v_j-v_i should be between two adjacent cyclists. If we let ube the smallest v_j - v_i, then

u = \mathrm{min} \{ v_2-v_1, v_3-v_2, \cdots, v_{2n} - v_{2n-1} \}

Furthermore, we can now say that the event ends at time \frac{d}{u} (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 n^2 meetings at this point. Let’s look at pairs of adjacent cyclists. If C_i and C_j are adjacent, then we know by definition that they must meet at least once in the time \frac{d}{u}.

But what about non-adjacent cyclists? If C_i and C_j are separated by exactly one cyclist, C_m, then v_m - v_i \geq u and v_j - v_m \geq u. Adding the two together gives v_j - v_i \geq 2u, so they meet at least once every \frac{d}{2u} units of time. Equivalently, they meet at least twice in the time \frac{d}{u}.

It follows that any pair of cyclists C_i and C_j meet at least every \frac{d}{u(j-i)} units of time, so they meet at least u(j-i) 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 n^2 meetings? Let’s look at any arbitrary cyclist, C_i. In the event, he meets at least i-1 times with C_1, at least i-2 times with C_2, at least 2n-i times with C_{2n}, and so on.

So the total number of times he meets is

\frac{i(i-1) + (2n-i)(2n-i+1)}{2}

All we have to do now is simplify:

\frac{i^2 - i + 4n^2 - 2ni + 2n - 2ni + i^2 - i}{2} \\= i^2 - i + 2n^2 - 2ni + n \\ = n^2 + (n-i)^2 + n - i \\ = n^2 + (n-i)(n-i+1) \geq n^2

since n-i and n-i+1 are consecutive integers and their product must be positive. This concludes the proof.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s