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

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

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

01101001100101101001011001101001.... (последовательность A010060 в OEIS )

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

• 1 Определение
  • 1.1 Прямое определение
  • 1.2 Быстрая генерация последовательности
  • 1.3 Отношение повторения
  • 1.4 L-система
  • 1.5 Характеризация с использованием побитового отрицания
  • 1.6 Бесконечное произведение
• 2 Некоторые свойства
  • 2.1 В комбинаторной теории игр
  • 2.2 Проблема Пруэ-Тарри-Эскотта
  • 2.3 Фракталы и графика черепах
  • 2.4 Справедливое упорядочение
• 3 История
• 4 См. Также
• 5 Примечания
• 6 Ссылки
• 7 Дополнительная литература
• 8 Внешние ссылки

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

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

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

Для вычисления n-го элемента t n запишите число n в двоичном. Если количество единиц в этом двоичном расширении i s нечетное, тогда t n = 1, если четное, то t n = 0. По этой причине Джон Х. Конвей et al. вызвать номера n, удовлетворяющие t n = 1 одиозным (для нечетных) номеров и номерам, для которых t n = 0 злым (для четных) номеров. Другими словами, t n = 0, если n является злым числом и t n = 1, если n является одиозным числом.

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

Этот метод приводит к быстрому способу вычисления последовательности Туэ – Морса: начните с t 0 = 0, а затем для каждого n найдите бит наивысшего порядка в двоичное представление n, которое отличается от того же бита в представлении n - 1. (Этот бит может быть изолирован, если позволить x быть побитовым исключающим или из n и n - 1, сдвинуть x вправо на один бит и вычислить исключающее или этого смещенного значения с помощью x.) Если этот бит имеет четный индекс, t n отличается от t n - 1, а в противном случае это то же самое, что t n - 1.

В форме псевдокода:

generateSequence (seqLength): value = 0 for n = 0 to seqLength-1 by 1: x = n ^ (n-1) if ((x ^ (x>>1)) 0x55555555): value = 1 - value return value

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

Отношение рекуррентности

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

$t\; 0\; =\; 0,\; t\; 2\; n\; =\; tn,\; t\; 2\; n\; +\; 1\; =\; 1\; -\; tn,\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; t\_\; \{0\}\; =\; 0,\; \backslash \backslash \; t\_\; \{2n\}\; =\; t\_\; \{n\; \},\; \backslash \backslash \; t\_\; \{2n\; +\; 1\}\; =\; 1-t\_\; \{n\},\; \backslash \; end\; \{align\}\}\}$

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

L-система

Thue –Последовательность Морса, сгенерированная L-системой

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

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

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

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

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

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

Итак,

