Jump to content

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

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

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

01101001100101101001011001101001.... [1]

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

Определение

[ редактировать ]

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

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

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

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

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

[ редактировать ]

Этот метод приводит к быстрому методу вычисления последовательности Туэ-Морса: начните с t 0 = 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

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

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

[ редактировать ]

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

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

L-система

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

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

Переменные 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 .
  • Т 1 = 01.
  • Т 2 = 0110.
  • Т3 = 01101001 .
  • Т 4 = 0110100110010110.
  • Т 5 = 01101001100101101001011001101001.
  • Т 6 = 0110100110010110100101100110100110010110011010010110100110010110.
  • И так далее.

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

[ редактировать ]

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

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

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

[ редактировать ]

Последовательность Туэ-Морса содержит много квадратов : экземпляры строки. , где обозначает строку , , , или , где для некоторых и это побитовое отрицание . [5] Например, если , затем . Площадь появляется в начиная с 16-го бита. Поскольку все квадраты в получаются повторением одной из этих 4 строк, все они имеют длину или для некоторых . не содержит кубов : экземпляры . Также нет перекрывающихся квадратов : экземпляры или . [6] [7] Критический показатель это 2. [8]

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

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

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

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

для всех целых чисел i от 1 до k .

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

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

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

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

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

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

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

[ редактировать ]

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

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

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

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

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

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

[ редактировать ]

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

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

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

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

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

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

где это член последовательности Туэ-Морса. Фактически для всех с действительной частью больше, чем , у нас есть

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Перейти обратно: а б Слоан, Нью-Джерси (ред.). «Последовательность A010060 (последовательность Туэ-Морса)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
  2. ^ Перейти обратно: а б Аллуш и Шалит (2003 , стр. 15)
  3. ^ Арндт (2011) .
  4. ^ Лотарь (2011 , стр. 11)
  5. ^ Брлек (1989) .
  6. ^ Лотарь (2011 , стр. 113)
  7. ^ Пифей Фогг (2002 , стр. 103)
  8. ^ Кригер (2006) .
  9. ^ Лотарь (2011 , стр. 30)
  10. ^ Берте и Риго (2010) .
  11. ^ Лотарь (2011 , стр. 31)
  12. ^ Берстель и др. (2009 , стр. 70)
  13. ^ Берстель и др. (2009 , стр. 80)
  14. ^ Болкер и др. (2016) .
  15. ^ Ма и Холденер (2005) .
  16. ^ Абель, Закари (23 января 2012 г.). «Навигационные черепахи Туэ-Морса» . Треугольные вещи .
  17. ^ Брэмс и Тейлор (1999) .
  18. ^ Левин и Штанге (2012) .
  19. ^ Перейти обратно: а б с Ричман (2001)
  20. ^ Абрахамс (2010) .
  21. ^ Перейти обратно: а б Купер и Дутл (2013)
  22. ^ Паласиос-Уэрта (2012) .
  23. ^ Паласиос-Уэрта (2014) .
  24. ^ Коэн-Зада, Крумер и Шапир (2018) .
  25. ^ Барроу (2010) .
  26. ^ «Типы фэнтезийных проектов» . НФЛ.com . Архивировано из оригинала 12 октября 2018 года.
  27. ^ Аллан, Ян (16 июля 2014 г.). «Отмененные драфты третьего раунда» . Индекс фэнтези . Проверено 1 сентября 2020 г.
  28. ^ Пачоцкий, Якуб; Радошевский, Якуб (2013). «Где использовать и как не использовать полиномиальное хеширование строк» ​​(PDF) . Олимпиады по информатике . 7 : 90–100.
  29. ^ Тот, Ласло (2022). «Линейные комбинации рядов Дирихле, связанных с последовательностью Туэ-Морса». Целые числа . 22 (статья 98). arXiv : 2211.13570 .
  30. ^ Вездесущий эпизод Пруэ-Тюэ-Морса Жана-Поля Аллюша и Джеффри Шаллита
  31. ^ Фредриксен, Гарольд (1992). «Коды Грея и последовательность Туэ-Морса-Хедлунда». Журнал комбинаторной математики и комбинаторных вычислений (JCMCC) . 11 . Аспирантура ВМФ, математический факультет, Монтерей, Калифорния, США: 3–11.
  32. ^ Эриксон, Джон (30 октября 2018 г.). «Об асимптотическом относительном изменении последовательностей перестановок» . Проверено 31 января 2021 г. [1]

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

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 7299c0c10e577dc871a9c1a94bb13b73__1721037120
URL1:https://arc.ask3.ru/arc/aa/72/73/7299c0c10e577dc871a9c1a94bb13b73.html
Заголовок, (Title) документа по адресу, URL1:
Thue–Morse sequence - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)