2019-05-26
Для каждой пары действительных чисел $a$ и $b$ рассмотрим последовательность чисел $p_{n} = [2 \{an + b \}]$. Любые $k$ подряд идущих членов этой последовательности назовем словом. Верно ли, что любой упорядоченный набор из нулей и единиц длины $k$ будет словом последовательности, заданной некоторыми $a$ и $b$ при $k = 4$; при $k = 5$?
Примечание: $[c]$ - целая часть, $\{c\}$ - дробная часть числа $c$.
Решение:
Будем изображать числа точками на окружности единичной длины (числам с одинаковой дробной частью соответствует одна и та же точка окружности). Тогда последовательности $x_n = \{ an + b \}$ соответствует последовательность точек на окружности, получаемых из $\{ b \}$ $n$-кратным поворотом на дугу $\{ a \}$. При этом $p_n = [2x_n]$.
Нетрудно видеть, что если $x_n \in [0; 1/2)$, т. е. точка $x_n$ лежит на верхней полуокружности, то $p_n =0$; если $x_n$ лежит на нижней полуокружности, то $p_n = 1$.
а) Построим последовательности $p_n$, в которых встречаются все слова длины 4, начинающиеся с нуля. Таких слов восемь. Остальные восемь слов можно получить заменой $(a, b)$ на $(a, b + 1/2)$. Действительно, при такой замене точки $x_n$ заменятся на диаметрально противоположные, так что $p_n$ заменится на $1-p_n$.
Примеры: Рассмотрим $a$ и $b$, при которых последовательность $x_n$ образует правильные фигуры (см. таблицу).
б) Докажем, что слово 00010 не реализуется ни при каких $a$ и $b$. Пусть это слово реализуется. Рассмотрим три подряд идущих члена последовательности $x_n, x_n+1 и x_n+2$.
Если точки $x_n$ и $x_n+2$ диаметрально противоположные, то следующая точка получается из предыдущей поворотом на $90^{\circ}$, и очевидно, что в последовательности $p_n$ не могут встретиться три нуля подряд.
Если точки $x_n$ и $x_n+2$ не диаметрально противоположные, то они делят окружность на две различные дуги. Возможны две ситуации: $x_n+1$ лежит на большей дуге (как на рис. 31, а), и $x_n+1$ лежит на меньшей дуге (как на рис. 31, б).
Пусть $x_n+1$ лежит на большей дуге, тогда любые другие точки $x_m, x_m+1$ и $x_m+2$ расположены так же, так как они получаются из точек $x_n, x_n+1$ и $x_n+2$ поворотом на один и тот же угол. Но тогда три такие точки не могут оказаться на верхней полуокружности, а значит, в последовательности $p_n$ слово 000 не встретится - противоречие.
Пусть $x_n+1$ лежит на меньшей дуге $\check{x_nx_n+2}$. Тогда любые точки $x_m, x_m+1$ и $x_m+2$ расположены так же, поэтому если $x_m$ и $x_m+2$ лежат на верхней полуокружности, то и точка $x_m+1$ лежит там же, а значит, в последовательности $p_n$ не встретится слово 010.
Итак, мы разобрали все варианты, и доказали, что слово 00010 не может встретиться.
Комментарий. Если разбить $p_n$ на куски, состоящие только из нулей или только из единиц (причем за куском из нулей идет кусок из единиц, а за куском из единиц - кусок из нулей), то длины любых двух таких кусков будут отличаться не больше, чем на 1. Эта задача относится к символической динамике.
Ответ: При $k=4$ верно, при $k=5$ неверно.