M1443. О периодичности некоторой бесконечной последовательности

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

Условие

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

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

Решение

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

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

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

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

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

1picture

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

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

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