Последовательность Туэ-Морса: определение и свойства

Последовательность Туэ-Морса - это бесконечная последовательность из нулей и единиц, которая начинается так: 0, 1, 1, 0, 1, 0, 0, 1, ... Несмотря на то что она состоит всего из двух символов, у неё удивительно богатые свойства: она не периодична, не содержит трёх одинаковых блоков подряд и при этом строится по простому правилу. Её придумали независимо несколько математиков (Туэ, Морс, ещё раньше Пруэ), и сегодня она встречается в комбинаторике слов, теории чисел и даже в задаче о справедливом дележе. Ниже разберём два эквивалентных определения последовательности Туэ-Морса, формулу для члена $t(n)$, её первые члены и ключевые свойства. Чтобы сразу почувствовать, как устроен этот ряд, покрутите калькулятор ниже: он считает любой член по двоичной записи, рисует ленту и показывает, как очередь Туэ-Морса делит предметы почти поровну.

Определение через двоичную запись

Самое короткое определение последовательности Туэ-Морса работает через двоичную систему счисления. Член с номером $n$ (нумерация с нуля) определяется так:

$t(n) = \left(\text{число единиц в двоичной записи } n\right) \bmod 2.$

Другими словами, $t(n)$ равно нулю, если в двоичной записи числа $n$ чётное количество единиц, и единице, если нечётное. Эту величину называют чётностью числа единиц, или цифровой суммой по модулю два.

Возьмём $n = 11$. В двоичной системе $11 = 1011_2$, здесь три единицы, число нечётное, поэтому $t(11) = 1$. А для $n = 23 = 10111_2$ единиц уже четыре, число чётное, значит $t(23) = 0$. Так, член за членом, можно вычислить всю последовательность.

Рассчитать для своей задачи

На схеме показан именно этот шаг: двоичные разряды числа 11, выделенные единичные разряды и вывод про чётность. Такой расчёт легко проделать для любого номера вручную, а калькулятор выше делает его мгновенно и сразу подсвечивает нужный член на ленте.

Определение через подстановку

Тот же ряд получается совершенно другим способом - без всякой двоичной записи. Возьмём один символ 0 и будем многократно применять к каждому символу правило подстановки:

$0 \to 01, \qquad 1 \to 10.$

На каждом шаге каждый ноль заменяется парой 01, а каждая единица - парой 10. Начнём с 0 и проследим несколько поколений:

Рассчитать для своей задачи

• поколение 0: 0;
• поколение 1: 01;
• поколение 2: 0110;
• поколение 3: 01101001;
• поколение 4: 0110100110010110.

Каждое следующее поколение начинается с предыдущего, поэтому в пределе получается одна бесконечная последовательность. И она в точности совпадает с той, что мы строили по двоичной записи. Это не совпадение: применение подстановки к номеру $n$ устроено так же, как добавление младшего бита, поэтому оба определения дают один ряд. Длина $k$-го поколения равна $2^k$ - последовательность растёт вдвое быстрее на каждом шаге, и в этом её самоподобие.

Рекуррентная формула

Из двоичного определения выводится удобная рекуррентная формула. Чтобы получить двоичную запись числа $2n$, к записи $n$ дописывают ноль справа - число единиц не меняется. А для $2n+1$ дописывают единицу - число единиц увеличивается на один, и чётность переключается. Отсюда:

$t(0) = 0, \qquad t(2n) = t(n), \qquad t(2n+1) = 1 - t(n).$

Эта формула удобна для программирования и для индуктивных доказательств: член с чётным номером повторяет член с вдвое меньшим номером, а член с нечётным номером - его противоположность. По ней же видно, почему последовательность Туэ-Морса так тесно связана со степенями двойки.

Первые члены и лента

Выпишем первые шестнадцать членов последовательности Туэ-Морса (нумерация с нуля):

$0,\ 1,\ 1,\ 0,\ 1,\ 0,\ 0,\ 1,\ 1,\ 0,\ 0,\ 1,\ 0,\ 1,\ 1,\ 0.$

Заметьте симметрию: вторая половина этого отрезка - это первая половина, в которой нули и единицы поменяли местами. Так и должно быть по правилу подстановки: блок длины $2^k$ порождается из блока вдвое короче, а его «зеркальное» дополнение идёт следом. В калькуляторе выше лента раскрашена по значению, синие столбики - нули, красные - единицы, и выбранный вами номер подсвечивается золотом, если попадает в показанное окно.

