A1exYY 16 июл в 17:16

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

Средний

2 мин

1.7K

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

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

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

Решение

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

- многочлен степени не более чем .
Назовем потенциалом раскраски для многочлена, разность между суммой его приростов на чёрных и суммой приростов на белых подотрезках.
$\pi(P(x), T)^{[a; b]}$ - потенциал раскраски отрезка способом , для многочлена , в записи может сокращаться до .
- искомый способ раскраски отрезка, такой что для любого многочлена , верно $\pi(P_n, T_n)^{[0; 1]} = 0$ .
$T^{-1}$ - способ раскраски отрезка, противоположный (все белые отрезки делаем черными и наоборот). Тогда $\pi(P, T)^{[a; b]} = -\pi(P, T^{-1})^{[a; b]}$ .

Описывая раскраску, будем использовать запись такого вида: [10010] - разбить раскрашиваемый отрезок на 5 равных подотрезков, каждый из которых раскрасить в белый (1) или черный (0) цвет соответственно.
T = [110101]
$\tau = [001011]$
$T^{-1} = [001010]$
$T\cdot \tau = [110101]\cdot[001011]=[110101001011]$ - конкатенация раскрасок

UPD: Более формальное определение :

$\pi(P(x), T)^{[a; b]} = \sum_{i=0}^{n - 1} (-1)^{T[i]}\left(P\left(a+(b-a)\frac{i}{n}\right) - P\left(a+(b-a)\frac{i+1}{n}\right)\right)$

где T[i] - цвет -ого подотрезка раскраски.

UPD: Два несложных свойства :

$\pi(P(x), T)^{[a; b]} = \pi(P(kx), T)^{[a/k; b/k]}$ $\pi(P(x), T)^{[a; b]} = \pi(P(x+с), T)^{[a-с; b-с]}$

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

$\pi(P + Q, T)^{[a; b]} = \pi(P, T)^{[a; b]} + \pi(Q, T)^{[a; b]}$

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

$\pi(P + Q, T)^{[a; b]} = \sum\limits_i -1^{k_i}\cdot(P(i) + Q(i)) = \sum\limits_i -1^{k_i}\cdot P(i) + \sum\limits_i -1^{k_i}\cdot Q(i) = \pi(P, T)^{[a; b]} + \pi(Q, T)^{[a; b]}$

Лемма 1

$\pi(P_n, T_n)^{[a; b]} = 0, \forall \ \ a<b$

Рассмотрим многочлен $Q_n(x) = P_n(\frac{x - a}{b - a})$ .
Тогда $\pi(Q_n(x), T_n)^{[0; 1]} = 0$ по определению T_n .
$0 = \pi(Q_n(x), T_n)^{[0; 1]} = \pi(P_n(\frac{x - a}{b - a}), T_n)^{[0; 1]} = \pi(P_n(x - a), T_n)^{[0; b - a]} = \pi(P_n(x), T_n)^{[a; b]}$

Лемма 2

$\pi(P_{n + 1}, T_n)^{[0; l]} = \pi(P_{n + 1}, T_n)^{[a; a + l]}, \forall \ \ a, l$

Пусть $\lambda$ , Q_n и S_n такие, что

$P_{n + 1}(x) = \lambda\cdot x^{n + 1} + Q_n(x)$ ;
$P_{n + 1}(x + a) = \lambda\cdot (x + a)^{n + 1} + Q_n(x + a) = \lambda\cdot x^{n + 1} + S_n(x)$ ;

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

$\pi(P_{n+1}, T_n)^{[0; l]} = \pi(\lambda\cdot x^{n + 1} + Q_n, T_n)^{[0; l]} \stackrel{\text{по св-ву 0}} = \pi(\lambda\cdot x^{n + 1}, T_n)^{[0, l]} + \pi(Q_n, T_n)^{[0; l]} \stackrel{\text{по лемме 1}} = \pi(\lambda\cdot x^{n + 1}, T_n)^{[0, l]}$

$\pi(P_{n+1}(x), T_n)^{[a; a + l]} = \pi(P_{n+1}(x + a), T_n)^{[0; l]} = \pi(\lambda\cdot x^{n + 1} + S_n(x), T_n)^{[0; l]} \stackrel{\text{по св-ву 0}} =$ $= \pi(\lambda\cdot x^{n + 1}, T_n)^{[0, l]} + \pi(S_n(x), T_n)^{[0; l]} \stackrel{\text{по лемме 1}}= \pi(\lambda\cdot x^{n + 1}, T_n)^{[0, l]}$

$\pi(P_{n+1}(x), T_n)^{[0; l]} \stackrel{\text{1.}}= \pi(\lambda\cdot x^{n + 1}, T_n)^{[0, l]} \stackrel{\text{2.}}= \pi(P_{n+1}(x), T_n)^{[a; a + l]}$

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

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

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

База

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

Переход

Пусть мы знаем раскраску T_n и хотим найти раскраску $T_{n + 1}$ .
Утверждается что подходящей является $T_n \cdot T_n^{-1}$ .

$T_{n + 1} = T_n \cdot T_n^{-1}$

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

$\pi(P_{n + 1}, T_n\cdot T_n^{-1})^{[0; 1]} = \pi(P_{n + 1}, T_n)^{[0,\frac{1}{2}]} + \pi(P_{n + 1}, T_n^{-1})^{[\frac{1}{2}; 1]} =$ $= \pi(P_{n + 1}, T_n)^{[0,\frac{1}{2}]} - \pi(P_{n + 1}, T_n)^{[\frac{1}{2}; 1]} \stackrel{\text{по лемме 2}}=$ $= \pi(P_{n + 1}, T_n)^{[0,\frac{1}{2}]} - \pi(P_{n + 1}, T_n)^{[0; \frac{1}{2}]} =$ = 0

Итог

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

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

T_0 = [0] ;
T_1 = [01] ;
T_2 = [0110] ;
T_3 = [01101001] ;
T_4 = [0110100110010110] ;

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

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

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

P.S. Благодарю за задачу Никиту Дмитриевича Пшеничного и Арсения Андреевича Акиншина.

Хабы: