
Let F(x) be a nondecreasing function for all x in [0 1], such that
2F(x/3)=F(x) and F(x)+F(1x)=1
1. Find F(173/1993) and F(1/13).
2. If possible give a general algorithm to find F(x) for any x.
Other questions:
3. Is F(x) uniquely determined(in [0,1])?
4. Is F(x) continuous(in [0,1])?
Source: unknown
1. F(173/1993) = 3/16, and F(1/13) = 1/7.
2. Here's the algorithm to find F(x) given x:
1. Express x in base 3.
2. Searching from the left, if any trigit is 1, increase it to 2, and then truncate the base3 representation after that trigit.
(The result after step 2 is a base3 number between 0 and 1, inclusive, containing only 0's and 2's.)
3. Replace all the "2" trigits with "1".
4. Reevaluate the number as a base 2 number. This is F(x).
3 and 4. Yes. Starting with the interval [0,1], and repeatedly dividing it into thirds, we get a dense set of xvalues (the endpoints of the successively smaller intervals) for which F(x) is uniquely determined. Since F is nondecreasing, the values of F between those endpoints must be between the values of F at the endpoints. So F is continuous.
Here's a graph of F:
Proof that F(0)=0: From the definition of F, it follows that if
F(x)=y, then F(x/3)=y/2, and F(1/2)=1/2,
so for any positive integer, k, F(3^{k}/2)=2^{k}/2.
Suppose F(0)=ε, where ε>0. Then an integer, k, exists such that 2^{k}/2>ε,
and so F(3^{k}/2)<F(0), a contradiction.
Corollary: F(1)=1.
Repeatedly dividing the interval into thirds: From facts presented thus far, it follows that F(1/3)=F(2/3)=1/2, dividing the unit interval into thirds. F is constant on the middle third, so there's no need to divide it further, but each of the two other thirds can be divided further into thirds, giving us
F(1/9)=F(2/9)=1/4, and
F(7/9)=F(8/9)=3/4
So you can see that the middle third is a "plateau" after each successive division of an interval. That is, F(x) is constant for all values of x that fall into a middle interval.
Expressing x in base 3 and F(x) in base 2, we see:
F(0.1_{3})=F(0.2_{3})=0.1_{2},
F(0.01_{3})=F(0.02_{3})=0.01_{2},
F(0.21_{3})=F(0.22_{3})=0.11_{2},
F(0.001_{3})=F(0.002_{3})=0.001_{2},
F(0.021_{3})=F(0.022_{3})=0.011_{2},
F(0.201_{3})=F(0.202_{3})=0.101_{2},
F(0.221_{3})=F(0.222_{3})=0.111_{2},
Each digit of the base3 representation of a number, x, identifies which third of each of the successive divisions the number falls into. If the n'th digit of x (in base 3) is 1, then x falls in the middle third of the unit interval after it has been divided n times. For example, if x=0.202211202..._{3}, the fifth digit is 1, and so x falls in the middle third of an interval that is the fifth successive division of the unit interval into thirds. All the numbers between 0.20221_{3} and 0.20222_{3} fall in this interval, so F(x)=F(0.20221_{3})=F(0.20222_{3}). From this, it is clear that upon encountering the first 1 in the base3 representation of x, the number can be truncated after that trigit, and then the trigit can be changed to 2 without affecting the value of F(x). Then, the value of F(x) is obtained by changing each "2" in x's base3 representation to "1", and reinterpreting the number as a binary number.
173/1993 is between 0.0021_{3} and 0.0022_{3}, so F(173/1993) = F(0.0022_{3}) = 0.0011_{2} = 3/16
Repeating Fractions in Base 3: 1/13 is a bit trickier, because in base 3 it's a repeating "decimal" (using the term loosely) that has no 1's. To explore repeating decimals in base 3, I would like to start with a review of an infinite geometric series. Why? If you think about it, you will realize that a repeating decimal in any base is a geometric series. Perhaps you recall that
x^{1} + x^{2} + x^{3} + ... = 1/(x1)
If not, then refresh your memory this way:
Let S = x^{1} + x^{2} + x^{3} + ...
Then xS = 1 + x^{1} + x^{2} + ...
And xSS = 1, and then by dividing both sides by x1,
we see that S = 1/(x1)
Now, if x is a power of 3 then the sum, S, which equals 1/(x1), can be expressed very neatly as a repeating fraction. For example, when x=3, 1/(31) = 1/2 = 0.111..._{3}. When x=9, 1/(91) = 1/8 = 0.010101..._{3}. And when x=27, 1/(271) = 1/26 = 0.001001001..._{3}.
What does this have to do with 1/13? Well, 1/13 = 2/26 = 2/(271) =
0.002002002..._{3}.
So F(1/13) = 0.001001001..._{2} = 8^{1} + 8^{2} + 8^{3}
+ ... = 1/(81) = 1/7.
Can F be extended in a sensible way so that it is defined over the domain of all nonnegative real numbers?
Can F be extended to negative reals? Complex numbers?
What features or characteristics of F do you try to preserve when extending the function?
What are some of the problems you encounter when you try to extend F? How do you overcome these problems?
Wikipedia: Cantor function
Cuttheknot: Cantor Set and Function  A continuous function may grow considerably virtually without changing.
(none)
The webmaster and author of this Math Help site is Graeme McRae.