Последовательность Туэ – Морса

Этот рисунок демонстрирует повторяющийся и дополняющий состав последовательности Туэ – Морса.

В математике последовательность Туэ -Морса или Пруэ-Туэ-Морса представляет собой двоичную последовательность (бесконечную последовательность нулей и единиц), которую можно получить, начиная с 0 и последовательно добавляя логическое дополнение к полученной к настоящему моменту последовательности. Иногда ее называют последовательностью справедливого распределения из-за ее применения к последовательности справедливого деления или последовательности паритета . Первые несколько шагов этой процедуры дают строки 0, 01, 0110, 01101001, 0110100110010110 и т. д., которые являются префиксами последовательности Туэ–Морса. Полная последовательность начинается:

01101001100101101001011001101001....

Эпизод назван в честь Акселя Туэ и Марстона Морса .

Определение

Существует несколько эквивалентных способов определения последовательности Туэ – Морса.

Прямое определение

При двоичном счете сумма цифр по модулю 2 представляет собой последовательность Туэ – Морса.

Чтобы вычислить n -й элемент t _n , запишите число n в двоичном формате . Если число единиц в этом двоичном разложении нечетное, то t _n = 1, если четное, то t _n = 0. То есть t _n — это бит четности для n . Джон Х. Конвей и др . считал числа n, удовлетворяющие t _n = 1, одиозными ( похожими на нечетные ) числами, а числа, для которых t _n = 0, злыми (похожими на четные ) числами.

Быстрая генерация последовательности

Этот метод приводит к быстрому методу вычисления последовательности Туэ-Морса: начните с t ₀ = 0 , а затем для каждого n найдите бит старшего порядка в двоичном представлении n , который отличается от того же бита в представление n - 1 . Если этот бит имеет четный индекс, t _n отличается от t _{n − 1} , в противном случае он совпадает с t _{n − 1} .

В Питоне :

def generate_sequence(seq_length: int):
    """Thue–Morse sequence."""
    value = 1
    for n in range(seq_length):
        # Note: assumes that (-1).bit_length() gives 1
        x = (n ^ (n - 1)).bit_length() + 1
        if x & 1 == 0:
            # Bit index is even, so toggle value
            value = 1 - value
        yield value

Полученный алгоритм требует постоянного времени для генерации каждого элемента последовательности, используя только логарифмическое количество битов (постоянное количество слов) памяти.

Рекуррентное отношение

Последовательность Туэ–Морса — это последовательность t _n, удовлетворяющая рекуррентному соотношению

${\begin{aligned}t_{0}&=0,\\t_{2n}&=t_{n},\\t_{2n+1}&=1-t_{n},\end{aligned}}$

для всех неотрицательных целых чисел n .

L-система

Последовательность Туэ – Морса, порожденная L-системой

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

Переменные	0, 1
Константы	Никто
Начинать	0
Правила	(0 → 01), (1 → 10)

Характеризация с использованием побитового отрицания

Последовательность Туэ–Морса в приведенной выше форме, как последовательность битов , может быть определена рекурсивно с помощью операции побитового отрицания . Итак, первый элемент равен 0. Затем, как только первые 2 ^н были указаны элементы, образующие строку s , затем следующие 2 ^н элементы должны образовывать побитовое отрицание s . Теперь мы определили первые 2 ^{п +1} элементы, и мы рекурсируем.

Подробное описание первых шагов:

• Начинаем с 0.
• Побитовое отрицание 0 равно 1.
• Объединив их, первые два элемента равны 01.
• Побитовое отрицание 01 равно 10.
• Объединив их, первые 4 элемента равны 0110.
• Поразрядное отрицание 0110 равно 1001.
• Объединив их, первые 8 элементов составят 01101001.
• И так далее.

Так

• Т0 _{= 0} .
• Т ₁ = 01.
• Т ₂ = 0110.
• Т3 _{= 01101001} .
• Т ₄ = 0110100110010110.
• Т ₅ = 01101001100101101001011001101001.
• Т ₆ = 0110100110010110100101100110100110010110011010010110100110010110.
• И так далее.

Бесконечный продукт

Последовательность также может быть определена следующим образом:

$\prod _{i=0}^{\infty }\left(1-x^{2^{i}}\right)=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j},$

где t _j — j -й элемент, если мы начинаем с j = 0.

Характеристики