• T0= 0.
• T1= 01.
• T2= 0110.
• T3= 01101001.
• T4= 0110100110010110.
• T5= 01101001100101101001011001101001.
• T6= 0110100110010110100101100110100110010110011010010110100110010110.
• И т.д.>∏ я знак равно 0 ∞ (1 - Икс 2 я) знак равно ∑ J знак равно 0 ∞ (- 1) tjxj, {\ displaystyle \ prod _ {i = 0} ^ {\ infty} \ left (1-x ^ {2 ^ {i}} \ right) = \ sum _ {j = 0} ^ {\ infty} (- 1) ^ {t_ {j}} x ^ {j},}

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

  Некоторые свойства

  Потому что каждый новый блок в последовательности Туэ – Морса определяется путем формирования t Поразрядное отрицание начала, и это повторяется в начале следующего блока, последовательность Туэ – Морса заполняется квадратами: последовательные строки, которые повторяются. То есть существует много экземпляров XX, где X - некоторая строка. Действительно, $X\; \{\backslash \; displaystyle\; X\}$является такой строкой тогда и только тогда, когда $X\; =\; A,\; A\; ¯,\; AA\; ¯\; A,\; \{\backslash \; displaystyle\; X\; =\; A,\; \backslash ,\; \{\backslash \; overline\; \{A\}\},\; \backslash ,\; A\; \{\backslash \; overline\; \{A\}\}\; A,\}$или $A\; ¯\; AA\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; overline\; \{A\}\}\; A\; \{\backslash \; overline\; \{A\}\; \}\}$где $A\; =\; T\; k\; \{\backslash \; displaystyle\; A\; =\; T\_\; \{k\}\}$для некоторых $k\; \ge \; 0\; \{\backslash \; displaystyle\; k\; \backslash \; geq\; 0\}$и $A\; ¯\; \{\backslash \; displaystyle\; \{\backslash \; overline\; \{A\}\}\}$обозначает побитовое отрицание $A\; \{\backslash \; displaystyle\; A\}$(заменяют нули и 1с). Например, с $k\; =\; 0\; \{\backslash \; displaystyle\; k\; =\; 0\}$мы имеем $A\; =\; T\; 0\; =\; 0\; \{\backslash \; displaystyle\; \backslash \; A\; =\; T\_\; \{0\}\; =\; 0\}$, а квадрат $AA\; ¯\; AAA\; ¯\; A\; =\; 010010\; \{\backslash \; displaystyle\; A\; \{\backslash \; overline\; \{A\}\}\; AA\; \{\backslash \; overline\; \{A\}\}\; A\; =\; 010010\}$отображается в $T\; \{\backslash \; displaystyle\; T\}$начиная с 16-го бита. (Таким образом, квадраты в $T\; \{\backslash \; displaystyle\; T\}$имеют длину, равную степени 2 или 3, умноженной на степень 2.) Однако кубов нет: экземпляры XXX. Также нет перекрывающихся квадратов: экземпляры 0X0X0 или 1X1X1. критический показатель равен 2.

  Последовательность T 2n является палиндромом для любого n. Далее, пусть q n будет словом, полученным из T 2n путем подсчета единиц между последовательными нулями. Например, q 1 = 2 и q 2 = 2102012 и так далее. Слова T n не содержат перекрывающихся квадратов, следовательно, слова q n являются палиндромом бесквадратными словами.

  Утверждение выше, что последовательность Туэ – Морзе "заполнена" с квадратами "можно уточнить: это равномерно повторяющееся слово, означающее, что для любой конечной строки X в последовательности существует некоторая длина n X (часто намного длиннее, чем длина X) так, что X появляется в каждом блоке длины n X. Самый простой способ создать повторяющуюся последовательность - сформировать периодическую последовательность , в которой последовательность полностью повторяется после заданного количества шагов m. Тогда n X может быть установлено равным любому кратному m, которое больше, чем удвоение длины X. Но последовательность Морса является равномерно рекуррентной, но не периодической, даже в конечном итоге периодической (т.е. периодической после некоторого непериодического начального сегмента

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

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

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

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

  $Z\; +\; (1\; +\; Z)\; 2\; t\; +\; (1\; +\; Z)\; 3\; t\; 2\; =\; 0\; \{\backslash \; displaystyle\; Z\; +\; (1\; +\; Z)\; ^\; \{2\}\; t\; +\; (1\; +\; Z)\; ^\; \{3\}\; t\; ^\; \{2\}\; =\; 0\}$

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

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

  Проблема Пруэ-Тарри-Эскотта

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

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

  У этого есть решение, если N кратно 2, учитывая by:

  • S0состоит из целых чисел n в S, для которых t n = 0,
  • S1состоит из целых чисел 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, не является строго необходимым: есть еще несколько случаев, для которых существует решение. Однако это гарантирует более сильное свойство: если условие выполняется, то набор k-й степени любого набора из N чисел в арифметической прогрессии может быть разделен на два набора с равными суммами. Это следует непосредственно из расширения, данного биномиальной теоремой , примененного к биному, представляющему n-й элемент арифметической прогрессии.

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

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

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

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

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

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

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

  Равная последовательность

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

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

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

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

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

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

  Справедливость особенно важна в игроки шашки. Многие профессиональные спортивные лиги пытаются достичь конкурентного паритета, давая более ранние выборы в каждом раунде более слабым командам. Напротив, лиги фэнтези-футбола не имеют ранее существовавшего дисбаланса, который нужно исправить, поэтому они часто используют «змеиный» вариант (вперед, назад и т. Д.; или T 1). Ян Аллан утверждал, что «разворот в третьем раунде» (вперед, назад, назад, вперед и т.д.; или T 2) был бы еще более справедливым. Ричман предположил, что наиболее справедливый способ для «капитана A» и «капитана B» выбирать стороны для игры в баскетбол отражает T 3 : капитан A имеет первую, четвертую, шестой и седьмой варианты, в то время как у капитана B есть второй, третий, пятый и восьмой варианты.

  История

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

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

  На Wikimedia Commons есть материалы, связанные с последовательностью Туэ-Морса.

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