Свойства: непериодичность и кубсвободность

Главная причина, по которой Туэ ввёл эту последовательность, - её бесповторность. Последовательность Туэ-Морса обладает двумя важными свойствами.

Во-первых, она не периодична: в ней нет такого хвоста, который повторялся бы с постоянным периодом. Если бы период существовал, он противоречил бы рекуррентной формуле и самоподобной структуре блоков.

Во-вторых, она кубсвободна: в ней нет трёх одинаковых блоков подряд, то есть нет фрагмента вида $www$, где $w$ - любое непустое слово. Более того, она бесповторна в сильном смысле (не содержит так называемых перекрытий $axaxa$). Именно поэтому последовательность Туэ-Морса служит классическим примером бесконечного слова без коротких повторов над двухбуквенным алфавитом - а доказать, что такое слово вообще существует, далеко не очевидно.

Применение: справедливый делёж

У последовательности Туэ-Морса есть наглядное практическое применение - справедливое распределение по очереди. Представьте, что два игрока по очереди разбирают предметы разной ценности, и нужно, чтобы суммы у обоих оказались близкими. Если брать предметы строго по очереди (A, B, A, B, ...), у первого окажется перевес. А если назначить очередь по последовательности Туэ-Морса (0 - берёт A, 1 - берёт B), распределение получается заметно справедливее.

Это свойство связано с тождеством Пруэ: если разбить числа от $0$ до $2^{k}-1$ на две группы по последовательности Туэ-Морса, то суммы первых, вторых и так далее степеней в обеих группах совпадают. В калькуляторе выше нижний график показывает баланс - разность сумм двух игроков, когда предметы ценностью $1, 2, 3, \dots$ раздаются по очереди Туэ-Морса. Линия не уходит далеко от нуля и точно обнуляется на каждой степени двойки (золотые точки), тогда как простое чередование давало бы устойчивый перевес.

Частые ошибки

• Путают нумерацию с нуля и с единицы. В формуле $t(n)$ номер $n$ обычно отсчитывается от нуля: $t(0) = 0$. Если начать с единицы, члены сдвинутся, и ответы перестанут сходиться с таблицами.
• Считают единицы в десятичной записи вместо двоичной. Чётность берётся именно от числа единиц в двоичном представлении $n$, а не от самих цифр числа.
• Думают, что ряд периодичен. Первые члены 0, 1, 1, 0 могут навести на мысль о периоде, но дальше структура ломается: последовательность Туэ-Морса непериодична.
• Считают дружественную очередь A, B, A, B справедливой. Простое чередование даёт перевес одному игроку, а очередь Туэ-Морса выравнивает суммы.
• Забывают, что подстановка и двоичное определение эквивалентны. Это один и тот же ряд, а не два разных; их полезно сверять друг с другом.

FAQ

Чему равен член последовательности Туэ-Морса с номером 100? Число $100 = 1100100_2$, в нём три единицы, число нечётное, поэтому $t(100) = 1$. Тот же ответ даёт подстановка, если развернуть последовательность до сотого члена.

Чем последовательность Туэ-Морса отличается от просто чередования 0, 1, 0, 1? Чередование периодично и содержит сколь угодно длинные повторы. Последовательность Туэ-Морса непериодична и кубсвободна: в ней нет трёх одинаковых блоков подряд, хотя строится она тоже по простому правилу.

Где применяется последовательность Туэ-Морса? В комбинаторике слов как пример бесповторного слова, в теории чисел через тождество Пруэ, в задачах справедливого дележа и распределения очереди, а также в теории динамических систем и фрактальной геометрии из-за самоподобия.

Коротко

Последовательность Туэ-Морса 0, 1, 1, 0, 1, 0, 0, 1, ... определяется двумя эквивалентными способами: член $t(n)$ равен чётности числа единиц в двоичной записи $n$, и тот же ряд получается подстановкой $0 \to 01$, $1 \to 10$ из одного символа. Рекуррентно $t(2n) = t(n)$, $t(2n+1) = 1 - t(n)$. Главные свойства - непериодичность и кубсвободность, а самое наглядное применение - справедливый делёж, где очередь Туэ-Морса выравнивает суммы двух игроков. Калькулятор выше считает любой член по двоичной записи и показывает оба свойства на живых графиках.