Последовательность Туэ-Морса содержит много квадратов : экземпляры строки. $XX$, где $X$ обозначает строку $A$, ${\overline {A}}$, $A{\overline {A}}A$, или ${\overline {A}}A{\overline {A}}$, где $A=T_{k}$ для некоторых $k\geq 0$ и ${\overline {A}}$ это побитовое отрицание $A$. Например, если $k=0$, затем $A=T_{0}=0$. Площадь $A{\overline {A}}AA{\overline {A}}A=010010$ появляется в $T$ начиная с 16-го бита. Поскольку все квадраты в $T$ получаются повторением одной из этих 4 строк, все они имеют длину $2^{n}$ или $3\cdot 2^{n}$ для некоторых $n\geq 0$. $T$ не содержит кубов : экземпляры $XXX$. Также нет перекрывающихся квадратов : экземпляры $0X0X0$ или $1X1X1$. Критический показатель ​ $T$ это 2.

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

Последовательность T _{2 n} является палиндромом для любого n . Кроме того, пусть q _n — слово, полученное путем подсчета единиц между последовательными нулями в T _{2 n} . Например, q ₁ = 2 и q ₂ = 2102012. Поскольку T _n не содержит перекрывающихся квадратов , слова q _n являются палиндромными словами без квадратов .

Морфизм Туэ–Морса . µ определяется в алфавите {0,1} с помощью карты подстановки µ (0) = 01, µ (1) = 10: каждый 0 в последовательности заменяется на 01, а каждая 1 – на 10 Если T последовательность Туэ–Морса, то µ ( T ) также является T. — образом, T является неподвижной точкой µ Таким . Морфизм µ является продолжаемым морфизмом на свободном моноиде {0,1} ^∗ с T в качестве фиксированной точки: T по существу является единственной фиксированной точкой µ ; единственная другая фиксированная точка - это побитовое отрицание T , которое представляет собой просто последовательность Туэ – Морса для (1,0) вместо (0,1). Это свойство можно обобщить до понятия автоматической последовательности .

Производящий ряд T над бинарным полем представляет собой формальный степенной ряд

$t(Z)=\sum _{n=0}^{\infty }T(n)Z^{n}\ .$

Этот степенной ряд является алгебраическим над полем рациональных функций и удовлетворяет уравнению

$Z+(1+Z)^{2}t+(1+Z)^{3}t^{2}=0$

В комбинаторной теории игр

Набор злых чисел (цифр $n$ с $t_{n}=0$) образует подпространство неотрицательных целых чисел при добавлении nim ( побитовое исключающее или ). В игре Кейлса злые ним-значения встречаются для нескольких (конечно многих) позиций в игре, при этом все оставшиеся позиции имеют одиозные ним-значения.

Задача Пруэ–Тэрри–Эскотта.

Задачу Пруэ-Тэрри-Эскотта можно определить следующим образом: учитывая целое положительное число N и целое неотрицательное число k , разбейте множество S = {0, 1, ..., N -1} на два непересекающихся подмножества S ₀ и S ₁ , которые имеют равные суммы степеней до k, то есть:

$\sum _{x\in S_{0}}x^{i}=\sum _{x\in S_{1}}x^{i}$ для всех целых чисел i от 1 до k .

Это имеет решение, если N кратно 2. ^{к +1} , заданный:

• S ₀ состоит из целых чисел n из S, для которых t _n = 0,
• S ₁ состоит из целых чисел n из S, для которых t _n = 1.

Например, для N = 8 и k = 2,

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,

0 ² + 3 ² + 5 ² + 6 ² = 1 ² + 2 ² + 4 ² + 7 ² .

Условие, требующее, чтобы N было кратно 2 ^{к +1} не является строго необходимым: есть еще несколько случаев, для которых существует решение. Однако оно гарантирует более сильное свойство: если условие выполнено, то множество k -х степеней любого набора из N чисел в арифметической прогрессии можно разбить на два множества с равными суммами. Это следует непосредственно из расширения, данного биномиальной теоремой, примененной к биному, представляющему n- й элемент арифметической прогрессии.

Обобщения последовательности Туэ-Морса и проблемы Пруэ-Тэрри-Эскотта для разделения на более чем две части см. в книге Болкера, Оффнера, Ричмана и Зары, «Проблема Пруэ-Тэрри-Эскотта и обобщенные последовательности Туэ-Морса».

Фракталы и черепаховая графика

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

• Если t ( n ) = 0, двигаться вперед на одну единицу,
• Если t ( n ) = 1, поверните на угол π/3 радиан (60°).

Полученная кривая сходится к кривой Коха , фрактальной кривой бесконечной длины, содержащей конечную площадь. Это иллюстрирует фрактальную природу последовательности Туэ – Морса.

