Here's a very simple problem whose solution was not obvious to me immediately. Indeed I tried several approaches before stumping into one that worked. After several failed attempts, I asked myself a question that helped me many times before: Have I used all the data?

The problem was posed to me by Irina Khmelnitskaya, Vice Principal of Gelfand's Outreach Program in Mathematics. Irina mentioned that Gelfand himself did not solve the problem right away either. Hence, the incentive.

(The number of yellow dots will automatically be set to the sum of the number of red and blue dots if the "Link" box is checked. Otherwise, the number of yellow dots may be set idependently.)

Copyright © 1996-2009 Alexander Bogomolny

Let's call the red and blue dots collectively magenta dots. Assume on the contrary that two magenta dots lie inside a yellow interval. Since yellow intervals are shorter than either red or blue ones, the two magenta dots must be of different colors: one red, the other blue. For the definiteness' sake, assume dots a/13 and b17 lie inside the interval (c/30, (c + 1)/30). Then the mediant fraction (a + b)/(13 + 17) = (a + b)/30 lies between a/13 and b/17, i.e. inside the interval (c/30, (c + 1 )/30), which is impossible. Contradiction.

Obviously, the problem can be generalized to arbitrary subdivisions into m red, n blue, and (m + n) yellow intervals as long as m and n are coprime.

The above proof is a proof by reductio ad absurdum. It's direct analog was suggested by W.McWorter.

Consider the combined sequence of red, blue, and yellow dots. May a red dot immediately follow another red dot? No, there bound to be a yellow dot in-between two successive red dots. This is because the yellow intervals are shorter than the red ones.

A blue dot can't follow another blue dot for the same reason. Can it follow a red dot, or vice versa? No, this, too, is impossible. The mediant of a red dot and a blue dot (which is a yellow dot) always squeezes in-between.

Now, we just saw that in the combined sequence of magenta and yellow dots, any two magenta dots are always separated by at least one yellow dot. There are m + n magenta dots and m + n - 1 open magenta intervals with no magenta dots in the interior. Not counting the terminal dots at 0 and 1, there are exactly m + n - 1 yellow dots. It thus follows that exactly 1 yellow dot falls into each of the magenta intervals. In other words, magenta and yellow dots interlace. Therefore, every yellow interval (excluding the terminal ones: the leftmost with the left endpoint at 0 and the rightmost with the right endpoint at 1) contains exactly 1 magenta dot.

Professor McWorter has also considered a generalization

The proof of the generalization is only slightly different from the case already discussed. Assume dots a/m and b/n are located in a yellow interval. Before forming the mediant, observe that a/m = ay/my and b/n = bz/nz. Now, the mediant (ay + bz)/(my + nz) = (ay + bz)/x is a yellow dot inside the yellow interval at hand. Contradiction.

Experimentation with the applet at the beginning of the page easily reveals that McWorter's condition (x = my + nz) is sufficient but not necessary for there being at most one magenta dot in every yellow interval. Nonetheless, as the following example shows, it can't be omitted altogether.

Let m = 8, n = 7, and x = 27. Obviously, 27 can't be written in the form 27 = 8y + 7z with positive y and z. Now, since 3/27 < 1/8 < 1/7 < 4/27, two magenta dots (1/8 and 1/7) fall inside a yellow interval (3/27, 4/27).

Let N < (m + n) be an integer. There are [N/(r + 1)] terms of the first sequence below N. ([x] is the whole part of x, i.e. the largest integer not exceeding x.)

Similarly, there are [N/(s + 1)] terms of the second sequence below N. Since neither N/(r + 1) or N/(s + 1) is an integer, we have two pairs of inequalities:

(*)	N/(r + 1) - 1 < [N/(r + 1)] < N/(r + 1), and N/(s + 1) - 1 < [N/(s + 1)] < N/(s + 1)

Now note that

With this in mind, let's sum up the inequalities (*):

N - 2 < [N/(r + 1)] + [N/(s + 1)] < N.

Since all quantities involved here are integers, we can claim an identity

[N/(r + 1)] + [N/(s + 1)] = N - 1,

which says that the two sequences total exactly N - 1 elements below N. This is true for any integer N < (m + n). If N is such that also N + 1 < (m + n), then there are exactly N terms of the two sequences that are less than N + 1. In other words, passing from N to N + 1 we add just 1 term in the union of the two sequences. The latter simply means that, between them, the two sequences have exactly 1 element between N and N + 1.

To finish the proof, scale the interval [1, m + n] into the unit interval [0, 1].

(This proof is an adaptation of a 1927 proof by A. Ostrowski and A.C. Eitken of a statement about complementary sequences. We met a pair of such sequence while analysing Wythoff's game. Two inscreasing sequences are complementary if their union covers the whole set of positive integers and each integer belongs to exactly one of the sequences.)

Copyright © 1996-2009 Alexander Bogomolny