Maths Olympiad Prep

Library / /359 of 377

Algebra Difficulty 5.8 AIME, harder Prove it United States

Problem:
Let f:(0,1)(0,1)f:(0,1) \rightarrow (0,1) be a differentiable function with a continuous derivative such that for every positive integer nn and odd positive integer a<2na < 2^{n}, there exists an odd positive integer b<2nb < 2^{n} such that f(a2n)=b2nf\left(\frac{a}{2^{n}}\right) = \frac{b}{2^{n}}. Determine the set of possible values of f(12)f^{\prime}\left(\frac{1}{2}\right).

Solution

Solution:
Answer: {1,1}\{-1,1\}

The key step is to notice that for such a function ff, f(x)0f^{\prime}(x) \neq 0 for any xx.

Assume, for sake of contradiction, that there exists 0<y<10 < y < 1 such that f(y)=0f^{\prime}(y) = 0. Since ff^{\prime} is a continuous function, there is some small interval (c,d)(c, d) containing yy such that f(x)12|f^{\prime}(x)| \leq \frac{1}{2} for all x(c,d)x \in (c, d). Now there exists some n,an, a such that a2n,a+12n\frac{a}{2^{n}}, \frac{a+1}{2^{n}} are both in the interval (c,d)(c, d). From the definition,
f(a+12n)f(a2n)a+12na2n=2n(b2nb2n)=bb \frac{f\left(\frac{a+1}{2^{n}}\right) - f\left(\frac{a}{2^{n}}\right)}{\frac{a+1}{2^{n}} - \frac{a}{2^{n}}} = 2^{n}\left(\frac{b'}{2^{n}} - \frac{b}{2^{n}}\right) = b' - b
where b,bb, b' are integers; one is odd, and one is even. So bbb' - b is an odd integer. Since ff is differentiable, by the mean value theorem there exists a point where f=bbf^{\prime} = b' - b. But this point is in the interval (c,d)(c, d), and bb>12|b' - b| > \frac{1}{2}. This contradicts the assumption that f(x)12|f^{\prime}(x)| \leq \frac{1}{2} for all x(c,d)x \in (c, d).

Since f(x)0f^{\prime}(x) \neq 0, and ff^{\prime} is a continuous function, ff^{\prime} is either always positive or always negative. So ff is either increasing or decreasing. f(12)=12f\left(\frac{1}{2}\right) = \frac{1}{2} always. If ff is increasing, it follows that f(14)=14f\left(\frac{1}{4}\right) = \frac{1}{4}, f(34)=34f\left(\frac{3}{4}\right) = \frac{3}{4}, and we can show by induction that indeed f(a2n)=a2nf\left(\frac{a}{2^{n}}\right) = \frac{a}{2^{n}} for all integers a,na, n. Since numbers of this form are dense in the interval (0,1)(0,1), and ff is a continuous function, f(x)=xf(x) = x for all xx.

It can be similarly shown that if ff is decreasing, f(x)=1xf(x) = 1 - x for all xx. So the only possible values of f(12)f^{\prime}\left(\frac{1}{2}\right) are 1,1-1, 1.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.