Также можно точно нарисовать кривую, используя следующие инструкции:

• Если t ( n ) = 0, поверните на угол π радиан (180°),
• Если t ( n ) = 1, переместимся вперед на одну единицу, а затем повернём на угол π/3 радиан.

Справедливая последовательность

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

Лайонел Левин и Кэтрин Э. Стэндж в обсуждении того, как справедливо распределить совместную трапезу, например эфиопский ужин , предложили последовательность Туэ-Морса как способ уменьшить преимущество движения первым. Они предположили, что «было бы интересно количественно оценить интуицию, согласно которой порядок Туэ-Морса имеет тенденцию давать справедливый результат».

Роберт Ричман обратился к этой проблеме, но он тоже не определил последовательность Туэ-Морса как таковую на момент публикации. Он представил последовательности T _n как ступенчатые функции на интервале [0,1] и описал их связь с функциями Уолша и Радемахера . Он показал, что n- я производная может быть выражена через T _n . Как следствие, ступенчатая функция, возникающая из T _n, полиномам ортогональна порядка наиболее справедливо распределяется с использованием n − монотонно 1. Следствием этого результата является то, что ресурс, значение которого выражается как убывающая непрерывная функция, последовательности, сходящейся к Туэ-Морса, когда функция становится более плоской . На примере было показано, как наливать чашки кофе из графина одинаковой крепости с нелинейным концентрации градиентом , что послужило поводом для создания причудливой статьи в популярной прессе.

Джошуа Купер и Аарон Дутл показали, почему порядок Туэ-Морса обеспечивает справедливый результат для дискретных событий. Справедливее всего они посчитали устроить дуэль Галуа , в которой каждый из стрелков одинаково плохо владеет стрелковыми навыками. другого Купер и Дутл постулировали, что каждый дуэлянт потребует возможности выстрелить, как только априорная вероятность победы превысит его собственную. Они доказали, что, когда вероятность попадания дуэлянтов приближается к нулю, последовательность стрельбы сходится к последовательности Туэ – Морса. При этом они продемонстрировали, что порядок Туэ–Морса дает справедливый результат не только для последовательностей T _n длины 2. ^н , но для последовательностей любой длины.

Таким образом, математика поддерживает использование последовательности Туэ-Морса вместо чередующихся ходов, когда целью является справедливость, но более ранние ходы монотонно отличаются от более поздних по некоторому значимому качеству, независимо от того, меняется ли это качество непрерывно. или дискретно.

Спортивные соревнования составляют важный класс задач справедливой последовательности, поскольку строгое чередование часто дает несправедливое преимущество одной команде. Игнасио Паласиос-Уэрта предложил изменить последовательный порядок на Туэ-Морса, чтобы улучшить ex post справедливость различных турнирных соревнований, таких как последовательность ударов ногами в серии пенальти в футболе. Он провел серию полевых экспериментов с профессиональными игроками и обнаружил, что команда, начавшая удар первой, выиграла 60% игр, используя ABAB (или T1 _{), и} ), 54%, используя ABBA (или T2 _. 51%, используя полную версию Туэ-Морса (или T2) Т _н ). В результате ABBA проходит обширные испытания в ФИФА (чемпионаты Европы и мира) и английской федерации профессионального футбола ( Кубок EFL ). Было также обнаружено, что схема подачи ABBA повышает справедливость теннисных тай-брейков . В соревновательной гребле Т 2 _— единственное расположение членов экипажа , гребущих по левому и правому борту , которое устраняет поперечные силы (и, следовательно, боковое покачивание) на четырехчленной гоночной лодке без рулевого, тогда как Т ₃ — одна из четырех оснасток, позволяющая избежать покачивания. на восьмиместной лодке.

Справедливость особенно важна при драфте игроков . Многие профессиональные спортивные лиги пытаются достичь конкурентного паритета , предоставляя более ранние выборы в каждом раунде более слабым командам. Напротив, лигам фэнтези-футбола не нужно исправлять уже существующий дисбаланс, поэтому они часто используют «змеиный» драфт (вперед, назад и т. д.; или Т ₁ ). Ян Аллан утверждал, что «разворот в третьем раунде» (вперед, назад, назад, вперед и т. д.; или Т ₂ ) был бы еще более справедливым. Ричман предположил, что самый справедливый способ для «капитана А» и «капитана Б» выбирать стороны в баскетбольной игре отражает Т ₃ : у капитана А есть первый, четвертый, шестой и седьмой варианты выбора, а у капитана Б — второй, третий, пятый и восьмой варианты.

