В математике последовательность Туэ – Морса или последовательность Пруэ – Туэ – Морса - это двоичная последовательность (бесконечная последовательность нулей и единиц), полученная, начиная с 0 и последовательно добавляя логическое дополнение к последовательности, полученной до сих пор. Первые несколько шагов этой процедуры дают строки 0, затем 01, 0110, 01101001, 0110100110010110 и т. Д., Которые являются префиксами последовательности Туэ – Морзе. Полная последовательность начинается:
Последовательность названа в честь Акселя Ту и Марстона Морса .
Определение
Есть несколько эквивалентных способов определения последовательности Туэ – Морса.
Прямое определение
Чтобы вычислить n- й элемент t n , запишите число n в двоичном формате . Если количество единиц в этом двоичном разложении нечетное, то t n = 1, если четное, то t n = 0. [1] По этой причине John H. Conway et al . называют номера n, удовлетворяющие t n = 1 одиозным (для нечетных ) номеров и номерам, для которых t n = 0, злым (для четных ) номеров. Другими словами, t n = 0, если n - злое число, и t n = 1, если n - одиозное число .
Быстрая генерация последовательности
Этот метод приводит к быстрому способу вычисления последовательности Туэ – Морса: начните с 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 для n = 0 до seqLength - 1 на 1 : x = n ^ ( n - 1 ) if (( x ^ ( x >> 1 )) & 0 x55555555 ): value = 1 - value возвращаемое значение
Результирующий алгоритм требует постоянного времени для генерации каждого элемента последовательности, используя только логарифмическое количество битов (постоянное количество слов) памяти. [2]
Отношение повторения
Последовательность Туэ – Морса - это последовательность t n, удовлетворяющая рекуррентному соотношению
для всех неотрицательных целых чисел n . [1]
L-система
Последовательность Туэ – Морса является морфическим словом : [3] это результат следующей системы Линденмайера :
Переменные | 0, 1 |
---|---|
Константы | Никто |
Начинать | 0 |
Правила | (0 → 01), (1 → 10) |
Характеризация с использованием побитового отрицания
Последовательность Туэ – Морса в приведенной выше форме как последовательность битов может быть определена рекурсивно с помощью операции побитового отрицания . Итак, первый элемент равен 0. Затем, как только первые 2 n элементов были указаны, образуя строку s , следующие 2 n элементов должны образовать побитовое отрицание s . Теперь мы определили первые 2 n + 1 элементов и приступаем к рекурсии.
Подробное изложение первых нескольких шагов:
- Начнем с 0.
- Побитовое отрицание 0 равно 1.
- Объединяя их, первые 2 элемента - 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.
Некоторые свойства
Поскольку каждый новый блок в последовательности Туэ – Морса определяется путем формирования побитового отрицания начала, и это повторяется в начале следующего блока, последовательность Туэ – Морса заполняется квадратами : последовательными строками, которые повторяются. То есть существует множество экземпляров XX , где X - некоторая строка. Действительно, такая строка тогда и только тогда, когда или же где для некоторых а также обозначает побитовое отрицание (меняем местами 0 и 1). [4] Например, с, у нас есть , и квадрат появляется в начиная с 16-го бита. (Таким образом, квадраты вимеют длину, равную степени 2 или 3, умноженной на 2). Однако кубов нет : экземпляры XXX . Там нет также нет перекрывающихся квадратов : экземпляры 0 X 0 X 0 или 1 Х 1 Х 1. [5] [6] критический показатель равен 2. [7]
Последовательность T 2 n является палиндромом для любого n . Далее, пусть q n - слово, полученное из T 2 n путем подсчета единиц между последовательными нулями. Например, q 1 = 2, q 2 = 2102012 и так далее. Слова T n не содержат перекрывающихся квадратов, следовательно, слова q n являются палиндромными бесквадратными словами .
Вышеупомянутое утверждение о том, что последовательность Туэ – Морса «заполнена квадратами», можно уточнить: это равномерно повторяющееся слово , означающее, что для любой конечной строки X в последовательности существует некоторая длина n X (часто намного длиннее, чем длина X ) такое , что X появляется в каждом блоке длины п X . [8] [9] Самый простой способ создать повторяющуюся последовательность - сформировать периодическую последовательность , в которой последовательность полностью повторяется после заданного количества шагов m . Тогда п Х может быть установлен на любое кратное м , который больше , чем в два раза длины X . Но последовательность Морса является равномерно рекуррентной, но не периодической, даже в конечном итоге периодической (то есть периодической после некоторого непериодического начального сегмента). [10]
Мы определяем морфизм Туэ – Морса как функцию f из набора двоичных последовательностей к себе, заменяя каждый 0 в последовательности на 01 и каждую единицу на 10. [11] Тогда, если T - последовательность Туэ – Морса, то f ( T ) снова является T ; то есть, Т является фиксированной точкой из F . Функция F является могущий быть продленным морфизм на свободном моноиде {0,1} * с Т в фиксированной точке: в самом деле, Т , по существу, только фиксированная точка F ; единственная другая фиксированная точка - это побитовое отрицание T , которое представляет собой просто последовательность Туэ – Морса на (1,0) вместо на (0,1). Это свойство можно обобщить до концепции автоматической последовательности .
Производящий ряд из Т над бинарным полем является формальным степенным рядом
Этот степенной ряд является алгебраическим над полем рациональных функций, удовлетворяющих уравнению [12]
В комбинаторной теории игр
Набор злых чисел (чисел с участием ) образует подпространство неотрицательных целых чисел при добавлении ним ( побитовое исключающее ИЛИ ). В игре Кейлза злые значения нима встречаются для нескольких (конечного числа) позиций в игре, при этом все оставшиеся позиции имеют одиозные значения нима.
Проблема Пруэ – Тарри – Эскотта
Проблема Пруэ-Тарри-Эскотт может быть определена как: дано положительное целое число N и неотрицательное целое число K , разбиение множества S = {0, 1, ..., N -1} на два непересекающихся подмножества S 0 и S 1, которые имеют равные суммы степеней до k, то есть:
- для всех целых чисел i от 1 до k .
У этого есть решение, если N кратно 2 k +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 k +1 , не является строго необходимым: есть еще несколько случаев, для которых существует решение. Однако это гарантирует более сильное свойство: если условие выполняется, то набор k- й степени любого набора из N чисел в арифметической прогрессии может быть разделен на два набора с равными суммами. Это следует непосредственно из разложения, данного биномиальной теоремой, примененной к биному, представляющему n- й элемент арифметической прогрессии.
Об обобщении последовательности Туэ – Морса и проблемы Пруэ – Тарри – Эскотта на разбиение более чем на две части см. Болкер, Оффнер, Ричман и Зара, «Проблема Пруэ – Тарри – Эскотта и обобщенные последовательности Туэ – Морса». [13]
Фракталы и графика черепахи
Используя графику черепахи , можно сгенерировать кривую, если автомат запрограммирован с помощью последовательности. Когда члены последовательности Туэ – Морзе используются для выбора состояний программы:
- Если t ( n ) = 0, продвинемся на одну единицу вперед,
- Если t ( n ) = 1, повернуть на угол π / 3 радиан (60 °).
Полученная кривая сходится к кривой Коха , фрактальной кривой бесконечной длины, содержащей конечную площадь. Это иллюстрирует фрактальную природу последовательности Туэ – Морса. [14]
Также можно точно нарисовать кривую, используя следующие инструкции: [15]
- Если t ( n ) = 0, повернуть на угол π радиан (180 °),
- Если t ( n ) = 1, продвиньтесь на одну единицу вперед, а затем поверните на угол π / 3 радиан.
Справедливая последовательность
В своей книге о проблеме справедливого разделения , Стивен Брамс и Алан Тейлор вызываются последовательность Туэ-Морс , но не идентифицировали его как таковые. Распределяя оспариваемую кучу предметов между двумя сторонами, которые согласны относительно относительной ценности предметов, Брамс и Тейлор предложили метод, который они назвали сбалансированным чередованием , или по очереди по очереди. . . , как способ обойти фаворитизм, присущий, когда одна сторона делает выбор перед другой. Пример показал, как разводящаяся пара может достичь справедливого урегулирования при распределении вещей, находящихся в совместном владении. Стороны по очереди будут первыми выбирать на разных этапах процесса выбора: Энн выбирает один пункт, затем Бен, затем Бен выбирает один пункт, затем делает Энн. [16]
Лайонел Левин и Кэтрин Штанге в своем обсуждении того, как справедливо распределить общую трапезу, например эфиопский обед , предложили последовательность Туэ – Морзе как способ уменьшить преимущество движения первым. Они предположили, что «было бы интересно количественно оценить интуицию о том, что порядок Туэ-Морса имеет тенденцию давать справедливый результат». [17]
Роберт Ричман обратился к этой проблеме, но он также не идентифицировал последовательность Туэ – Морса как таковую на момент публикации. [18] Он представил последовательности T n как ступенчатые функции на интервале [0,1] и описал их связь с функциями Уолша и Радемахера . Он показал , что п - й производной может быть выражено в терминах Т н . Как следствие, функция шага , вытекающая из Т п является ортогональной к многочленам от порядка п - 1. Следствия этого результата является то , что ресурс , значение которого выражаются в виде монотонно убывающей непрерывной функции наиболее справедливо распределен с использованием последовательности , которая сходится к Туэ-Морс, поскольку функция становится более плоской . Пример показал, как налить чашки кофе одинаковой крепости из графина с нелинейным градиентом концентрации , что вызвало появление причудливой статьи в популярной прессе. [19]
Джошуа Купер и Аарон Датл показали, почему порядок Туэ-Морса обеспечивает справедливый исход для отдельных событий. [20] Они считали самый справедливый способ устроить дуэль Галуа , в которой каждый из стрелков имеет одинаково плохие навыки стрельбы. Купер и Датл постулировали, что каждый дуэлянт будет требовать шанс выстрелить, как только априорная вероятность выигрыша другого игрока превысит его собственную. Они доказали, что по мере приближения вероятности попадания дуэлей к нулю последовательность увольнения сходится к последовательности Туэ – Морса. При этом они продемонстрировали, что порядок Туэ-Морса дает хороший результат не только для последовательностей T n длины 2 n , но и для последовательностей любой длины.
Таким образом, математика поддерживает использование последовательности Туэ – Морса вместо чередования поворотов, когда целью является честность, но более ранние повороты монотонно отличаются от более поздних поворотов некоторым значимым качеством, независимо от того, изменяется это качество непрерывно [18] или дискретно. [20]
Спортивные соревнования образуют важный класс задач равной последовательности, потому что строгое чередование часто дает несправедливое преимущество одной команде. Игнасио Паласиос-Уэрта предложил изменить порядок следования на Туэ-Морс, чтобы улучшить объективность ex post различных турниров, таких как последовательность ударов ногами в серии пенальти в футболе. [21] Он провел ряд полевых экспериментов с профессиональными игроками и обнаружил, что команда, пинающая первой, выиграла 60% игр с использованием ABAB (или T 1 ), 54% с использованием ABBA (или T 2 ) и 51% с использованием полного Thue- Морс (или Т н ). В результате ABBA проходит обширные испытания в ФИФА (чемпионаты Европы и мира) и английской федерации профессионального футбола ( Кубок EFL ). [22] Также было обнаружено, что схема подачи ABBA улучшает справедливость тай-брейков в теннисе . [23] В конкурентных греб , Т 2 является единственным расположением port- и правого борт-греб член экипажа , что исключает поперечные силы (и , следовательно , боковое покачивание) на четыре-членный coxless гоночной лодки, в то время как Т 3 является одним из четырех буровых установок чтобы не покачиваться на восьмичленной лодке. [24]
Честность особенно важна в драфтах игроков . Многие профессиональные спортивные лиги пытаются достичь конкурентного паритета , отдавая более ранние выборы в каждом раунде более слабым командам. Напротив, лиги фэнтези-футбола не имеют ранее существовавшего дисбаланса, который нужно исправить, поэтому они часто используют «змейку» (вперед, назад и т. Д .; или T 1 ). [25] Ян Аллан утверждал, что «разворот в третьем раунде» (вперед, назад, назад, вперед и т.д .; или T 2 ) был бы еще более справедливым. [26] Ричман предположил, что наиболее справедливый способ для «капитана А» и «капитана Б» выбирать стороны для игры в баскетбол отражает Т 3 : капитан А имеет первый, четвертый, шестой и седьмой варианты выбора, в то время как капитан У B есть второй, третий, пятый и восьмой варианты. [18]
История
Последовательность Туэ – Морса была впервые изучена Эженом Пруэ в 1851 г. [27], который применил ее к теории чисел . Однако Пруэ не упомянул последовательность явно; это было оставлено Акселю Туэ в 1906 году, который использовал его, чтобы основать изучение комбинаторики слов . Последовательность была доведена до всеобщего внимания только в работе Марстона Морса в 1921 году, когда он применил ее к дифференциальной геометрии . Последовательность была открыта независимо много раз, не всегда профессиональными математиками-исследователями; например, Макс Эйве , шахматный гроссмейстер , обладавший титулом чемпиона мира с 1935 по 1937 год, и учитель математики , открыл его в 1929 году в приложении к шахматам : используя его свойство отсутствия куба (см. выше), он показал, как обойти правило, направленное на предотвращение бесконечно затяжных игр, объявив повтор ходов ничьей.
Смотрите также
- Теорема Дежана
- Функция Фабиуса
- Код Грея [28] [29] [30]
- Константа Коморника – Лорети
- Постоянная Пруэ – Туэ – Морса
Заметки
- ^ a b Allouche & Shallit (2003 , с. 15)
- Перейти ↑ Arndt (2011) .
- ^ Lothaire (2011 , стр. 11)
- ^ Brlek (1989) .
- ^ Lothaire (2011 , стр. 113)
- ^ Pytheas Фогг (2002 , стр. 103)
- Перейти ↑ Krieger (2006) .
- ^ Lothaire (2011 , стр. 30)
- ^ Берте и Риго (2010) .
- ^ Lothaire (2011 , стр. 31)
- ^ Berstel et al. (2009 , с. 70)
- ^ Berstel et al. (2009 , с. 80)
- ^ Bolker et al. (2016) .
- ^ Ma & Holdener (2005) .
- ↑ Abel, Zachary (23 января 2012 г.). "Плавучие черепахи Туэ-Морса" . Трехсторонние вещи .
- ^ Брамс & Taylor (1999) .
- ^ Levine & Штанге (2012) .
- ^ a b c Ричман (2001)
- Перейти ↑ Abrahams (2010) .
- ^ a b Купер и Датл (2013)
- Перейти ↑ Palacios-Huerta (2012) .
- ^ Паласиос-Уэрта (2014) .
- ^ Коэн-зад, Крумер & Шапир (2018) .
- ^ Барроу (2010) .
- ^ «Фантазия Проект Типы» . NFL.com . Архивировано из оригинального 12 октября 2018 года.
- ^ Аллан, Ян (16 июля 2014 г.). «Реверсивные шашки третьего раунда» . Индекс фантазии . Проверено 1 сентября 2020 года .
- ^ Вездесущий последовательность Пруэ-Туэ- Морзе Жан-Поль ALLOUCHE и Джеффри Шаллит
- ^ Фредриксен, Гарольд (1992). «Коды Грея и последовательность Туэ-Морса-Хедлунда». Журнал комбинаторной математики и комбинаторных вычислений (JCMCC) . Военно-морская аспирантура, математический факультет, Монтерей, Калифорния, США. 11 : 3–11.
- ^ Эриксон, Джон (30.10.2018). "Об асимптотическом относительном изменении последовательностей перестановок" . Проверено 31 января 2021 . [1]
- ^ Плюсос, Джордж (21.06.2020). «Какая связь между кодом Грея и последовательностью Туэ-Морзе» . Quora . Архивировано 17 декабря 2020 года . Проверено 31 января 2021 .
Рекомендации
- Абрахамс, Марк (12 июля 2010 г.). «Как налить идеальную чашку кофе» . Хранитель .
- Арндт, Йорг (2011). «1.16.4 Последовательность Туэ – Морса» (PDF) . Вопросы вычислительные: идеи, алгоритмы, исходный код . Springer. п. 44.
- Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6. Zbl 1086.11015 .
- Барроу, Джон Д. (2010). «Гребля и задача с одинаковой суммой имеют свои моменты». Американский журнал физики . 78 (7): 728–732. arXiv : 0911.3551 . Bibcode : 2010AmJPh..78..728B . DOI : 10.1119 / 1.3318808 .
- Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Слова Кристоффеля и их повторы . Серия монографий CRM. 27 . Провиденс, Род-Айленд, США: Американское математическое общество . ISBN 978-0-8218-4480-9. Zbl 1161.68043 .
- Берте, Валери ; Риго, Мишель, ред. (2010). Комбинаторика, автоматы и теория чисел . Энциклопедия математики и ее приложений. 135 . Кембридж: Издательство Кембриджского университета . п. 7. ISBN 978-0-521-51597-9. Zbl 1197.68006 .
- Болкер, Итан; Оффнер, Карл; Ричман, Роберт; Зара, Каталин (2016). «Проблема Пруэ – Тарри – Эскотта и обобщенные последовательности Туэ – Морса». Журнал комбинаторики . 7 (1): 117–133. arXiv : 1304,6756 . DOI : 10,4310 / JOC.2016.v7.n1.a5 .}
- Брамс, Стивен Дж .; Тейлор, Алан Д. (1999). Беспроигрышное решение: гарантия справедливой доли участия для всех . WW Norton & Co., Inc., стр. 36–44 . ISBN 978-0-393-04729-5.
- Брлек, Сречко (1989). «Перечень факторов в слове Туэ-Морзе». Дискретная прикладная математика . 24 (1–3): 83–96. DOI : 10.1016 / 0166-218x (92) 90274-e .
- Коэн-Зада, Дэнни; Крумер, Алекс; Шапир, Предложение Моше (2018). «Тестирование эффекта порядка подачи в теннисном тай-брейке» . Журнал экономического поведения и организации . 146 : 106–115.
- Купер, Джошуа; Датл, Аарон (2013). «Жадные игры Галуа» (PDF) . Американский математический ежемесячник . 120 (5): 441–451. arXiv : 1110.1137 . DOI : 10,4169 / amer.math.monthly.120.05.441 .
- Кригер, Далия (2006). «О критических показателях в неподвижных точках нестираемых морфизмов». В Ибарре, Оскар Х .; Данг, Чжэ (ред.). Развитие теории языка: Труды 10 - й Международной конференции, DLT 2006, Санта - Барбара, штат Калифорния, США, 26-29 июня 2006 года . Конспект лекций по информатике. 4036 . Springer-Verlag . С. 280–291. ISBN 978-3-540-35428-4. Zbl 1227.68074 .
- Левин, Лайонел; Штанге, Кэтрин Э. (2012). «Как извлечь максимальную пользу из общей еды: сначала спланируйте последний укус» (PDF) . Американский математический ежемесячник . 119 (7): 550–565. arXiv : 1104.0961 . DOI : 10,4169 / amer.math.monthly.119.07.550 .
- Лотэр, М. (2011). Алгебраическая комбинаторика слов . Энциклопедия математики и ее приложений. 90 . С предисловием Жана Берштеля и Доминика Перрена (перепечатка изд. В твердой обложке 2002 г.) Издательство Кембриджского университета. ISBN 978-0-521-18071-9. Zbl 1221.68183 .
- Ма, июнь; Холденер, Джуди (2005). «Когда Туэ-Морс встречает Коха» (PDF) . Фракталы . 13 (3): 191–206. DOI : 10.1142 / S0218348X05002908 . Руководство по ремонту 2166279 .
- Паласиос-Уэрта, Игнасио (2012). «Турниры, справедливость и последовательность Пруэ – Туэ – Морса» (PDF) . Экономический запрос . 50 (3): 848–849. DOI : 10.1111 / j.1465-7295.2011.00435.x .
- Паласиос-Уэрта, Игнасио (2014). Прекрасная теория игр . Издательство Принстонского университета. ISBN 978-0691144023.
- Пифей Фогг, Н. (2002). Берте, Валери; Ференци, Себастьен; Mauduit, Christian; Сигель, А. (ред.). Подстановки в динамике, арифметике и комбинаторике . Конспект лекций по математике. 1794 . Берлин, Германия: Springer-Verlag . ISBN 978-3-540-44141-0. Zbl 1014.11015 .
- Ричман, Роберт (2001). «Рекурсивные двоичные последовательности различий» (PDF) . Сложные системы . 13 (4): 381–392.
дальнейшее чтение
- Буджо, Янн (2012). Распределение по модулю один и диофантово приближение . Кембриджские трактаты по математике. 193 . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-11169-0. Zbl 1260.11001 .
- Лотэр, М. (2005). Прикладная комбинаторика слов . Энциклопедия математики и ее приложений. 105 . Коллективный труд Жан Berstel Доминик Перрен, Максим Крошемор, Эрик Лапорта, Меряр Мори, Надя Pisanti, Мари-Франс Sagot, Гезине Рейнертом , Софи Schbath , Майкл Waterman, Филипп Жаке, Войцех Szpankowski , Доминик Poulalhon, Жиль Шеффера, Роман Колпаков , Грегори Кушеров, Жан-Поль Аллуш и Валери Берте. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-84802-2. Zbl 1133.68067 .
Внешние ссылки
- "Последовательность Туэ-Морса" , Энциклопедия математики , EMS Press , 2001 [1994]
- Вайсштейн, Эрик В. «Последовательность Туэ-Морса» . MathWorld .
- Allouche, J.-P .; Шаллит, Д.О. Вездесущая последовательность Пруэ-Туэ-Морса . (содержит много приложений и немного истории)
- Последовательность Туэ – Морса над (1,2) (последовательность A001285 в OEIS )
- Последовательность OEIS A000069 (одиозные числа: числа с нечетным числом единиц в их двоичном расширении)
- Последовательность OEIS A001969 (злые числа: числа с четным числом единиц в их двоичном расширении)
- Уменьшение влияния дрейфа смещения постоянного тока в аналоговых IP-адресах с помощью последовательности Туэ-Морса . Техническое применение последовательности Туэ – Морзе
- MusiNum - Музыка в цифрах . Бесплатное ПО для создания самоподобной музыки на основе последовательности Туэ – Морса и связанных числовых последовательностей.
- Паркер, Мэтт . "Самый справедливый эпизод обмена" (видео) . Standupmaths . Проверено 20 января +2016 .