Последовательность Туэ-Морса и многочлены

Недавно я встретил неожиданное появление последовательности Туэ-Морса (или Морса-Туэ) в задаче, которая, на первый взгляд, вообще не имеет решения. Такое камео показалось мне интересным, и я решил описать его в этой статье.

Постановка задачи

Требуется разбить отрезок на белые и черные подотрезки так, чтобы для произвольного многочлена степени не более сумма приростов значения на белых отрезках равнялась сумме приростов на чёрных отрезках.
Прирост на отрезке равен .

Решение

Для начала введём несколько обозначений:

• - многочлен степени не более чем .

• Назовем потенциалом раскраски для многочлена, разность между суммой его приростов на чёрных и суммой приростов на белых подотрезках.

• - потенциал раскраски отрезка способом , для многочлена , в записи может сокращаться до .

• - искомый способ раскраски отрезка, такой что для любого многочлена , , верно .

• - способ раскраски отрезка, противоположный (все белые отрезки делаем черными и наоборот). Тогда .

Описывая раскраску, будем использовать запись такого вида: - разбить раскрашиваемый отрезок на 5 равных подотрезков, каждый из которых раскрасить в белый или черный цвет соответственно.



- конкатенация раскрасок

Свойство 0 (Аддитивность 𝜋)

Аддитивность несложно выводится из определения потенциалa:

Лемма 1

Рассмотрим многочлен .
Тогда по определению .

Лемма 2

Пусть

;
;

Тогда используя Свойство 0 и определение , получим необходимое равенство:

Доказав аддитивность и эти 2 леммы, можно составить алгоритм нахождения

Нахождение раскрасок

Будем по индукции находить раскраску для многочленов степени не более по раскраске для степеней не более .

База

Для многочленов степени не больше подходящей раскраской является

Переход

Пусть мы знаем раскраску и хотим найти раскраску .
Утверждается что подходящей является .

Докажем что это так:

Итог

Задача решена. Мы научились находить раскраску для многочленов любой степени.

Вот они для нескольких первых степеней:

;
;
;
;
;

Полученные раскраски и являются префиксами небезызвестной последовательности Туэ-Морса.

Так что, мы можем получить решение и ещё одной задачи.

Каким образом нужно разбить луч на белые и чёрные отрезки, чтобы сумма приростов любого многочлена на белых отрезках равнялась сумме приростов на черных отрезках?