Хэш-коллизии

Начальный 2 ^к биты последовательности Туэ-Морса отображаются в 0 с помощью широкого класса полиномиальных хэш-функций по модулю степени двойки , что может привести к хеш-коллизиям .

Дзета-функция Римана

Определенные линейные комбинации рядов Дирихле, коэффициенты которых являются членами последовательности Туэ – Морса, приводят к тождествам, включающим дзета-функцию Римана (Tóth, 2022). ). Например:

${\begin{aligned}\sum _{n\geq 1}{\frac {5t_{n-1}+3t_{n}}{n^{2}}}&=4\zeta (2)={\frac {2\pi ^{2}}{3}},\\\sum _{n\geq 1}{\frac {9t_{n-1}+7t_{n}}{n^{3}}}&=8\zeta (3),\end{aligned}}$

где $(t_{n})_{n\geq 0}$ это $n^{\rm {th}}$ член последовательности Туэ-Морса. Фактически для всех $s$ с действительной частью больше, чем $1$, у нас есть

$(2^{s}+1)\sum _{n\geq 1}{\frac {t_{n-1}}{n^{s}}}+(2^{s}-1)\sum _{n\geq 1}{\frac {t_{n}}{n^{s}}}=2^{s}\zeta (s).$

История

Последовательность Туэ-Морса была впервые изучена Эженом Пруэ в 1851 году. который применил это к теории чисел . Однако Пруэ не упомянул эту последовательность явно; это было оставлено Акселю Туэ в 1906 году, который использовал его для изучения комбинаторики слов . Последовательность привлекла внимание всего мира только благодаря работе Марстона Морса в 1921 году, когда он применил ее к дифференциальной геометрии . Последовательность открывалась независимо много раз, не всегда профессиональными математиками-исследователями; например, Макс Эйве , гроссмейстер по шахматам и учитель математики , открыл его в 1929 году в приложении к шахматам : используя его свойство бескубности (см. выше), он показал, как обойти правило тройного повторения , направленное на предотвращение бесконечно затяжных игр. объявив повторение ходов ничьей. В то время для срабатывания правила требовались последовательные идентичные состояния доски; Позже в правило были внесены поправки, согласно которым одна и та же позиция на доске повторяется три раза в любой момент, поскольку последовательность показывает, что последовательный критерий можно обходить навсегда.

См. также

• Теория Дежана
• Функция Фабиуса
• Первое отличие последовательности Туэ – Морса
• Код Грея
• Константа судебного пристава-Лорети
• Константа Пруэ–Тюэ–Морса

Ссылки

