Метка: периодическая траектория

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

Задача из журнала «Квант» (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) показаны на рисунке:

1picture

Поэтому если точка 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 )? Мы предлагаем читателям подумать над этим и постараемся вернуться к этой теме, получив ваши ответы.
Н.Васильев