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

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

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

16.07.2025 17:16

A1exYY 3 986 Источник

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

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

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

Решение

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

- многочлен степени не более чем .
Назовем потенциалом раскраски для многочлена, разность между суммой его приростов на чёрных и суммой приростов на белых подотрезках.
$\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. Благодарю за задачу Никиту Дмитриевича Пшеничного и Арсения Андреевича Акиншина.

Комментарии (3)

wataru
17.07.2025 09:02
#28584964
Выглядит интересно, но очень много непоятностей и белых пятен.

Вы рассматриваете только "равномерные" раскраски из отрезков одинаковой длины?

Нужна расшифровка определения, "раскраски способом T", ведь вы там применяете одну и туже раскраску к отрезкам [0,1] и [a,b]. Я правильно понимаю, что это - разбить отрезок равномерно на n кусков? И если отрезок другой, то точки в нем другие?

Еще, вам надо бы формально определить $\pi(P(x), T)^{[a; b]}$ . Я правильно понимаю, что это:
$\sum_{i=0..n} (-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] - 0 или 1 в зависимости от цвета отрезка i+1.

Вы там в свойстве 0 что-то подобное используете, но как-то странно: значения полиномов берете от какого-то номера i, а не точки на отрезке [a,b] и вместо приростов берете просто значения в точках.

А еще, мне непонятна лемма 1. Могли бы вы ее доказательство поформальнее расписать?

У вас, похоже, там опечатка. Надо в определении Q делить на (b-a) аргумент полинома, а не его значение.Тогда станут понятны выкладки в доказательстве. Хотя, для этого хорошо бы вам при определении потенциала еще и расписать некоторые его свойства, вроде $\pi(P(x), T_n)^{[a; b]} = \pi(P(kx), T_n)^{[a/k; b/k]}$ а так же $\pi(P(x), T_n)^{[a; b]} = \pi(P(x+с), T_n)^{[a-с; b-с]}$

Тогда $\pi(Q_n(x), T_n)^{[0; 1]} = 0$ по определению

Определение Tn - это что P() имеет нулевой потенциал на [0,1], Как его применить к Q на отрезке [0,1] вообще не очевидно. Вам бы стоило тут по определению потенциала расписать и показать, почему это выполняется.

В лемме 2 тоже куча пропущенных определений и шагов.

Например:

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

Во-первых, что за P_{n+1}? Что за Q? Вы там используете определение Tn, но оно определено для какого-то полинома Pn, как связанны Qn и Pn? Вы там применяете лемму 1, как будто Tn зануляет потенциал для Qn(x) на отрезке [0,1].

У вас в условии леммы уже фигурируют какие-то P(n+1) и Tn. Вам надо их описать. P(n+1), кажется - произвольный полином степени n+1. Вот откуда берется Tn и каким свойствам оно удовлетворяет - это вопрос.
1. A1exYY Автор
  17.07.2025 09:02
  #28586034
  Здравствуйте, спасибо за комментарий. Постараюсь ответить на вопросы:
  
  Для решения задачи требуется найти любую подходящую раскраску. В моём решении она получилась составленной из равных по длине отрезков. Но, например, может быть вообще любой раскраской, а дальше по индукции мы бы нашли все остальные , которые тоже отличались бы от приведённых мной, и тоже были бы решением. Я взял для самую простую раскраску -
  
  Да, ваше определение правильное. В свойстве 0, я не расписывал потенциал подробно, а лишь указал, что он равен алгебраической сумме значений многочлена в некоторых точках. Чего достаточно для доказательства аддитивности.
  
  Я добавил в статью более подробные определения и исправил опечатки.
  
  В определениях и формулах я использовал P, Q, S как обозначения многочленов, то есть определения для применимы и к , и к , если они имеют тот же индекс, то есть то же ограничение на степень многочлена.
  
  Если у многочлена индекс не n, а n + 1, это означает, что он имеет степень не больше чем n + 1. Определение показывало "формат обозначения" многочленов степень которых не превышает какой-то величины.
  1. wataru
    17.07.2025 09:02
    #28586258
    Спасибо. Я еще в начале проморгал слово "любого" перед многочленом в определении T. Смотрю оно теперь выделено жирным, так гораздо понрятнее.