Олимпиадная задача: Слово в последовательности по Владимирову и Измайлову для 9–11 классов

Будем изображать числа точками на окружности единичной длины (числам с одинаковой дробной частью соответствует одна и та же точка окружности, см. комментарий к решению задачи 6 для 10 класса олимпиады 1997 г.). Тогда последовательностиx_n= {an+b} соответствует последовательность точек на окружности, получаемых из {b}n-кратным поворотом на дугу {a}. При этомp_n= [2x_n]. Нетрудно видеть, что если x_n $\in$ [0;${\frac{1}{2}}$), т. е. точка x_n лежит на верхней полуокружности, то p_n = 0; если x_n лежит на нижней полуокружности, то p_n = 1.

а) Построим последовательности p_n, в которых встречаются все слова длины 4, начинающиеся с нуля. Таких слов восемь. Остальные восемь слов можно получить заменой (a, b) на (a, b + ${\frac{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^o, и очевидно, что в последовательности p_n не могут встретиться три нуля подряд.

Если точки x_n и x_{n + 2} не диаметрально противоположные, то они делят окружность на две различные дуги. Возможны две ситуации: x_{n + 1} лежит на большей дуге (как на рис.  , а), и x_{n + 1} лежит на меньшей дуге (как на рис.  , б).

Пусть 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} лежит на меньшей дуге . Тогда любые точки x_m, x_{m + 1} и x_{m + 2} расположены так же, поэтому если x_m и x_{m + 2} лежат на верхней полуокружности, то и точка x_{m + 1} лежит там же, а значит, в последовательности p_n не встретится слово 010.

Итак, мы разобрали все варианты, и доказали, что слово 00010 не может встретиться.

Комментарий. Если разбить p_n на куски, состоящие только из нулей или только из единиц (причем за куском из нулей идет кусок из единиц, а за куском из единиц - кусок из нулей), то длины любых двух таких кусков будут отличаться не больше, чем на 1. Эта задача относится к символической динамике, о чем рассказано в статье [#!Smale-horseshoe!#].