• Абрахамс, Марк (12 июля 2010 г.). «Как налить идеальную чашку кофе» . Хранитель .
• Арндт, Йорг (2011). «1.16.4 Последовательность Туэ – Морса» (PDF) . Вопросы вычислений: идеи, алгоритмы, исходный код . Спрингер. п. 44.
• Аллуш, Жан-Поль; Шалит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN  978-0-521-82332-6 . Збл   1086.11015 .
• Барроу, Джон Д. (2010). «Гребля и задача об одной сумме имеют свои моменты». Американский журнал физики . 78 (7): 728–732. arXiv : 0911.3551 . Бибкод : 2010AmJPh..78..728B . дои : 10.1119/1.3318808 . S2CID   119207447 .
• Берстель, Жан; Лауве, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и повторы в словах . Серия монографий по CRM. Том. 27. Провиденс, Род-Айленд, США: Американское математическое общество . ISBN  978-0-8218-4480-9 . Коллекция   1161.68043 .
• Берта, Валери ; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. Том. 135. Кембридж: Издательство Кембриджского университета . п. 7. ISBN  978-0-521-51597-9 . Збл   1197.68006 .
• Болкер, Итан; Оффнер, Карл; Ричман, Роберт; Зара, Каталин (2016). «Проблема Пруэ – Тэрри – Эскотта и обобщенные последовательности Туэ – Морса». Журнал комбинаторики . 7 (1): 117–133. arXiv : 1304.6756 . дои : 10.4310/JOC.2016.v7.n1.a5 . S2CID   118040795 . }
• Брамс, Стивен Дж.; Тейлор, Алан Д. (1999). Беспроигрышное решение: гарантия справедливого распределения акций для всех . WW Norton & Co., Inc., стр. 36–44 . ISBN  978-0-393-04729-5 .
• Брлек, Сречко (1989). «Перечень факторов в слове Туэ-Морса». Дискретная прикладная математика . 24 (1–3): 83–96. дои : 10.1016/0166-218x(92)90274-e .
• Коэн-Зада, Дэнни; Крумер, Алекс; Шапир, Предложение Моше (2018). «Тестирование эффекта порядка подачи на тай-брейке в теннисе» . Журнал экономического поведения и организации . 146 : 106–115. дои : 10.1016/j.jebo.2017.12.012 . S2CID   89610106 .
• Купер, Джошуа; Дутл, Аарон (2013). «Жадные игры Галуа» (PDF) . Американский математический ежемесячник . 120 (5): 441–451. arXiv : 1110.1137 . doi : 10.4169/amer.math.monthly.120.05.441 . S2CID   1291901 .
• Кригер, Далия (2006). «О критических показателях в неподвижных точках нестирающихся морфизмов». В Ибарре, Оскар Х.; Данг, Чжэ (ред.). Развитие теории языка: материалы 10-й международной конференции, DLT 2006, Санта-Барбара, Калифорния, США, 26–29 июня 2006 г. Конспекты лекций по информатике. Том. 4036. Шпрингер-Верлаг . стр. 280–291. ISBN  978-3-540-35428-4 . Збл   1227.68074 .
• Левин, Лайонел; Штанге, Кэтрин Э. (2012). «Как получить максимальную пользу от совместной трапезы: сначала спланируйте последний кусочек» (PDF) . Американский математический ежемесячник . 119 (7): 550–565. arXiv : 1104.0961 . doi : 10.4169/amer.math.monthly.119.07.550 . S2CID   14537479 .
• Лотер, М. (2011). Алгебраическая комбинаторика на словах . Энциклопедия математики и ее приложений. Том. 90. С предисловием Жана Берстеля и Доминика Перрена (перепечатка издания 2002 г. в твердом переплете). Издательство Кембриджского университета. ISBN  978-0-521-18071-9 . Артикул   1221.68183 .
• Ма, Джун; Холденер, Джуди (2005). «Когда Туэ-Морс встречает Коха» (PDF) . Фракталы . 13 (3): 191–206. дои : 10.1142/S0218348X05002908 . МР   2166279 .
• Паласиос-Уэрта, Игнасио (2012). «Турниры, справедливость и последовательность Пруэ – Туэ – Морса» (PDF) . Экономическое расследование . 50 (3): 848–849. дои : 10.1111/j.1465-7295.2011.00435.x . S2CID   54036493 .
• Паласиос-Уэрта, Игнасио (2014). Красивая теория игр . Издательство Принстонского университета. ISBN  978-0691144023 .
• Пифей Фогг, Н. (2002). Берта, Валери; Ференци, Себастьен; Модуит, Кристиан; Сигел, А. (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин, Германия: Springer-Verlag . ISBN  978-3-540-44141-0 . Збл   1014.11015 .
• Ричман, Роберт (2001). «Рекурсивные двоичные последовательности разностей» (PDF) . Сложные системы . 13 (4): 381–392.

Дальнейшее чтение

• Бюжо, Янн (2012). Распределение по модулю единицы и диофантово приближение . Кембриджские трактаты по математике. Том. 193. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-11169-0 . Збл   1260.11001 .
• Лотер, М. (2005). Прикладная комбинаторика к словам . Энциклопедия математики и ее приложений. Полет. 105. Коллективная работа Жана Берстеля, Доминика Перрена, Максима Крошмора, Эрика Лапорта, Мехрияра Мори, Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана, Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-84802-2 . Збл   1133.68067 .

Внешние ссылки

• «Последовательность Туэ-Морса» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Последовательность Туэ-Морса» . Математический мир .
• Аллуш, Ж.-П.; Шалит, Дж. О. Вездесущая последовательность Пруэ-Тюэ-Морса . (содержит множество приложений и некоторую историю)
• Последовательность Туэ – Морса над (1,2) (последовательность A001285 в OEIS )
• Последовательность OEIS A000069 (одиозные числа: числа с нечетным числом единиц в двоичном представлении)
• Последовательность OEIS A001969 (Злые числа: числа с четным числом единиц в двоичном представлении)
• Уменьшение влияния дрейфа смещения постоянного тока в аналоговых IP с помощью последовательности Туэ-Морса . Техническое применение последовательности Туэ – Морса.
• MusiNum — Музыка в цифрах . Бесплатное программное обеспечение для создания самоподобной музыки на основе последовательности Туэ – Морса и связанных с ней числовых последовательностей.
• Паркер, Мэтт . «Самая справедливая сцена обмена» (видео) . стендапматематика . Проверено 20 января 2016 г.