|
|
 |
Условие
Для каждой пары действительных чисел a и b рассмотрим последовательность чисел pn = [2{an + b}]. Любые k подряд идущих членов этой последовательности назовем словом. Верно ли, что любой упорядоченный набор из нулей и единиц длины k будет словом последовательности, заданной некоторыми a и b при k = 4; при k = 5?
Примечание: [c] - целая часть, {c} - дробная часть числа c.
Решение
Будем изображать числа точками на окружности единичной длины (числам с одинаковой дробной частью соответствует одна и та же точка окружности, см. комментарий к решению задачи 6 для 10 класса олимпиады 1997 г.). Тогда последовательности xn = {an + b} соответствует последовательность точек на окружности, получаемых из {b} n-кратным поворотом на дугу {a}. При этом pn = [2xn].
Нетрудно видеть, что если
xn [0;
),
т. е. точка xn лежит на
верхней полуокружности, то pn = 0; если xn лежит на нижней
полуокружности, то pn = 1.
а) Построим последовательности pn, в которых встречаются все слова длины 4,
начинающиеся с нуля. Таких слов восемь. Остальные восемь слов можно
получить заменой (a, b) на
(a, b + ). Действительно, при такой замене
точки xn заменятся на диаметрально противоположные, так что pn
заменится на 1 - pn.
Примеры: Рассмотрим a и b, при которых последовательность xn образует правильные фигуры (см. таблицу).
| Правильные фигуры |
б) Докажем, что слово 00010 не реализуется ни при каких a и b. Пусть это слово реализуется. Рассмотрим три подряд идущих члена последовательности xn, xn + 1 и xn + 2.
Если точки xn и xn + 2 диаметрально противоположные, то следующая точка получается из предыдущей поворотом на 90o, и очевидно, что в последовательности pn не могут встретиться три нуля подряд.
Если точки xn и xn + 2 не диаметрально противоположные, то они делят окружность на две различные дуги. Возможны две ситуации: xn + 1 лежит на большей дуге (как на рис. , а), и xn + 1 лежит на меньшей дуге (как на рис. , б).
Пусть xn + 1 лежит на большей дуге, тогда любые другие точки xm, xm + 1 и xm + 2 расположены так же, так как они получаются из точек xn, xn + 1 и xn + 2 поворотом на один и тот же угол. Но тогда три такие точки не могут оказаться на верхней полуокружности, а значит, в последовательности pn слово 000 не встретится - противоречие.
Пусть xn + 1 лежит на меньшей дуге . Тогда любые точки xm, xm + 1 и xm + 2 расположены так же, поэтому если xm и xm + 2 лежат на верхней полуокружности, то и точка xm + 1 лежит там же, а значит, в последовательности pn не встретится слово 010.
Итак, мы разобрали все варианты, и доказали, что слово 00010 не может встретиться.
Комментарий. Если разбить pn на куски, состоящие только из нулей или только из единиц (причем за куском из нулей идет кусок из единиц, а за куском из единиц - кусок из нулей), то длины любых двух таких кусков будут отличаться не больше, чем на 1. Эта задача относится к символической динамике, о чем рассказано в статье [#!Smale-horseshoe!#].
