Задача из журнала «Квант» (1994, №4)

Условие

Бесконечная последовательность чисел $x_{n}$ определяется условиями:$x_{n+1}=1-\left | 1-2x_{n} \right |$, причем $0\leq x_{1}\leq 1$.

1. Докажите, что последовательность, начиная с некоторого места, периодическая в том и только в том случае, если $x_{1}$ рационально.
2. Сколько существует значений $x_{1}$, для которых эта последовательность — периодическая с периодом T ( для каждого T = 2, 3 $\cdots$ )?

Решение

Положим $f(x)=1-\left | 1-2x \right |$, $f_{n}(x)=\overset{n}{\overbrace{f((\cdots(f}}(x))\cdots))$.

Пусть $x_{1}$ — рациональное число (несократимая дробь вида p/q, где $q=2^{m}(2r-1)$, m и r целые, $m\geq 0$). Тогда $f(x_{1})$ — тоже рациональное, причем его знаменатель не больше, чем у $x_{1}$ (точнее, он тот же, если m=0, и вдвое меньше, если m>0), причем если $0\leq x_{1}<1$, то $0\leq f(x_{1})\leq 1$. Точно так же, числа $f_{n}(x_{1})$ будут рациональными, со знаменателем не больше, чем у $x_{1}$, и лежащими на отрезке $\left [ 0,1 \right ]$. Но таких чисел конечное число, и значит, среди них встретятся одинаковые:

$f_{n}(x_{1})=f_{n+T}(x_{1})$ при некоторых n и T, так что последовательность $f_{n}(x_{1})$, начиная с некоторого n, — периодическая.

Докажем обратное утверждение. Заметим, что функция y=f(x) на  каждом из отрезков $\left[0;\frac{1}{2}\right]$ и $\left[\frac{1}{2};1\right]$ — линейная:
$y=2x$ при $0\leq x\leq \frac{1}{2}$, $y=2-2x$ при $\frac{1}{2}\leq x\leq 1$.

Точно так же, функции $y=f_{n}(x)$ на каждом из отрезков $\left[\frac{k}{2^{n}};\frac{k+1}{2^{n}}\right]$ — линейная (причем $f_{n}(x)=a_{n}x+b_{n}$, где $a_{n}$, $b_{n}$ — целые, $a_{n}=\pm 2^{n}$); графики функций $y=f(x)$, $y=f_{2}(x)$, $y=f_{3}(x)$ показаны на рисунке:

Поэтому если точка x порождает «периодическую траекторию»: $f_{T}(x)=x$ при некотором $T\geq 1$, то x —  корень уравнения $x=a_{T}x+b_{T}$, т.е. число рациональное. Остается еще заметить, что любое y, $0\leq y< 1$, имеет $2^{n}$ «прообразов» при отображении $x\rightarrow f_{n}(x)$, т.е. уравнение $f_{n}(x)=y$ имеет $2^{n}$ решений, причем если y — рациональное, то и все эти решения рациональные. Поэтому если $y=f_{n}(x_{1})=f_{n+T}(x_{1})$ для некоторого $x_{1}$ (т.е. y порождает периодическую траекторию), то и y, и $x_{1}$ — рациональны.

Тем самым, оба утверждения первого пункта доказаны. Что касается второго пункта, как он поставлен в условии задачи, — ответ на него очень прост: таких точек бесконечно много для каждого T. В самом деле, существует (для каждого T=2,3,$\cdots$) по крайней мере одна точка периода ровно T : это, в частности, «последняя» точка пересечения отрезка $x=y$, $0\leq x< 1$, с графиком $y=f_{n}(x)$: $x_{T}=2^{T}/(2^{T}+1)$. (Ясно, что при k<T все решения уравнения $x=f_{k}(x)$ меньше $x_{T}$.) Тогда, взяв в роли $x_{1}$, любой из $2^{n}$ прообразов $x_{T}$ при отображении $x\rightarrow f_{n}(x)$ (лишь один из них входит в «периодическую траекторию» порождаемую $x_{T}$), мы получим последовательность, которая, начиная с некоторого места, — периодическая с периодом T.

Более интересный вопрос: сколько существует периодических траекторий каждого периода T ( или, что почти тоже самое, — точек x, для которых $x=f_{T}(x)$ и при этом $x\neq f_{k}(x)$ при k<T )? Мы предлагаем читателям подумать над этим и постараемся вернуться к этой теме, получив ваши ответы.
Н.Васильев