Maths Olympiad Prep

Library / /14 of 18

Algebra Difficulty 5.4 AIME, harder Prove it United States

Problem:
Define a function ff on the real numbers by
f(x)={2x if x<1/22x1 if x1/2 f(x)= \begin{cases}2 x & \text{ if } x<1 / 2 \\ 2 x-1 & \text{ if } x \geq 1 / 2\end{cases}
Determine all values xx satisfying f(f(f(f(f(x)))))=xf(f(f(f(f(x)))))=x.

Solution

Solution:
The answer is the 32 values 0,131,231,,3031,10, \frac{1}{31}, \frac{2}{31}, \ldots, \frac{30}{31}, 1.

If x<0x<0, then f(x)=2x<xf(x)=2 x<x so the sequence x,f(x),f(f(x)),x, f(x), f(f(x)), \ldots is strictly decreasing and cannot return to xx.

If x>1x>1, similarly f(x)=2x1>xf(x)=2 x-1>x so the sequence x,f(x),f(f(x)),x, f(x), f(f(x)), \ldots is strictly increasing and cannot return to xx.

If x=1x=1, then f(x)=1f(x)=1 and we have 11 as a solution.

Finally, we assume that 0x<10 \leq x<1, so 0f(x)<10 \leq f(x)<1 as well. For simplicity let x0=xx_{0}=x and xn+1=f(xn)x_{n+1}=f\left(x_{n}\right) so the equation we are trying to solve is x5=x0x_{5}=x_{0}. Note that 2xnxn+12 x_{n}-x_{n+1} is an integer (either 00 or 11) for each nn, so
32x0x5=16(2x0x1)+8(2x1x2)+4(2x2x3)+2(2x3x4)+(2x4x5) 32 x_{0}-x_{5}=16\left(2 x_{0}-x_{1}\right)+8\left(2 x_{1}-x_{2}\right)+4\left(2 x_{2}-x_{3}\right)+2\left(2 x_{3}-x_{4}\right)+\left(2 x_{4}-x_{5}\right)
must be an integer as well. If we assume x5=x0x_{5}=x_{0} we deduce that 31x031 x_{0} is an integer. Conversely, if 31x031 x_{0} is an integer, then x5x0x_{5}-x_{0} is an integer and this integer must be 00 because 0x0,x5<10 \leq x_{0}, x_{5}<1. Thus the solutions in this range are exactly the multiples of 131\frac{1}{31}: 0,131,231,,30310, \frac{1}{31}, \frac{2}{31}, \ldots, \frac{30}{31}.

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.