Dots and Fractions

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 unit interval $[0, 1]\;$ is divided into $13\;$ equal parts by red dots, $17\;$ equal parts by blue dots, and $30\;$ equal parts by orange dots. Name the shortest open intervals of a subdivision by the color of their endpoints. Prove that no orange interval may contain more than $1\;$ dot of another color: either red or blue.

28 January 2016, Created with GeoGebra

(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.)

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 $\displaystyle\frac{a}{13}\;$ and $\displaystyle\frac{b}{17}\;$ lie inside the interval $\displaystyle\left(\frac{c}{30}, \frac{c + 1}{30}\right)\;$. Then the mediant fraction $\displaystyle\frac{a + b}{13 + 17} = \frac{a + b}{30}\;$ lies between $\displaystyle\frac{a}{13}\;$ and $\displaystyle\frac{b}{17},\;$ i.e. inside the interval $\displaystyle\left(\frac{c}{30}, \frac{c + 1 }{30}\right)\;$, 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. Its 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

What's so sacred about $m + n?\;$ Let $m\;$ and $n\;$ be coprime, and let $x\;$ be a positive integer. Divide the unit interval into $m\;$ equal parts with red dots, divide the unit interval into $n\;$ equal parts with blue dots, and divide the unit interval into $x\;$ equal parts with yellow dots. If $x \lt m + n\;$, then, by the pigeonhole principle, some pair of consecutive yellow dots contains at least two magenta dots between them. On the other hand, if $x \gt mn\;$, then no consecutive yellow dots contain more than one magenta dot between them because the closest two magenta dots can be is $\displaystyle\frac{1}{mn},\;$ which is larger than $\displaystyle\frac{1}{x}.$

The case $x = m + n\;$ has been discussed. So what about $x\;$ greater than $m + n\;$ but less or equal $mn?\;$

What I can do is show that for every $x\;$ of the form $x = my + nz\;$, where $y\;$ and $z\;$ are positive integers, there is at most one magenta dot between consecutive yellow dots. So, in one sense, $m + n\;$ is not sacred because all $x\;$ of the above form work. In another sense, $x = m + n\;$ is sacred because it is the only $x\;$ for which there is exactly one magenta dot between consecutive yellow dots (other than the first and last consecutive pairs which have no magenta dots in between), or, less significantly, $m + n\;$ is sacred because $x = m + n\;$ is the smallest $x\;$ which works.

The proof of the generalization is only slightly different from the case already discussed. Assume dots $\displaystyle\frac{a}{m}\;$ and $\displaystyle\frac{b}{n}\;$ are located in a yellow interval. Before forming the mediant, observe that $\displaystyle\frac{a}{m} = \frac{ay}{my}\;$ and $\displaystyle\frac{b}{n} = \frac{bz}{nz}\;$. Now, the mediant $\displaystyle\frac{ay + bz}{my + nz} = \frac{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 $\displaystyle\frac{3}{27} \lt \frac{1}{8} \lt \frac{1}{7} \lt \frac{4}{27}\;$, two magenta dots $\displaystyle\left(\frac{1}{8}\;\text{and}\;\frac{1}{7}\right)\;$ fall inside a yellow interval $\displaystyle\left(\frac{3}{27}, \frac{4}{27}\right).\;$

Here's another proof of the same result.

Let $\displaystyle r = \frac{m}{n}\;$ and $\displaystyle s = \frac{n}{m},\;$ where $m\;$ and $n\;$ are coprime. Consider two sequences of rational numbers

$\{i(r + 1):\;0 \lt i\}\;$ and $\{i(s + 1):\;0 \lt i\}.$

In both sequences, $m + n\;$ is the first integer. This is because, as we assumed, $m\;$ and $n\;$ are coprime. From here, $m + n\;$ and $n\;$ are also coprime. $\displaystyle\frac{i(m + n)}{n}\;$ may only be an integer for $i \ge n\;$ and similarly for the second sequence. For the same reason, the two sequences have no common elements below $m + n.\;$

Let $N \lt (m + n)\;$ be an integer. There are $\displaystyle\left\lfloor\frac{N}{r + 1}\right\rfloor\;$ terms of the first sequence below $N.\;$ $(\lfloor x\rfloor$ is the whole part (floor function) of $x,\;$ i.e. the largest integer not exceeding $x.)\;$

Similarly, there are $\displaystyle\left\lfloor\frac{N}{s + 1}\right\rfloor\;$ terms of the second sequence below N. Since neither $\displaystyle\frac{N}{r + 1}\;$ or $\displaystyle\frac{N}{s + 1}\;$ is an integer, we have two pairs of inequalities:

(*)

$\displaystyle\frac{N}{r + 1} - 1 \lt \left\lfloor \frac{N}{r + 1}\right\rfloor \lt \frac{N}{r + 1},\;$ and
$\displaystyle\frac{N}{s + 1} - 1 \lt \left\lfloor \frac{N}{s + 1}\right\rfloor \lt \frac{N}{s + 1}.$

Now note that

$\displaystyle\frac{1}{r+1}+\frac{1}{s+1}=\frac{n}{m+n}+\frac{m}{m+n}=1.$

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

$\displaystyle N - 2 \lt \left\lfloor\frac{N}{r + 1}\right\rfloor + \left\lfloor\frac{N}{s + 1}\right\rfloor \lt N.$

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

$\displaystyle\left\lfloor\frac{N}{r + 1}\right\rfloor + \left\lfloor\frac{N}{s + 1}\right\rfloor = N - 1,$

which says that the two sequences total exactly $N - 1\;$ elements below $N.\;$ This is true for any integer $N \lt (m + n)\;$. If $N\;$ is such that also $N + 1 \lt (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.)

[an error occurred while processing this directive]