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.
| Buy this applet What if applet does not run? |
(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.)
|Contact| |Front page| |Contents| |Algebra| |Up| |Store|
Copyright © 1996-2015 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 b/17 lie inside the interval
Obviously, the problem can be generalized to arbitrary subdivisions into m red, n blue, and
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
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
The case x = m + n has been discussed. So what about x greater than
What I can do is show that for every x of the form
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
Experimentation with the applet at the beginning of the page easily reveals that McWorter's condition (
Let m = 8, n = 7, and x = 27. Obviously, 27 can't be written in the form
Here's another proof of the same result.
Let r = m/n and s = n/m, where m and n are coprime. Consider two sequences of rational numbers
{i(r + 1): 0 < i} and {i(s + 1): 0 < 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. 
n
Let
Similarly, there are
| (*) |
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
To finish the proof, scale the interval
(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.)
Related material
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|Contact| |Front page| |Contents| |Algebra| |Up| |Store|
Copyright © 1996-2015 Alexander Bogomolny
| 49552151 |
