Sekce Thue – Morse - Thue–Morse sequence

Tato grafika ukazuje opakující se a doplňující sekvence sekvence Thue – Morse.

V matematiky je sekvence Thue-Morse , nebo Prouhet-Thue-Morse sekvence , je binární sekvence (nekonečný sled 0 a 1), získané tím, že začíná 0 a postupně připojením Logická komplement sekvence získané tak daleko. Prvních několik kroků tohoto postupu poskytne řetězce 0, pak 01, 0110, 01101001, 0110100110010110 atd., Které jsou předponou sekvence Thue – Morse. Celá sekvence začíná:

01101001100101101001011001101001 .... (sekvence A010060 v OEIS )

Sekvence je pojmenována po Axel Thue a Marston Morse .

Definice

Existuje několik ekvivalentních způsobů definování sekvence Thue – Morse.

Přímá definice

Při počítání v binárním čísle je modulo sum 2 modu Thue – Morseova posloupnost

Pro výpočet n -tého prvku t _n , napsat číslo n v binární . Je -li počet jedniček v této binární expanzi lichý, pak t _n  = 1, pokud dokonce pak t _n  = 0. Z tohoto důvodu John H. Conway a kol . volejte čísla n vyhovující t _n  = 1 odporná (pro lichá ) čísla a čísla, pro která t _n  = 0 zlá (pro sudá ) čísla. Jinými slovy, t _n  = 0, pokud n je zlé číslo a t _n  = 1, pokud n je odporné číslo .

Rychlé generování sekvence

Tato metoda vede k rychlé metodě pro výpočet Thue – Morseovy sekvence: začněte s t ₀  = 0 a pak pro každé n najděte bit nejvyššího řádu v binární reprezentaci n, který se liší od stejného bitu v reprezentace n  - 1 . (Tento bit lze izolovat tak, že necháme x jako bitový výlučný nebo n a n  - 1 , posuneme x přímo o jeden bit a vypočítáme exkluzivní nebo posunutou hodnotu pomocí x .) Pokud je tento bit na sudém indexu, t _{n se} liší od t _{n  - 1} , a jinak je stejné jako t _{n  - 1} .

Ve formě pseudokódu:

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

Výsledný algoritmus generuje každý prvek sekvence konstantní čas, přičemž používá pouze logaritmický počet bitů (konstantní počet slov) paměti.

Vztah opakování

Posloupnost Thue – Morse je sekvence t _{n, která} splňuje relaci opakování

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

pro všechna nezáporná celá čísla n .

L-systém

Sekvence Thue – Morse generovaná L-systémem

Sekvence Thue – Morse je morfické slovo : je výstupem následujícího systému Lindenmayer :

Charakterizace pomocí bitové negace

Posloupnost Thue – Morse ve výše uvedené formě, jako posloupnost bitů , lze definovat rekurzivně pomocí operace bitové negace . První prvek je tedy 0. Poté, co byly zadány první 2 ⁿ prvky, které tvoří řetězec s , pak další 2 ⁿ prvky musí tvořit bitovou negaci s . Nyní jsme definovali první 2 ^{n +1} prvky a rekurzujeme.

Podrobně vysvětlete prvních pár kroků:

• Začínáme 0.
• Bitová negace 0 je 1.
• Jejich kombinací jsou první 2 prvky 01.
• Bitová negace 01 je 10.
• Jejich kombinací jsou první 4 prvky 0110.
• Bitová negace 0110 je 1001.
• Jejich kombinací je prvních 8 prvků 01101001.
• A tak dále.

Tak

• T ₀ = 0.
• T ₁ = 01.
• T ₂ = 0110.
• T ₃ = 01101001.
• T ₄ = 0110100110010110.
• T ₅ = 01101001100101101001011001101001.
• T ₆ = 0110100110010110100101100110100110010110011010010110100110010110.
• A tak dále.

Nekonečný produkt

Sekvence může být také definována:

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

kde t _j je j -tý prvek, pokud začínáme na j = 0.

Některé vlastnosti

Protože každý nový blok v sekvenci Thue – Morse je definován vytvořením bitové negace začátku, a to se opakuje na začátku dalšího bloku, sekvence Thue – Morse je vyplněna čtverci : po sobě jdoucími řetězci, které se opakují. To znamená, že existuje mnoho instancí XX , kde X je nějaký řetězec. Ve skutečnosti, je takový řetězec, pokud a pouze v případě, nebo pokud pro některé a označuje bitového doplňku (výměny 0 a 1). Například s , máme a čtverec se objeví od 16. bitu. (Čtverce mají tedy délku buď 2 nebo 3krát mocninu 2.) Neexistují však žádné kostky : instance XXX . Neexistují také žádné překrývající se čtverce : instance 0 X 0 X 0 nebo 1 X 1 X 1. Kritický exponent je 2. ${\ displaystyle X}$${\ Displaystyle X = A, \, {\ overline {A}}, \, A {\ overline {A}} A,}$${\ displaystyle {\ overline {A}} A {\ overline {A}}}$${\ displaystyle A = T_ {k}}$${\ Displaystyle k \ geq 0}$${\ displaystyle {\ overline {A}}}$${\ displaystyle A}$${\ displaystyle k = 0}$${\ displaystyle \ A = T_ {0} = 0}$${\ displaystyle A {\ overline {A}} AA {\ overline {A}} A = 010010}$${\ displaystyle T}$${\ displaystyle T}$

Sekvence T _{2 n} je palindrom pro jakékoli n . Dále nechť q _n je slovo získané z T _{2 n} počítáním jedniček mezi po sobě jdoucími nulami. Například q ₁ = 2 a q ₂ = 2102012 atd. Slova T _n v důsledku neobsahují překrývající se čtverce , slova q _n jsou slova bez palindromových čtverců .

Výše uvedené tvrzení, že sekvence Thue – Morse je „plná čtverců“, lze upřesnit: Je to rovnoměrně se opakující slovo , což znamená, že vzhledem k jakémukoli konečnému řetězci X v sekvenci existuje určitá délka n _X (často mnohem delší než délka X ) tak, že X se objeví v každém bloku délky n _X . Nejjednodušší způsob, jak vytvořit opakující se sekvenci, je vytvořit periodickou sekvenci , takovou, kde se sekvence zcela opakuje po daném počtu m kroků. Pak se n _X lze nastavit na libovolnou násobku m , která je větší než dvojnásobek délky X . Ale Morseova sekvence je rovnoměrně opakující se, aniž by byla periodická, dokonce ani nakonec periodická (což znamená periodická po nějakém neperiodickém počátečním segmentu).

Definujeme Thue-Morse morphism být funkce f z množiny binárních sekvencí k sobě tím, že nahradí každý 0 v sekvenci s 01 a každou 1 s 10. Pak, pokud T je sekvence Thue-Morse, pak f ( T ) je opět T ; to znamená, že T je pevný bod na f . Funkce f je prodloužitelný morfismus na volném monoidu {0,1} ^∗ s T jako pevným bodem: ve skutečnosti je T v podstatě jediným pevným bodem f ; jediným dalším pevným bodem je bitová negace T , což je jednoduše sekvence Thue – Morse na (1,0) místo na (0,1). Tuto vlastnost lze zobecnit na koncept automatické sekvence .

Série generující of T přes binární pole je formální výkon série

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

Tato mocninová řada je v oblasti racionálních funkcí algebraická a splňuje rovnici

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

V teorii kombinatorických her

Množina zlých čísel (čísla s ) tvoří podprostor nezáporných celých čísel pod nim-addition ( bitwise exclusive or ). Pro hru Kayles se zlé nimové hodnoty vyskytují na několika (nakonec mnoha) pozicích ve hře, přičemž všechny zbývající pozice mají odporné nimové hodnoty. ${\ displaystyle n}$${\ displaystyle t_ {n} = 0}$

Problém Prouhet – Tarry – Escott

Problém Prouhet – Tarry – Escott lze definovat jako: dané kladné celé číslo N a nezáporné celé číslo k , rozdělte množinu S = {0, 1, ..., N -1} na dvě disjunktní podmnožiny S ₀ a S _1, které mají stejné součty mocnin až k, to znamená:

${\ Displaystyle \ sum _ {x \ in S_ {0}} x^{i} = \ sum _ {x \ in S_ {1}} x^{i}}$pro všechna celá čísla i od 1 do k .

To má řešení, pokud N je násobek 2 ^{k +1} , daný:

• S _{0 se} skládá z celých čísel n v S, pro která t _n = 0,
• S _{1 se} skládá z celých čísel n v S, pro která t _n = 1.

Například pro N = 8 a k = 2,

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

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

Podmínka, která vyžaduje, aby N byl násobek 2 ^{k +1,} není nezbytně nutná: existuje několik dalších případů, pro které existuje řešení. Zaručuje však silnější vlastnost: pokud je podmínka splněna, pak sadu k th mocnin libovolné sady N čísel v aritmetické progresi lze rozdělit na dvě sady se stejnými součty. To vyplývá přímo z expanze dané binomickou větou aplikovanou na binomickou představující n -tý prvek aritmetické progrese.

Zobecnění Thue – Morseovy sekvence a Prouhet – Tarry – Escottova problému na rozdělení na více než dvě části viz Bolker, Offner, Richman a Zara, „Problém Prouhet – Tarry – Escott a zobecněné Thue – Morseovy sekvence“.

Fraktály a želva grafika

Pomocí želví grafiky lze vygenerovat křivku, pokud je automat naprogramován pomocí sekvence. Když jsou členy sekvence Thue – Morse použity k výběru stavů programu:

• Pokud t ( n ) = 0, posuňte se o jednu jednotku dopředu,
• Pokud t ( n ) = 1, otočte o úhel π/3 radiánů (60 °)

Výsledná křivka konverguje ke Kochově křivce , fraktální křivce nekonečné délky obsahující konečnou oblast. To ilustruje fraktální povahu sekvence Thue – Morse.

Křivku je také možné nakreslit přesně podle následujících pokynů:

• Pokud t ( n ) = 0, otočte o úhel π radiánů (180 °),
• Je -li t ( n ) = 1, posuňte se o jednu jednotku dopředu a poté otočte o úhel π/3 radiánů.

Spravedlivé sekvenování

Ve své knize o problému spravedlivé rozdělení , Steven Brams a Alan Taylor vyvolán sled Thue-Morse ale neidentifikoval to jako takový. Při přidělování napadené hromady položek mezi dvě strany, které se shodly na relativních hodnotách položek, Brams a Taylor navrhli metodu, kterou nazývali vyvážené střídání , nebo střídání se při střídání . . . , jako způsob, jak obejít zvýhodňování, které je vlastní, když si jedna strana vybere před druhou. Příklad ukázal, jak by se rozvádějící se pár mohl dosáhnout spravedlivého vypořádání při distribuci spoluvlastnických věcí. Strany by se střídaly, aby byly prvními, kdo volil v různých bodech výběrového procesu: Ann si vybere jednu položku, pak Ben udělá, pak Ben vybere jednu položku a pak Ann.

Lionel Levine a Katherine E. Stange ve své diskusi o tom, jak spravedlivě rozdělit sdílené jídlo, jako je etiopská večeře , navrhly sekvenci Thue – Morse jako způsob, jak omezit výhodu prvního pohybu. Navrhli, že „by bylo zajímavé kvantifikovat intuici, že řád Thue – Morse má tendenci vytvářet spravedlivý výsledek“.

Robert Richman se tomuto problému věnoval, ale ani on v době vydání neidentifikoval sekvenci Thue – Morse jako takovou. Sekvence T _{n představil} jako krokové funkce na intervalu [0,1] a popsal jejich vztah k Walshovým a Rademacherovým funkcím. Ukázal, že n -tou derivaci lze vyjádřit pomocí T _n . V důsledku toho, že krok funkce vyplývající z T _n je kolmá k polynomy v pořadí n  - 1. Důsledkem tohoto výsledku je, že zdroj, jehož hodnota je vyjádřena jako monotónně klesající spojité funkce je nejvíce spravedlivě rozdělovány pomocí sekvenci, která konverguje k Thue – Morse, jak se funkce stává plošší . Příklad ukázal, jak nalít šálky kávy stejné síly z karafy s nelineárním gradientem koncentrace , což vyvolalo rozmarný článek v populárním tisku.

Joshua Cooper a Aaron Dutle ukázali, proč řád Thue – Morse poskytuje spravedlivý výsledek pro diskrétní události. Považovali za nejférovější způsob, jak uspořádat duel Galois , ve kterém má každý ze střelců stejně špatné střelecké schopnosti. Cooper a Dutle předpokládali, že každý dueler bude požadovat šanci vystřelit, jakmile bude apriorní pravděpodobnost výhry druhého vyšší než ta jejich. Dokázali, že když se pravděpodobnost zasažení duelu blíží nule, sekvence střelby konverguje k sekvenci Thue – Morse. Přitom prokázali, že řád Thue – Morse vytváří spravedlivý výsledek nejen pro sekvence T _n o délce 2 ⁿ , ale pro sekvence jakékoli délky.

Matematika tedy podporuje použití Thue -Morseovy sekvence místo střídání zatáček, když je cílem férovost, ale dřívější zatáčky se v některých smysluplných kvalitách monotónně liší od pozdějších, ať už se tato kvalita mění kontinuálně nebo diskrétně.

Sportovní soutěže tvoří důležitou třídu spravedlivých problémů se sekvenováním, protože přísné střídání často dává jednomu týmu nefér výhodu. Ignacio Palacios-Huerta navrhl změnit sekvenční pořadí na Thue – Morse, aby se zlepšila ex post spravedlnost různých turnajových soutěží, jako je kopací sekvence penaltového rozstřelu ve fotbale. Udělal řadu terénních experimentů s profesionálními hráči a zjistil, že tým, který kopal, nejprve vyhrál 60% her pomocí ABAB (nebo T ₁ ), 54% pomocí ABBA (nebo T ₂ ) a 51% pomocí plné Thue – Morse (nebo T _n ). Výsledkem je, že ABBA prochází rozsáhlými zkouškami v profesionálním fotbale FIFA (mistrovství Evropy a světa) a anglické federace ( EFL Cup ). Bylo také zjištěno, že vzor podávání ABBA zlepšuje spravedlnost tenisových tie-breaků . V soutěžním veslování je T ₂ jediným uspořádáním členů posádky veslování na levoboku i na pravoboku, které eliminuje příčné síly (a tím i kroutí do stran) na čtyřčlenném bezkolejném závodním člunu, zatímco T ₃ je jednou ze čtyř souprav, které se vyhýbají vrtění na osmičlenném člunu.

Spravedlnost je obzvláště důležitá v konceptech hráčů . Mnoho profesionálních sportovních lig se pokouší dosáhnout konkurenční parity tím, že dřívější výběr v každém kole dává slabším týmům. Naproti tomu fantasy fotbalové ligy nemají již existující nerovnováhu k nápravě, takže často používají „hadí“ tah (dopředu, dozadu atd .; nebo T ₁ ). Ian Allan tvrdil, že „obrácení třetího kola“ (vpřed, vzad, vzad, vpřed atd .; nebo T ₂ ) by bylo ještě spravedlivější. Richman navrhl, že nejspravedlivější způsob, jak si „kapitán A“ a „kapitán B“ vybrat strany pro sběrnou hru basketbalových zrcadel T ₃ : kapitán A má první, čtvrtou, šestou a sedmou možnost, zatímco kapitán B má druhá, třetí, pátá a osmá volba.

Dějiny

Sekvence Thue – Morse byla poprvé studována Eugènem Prouhetem v roce 1851, který ji aplikoval na teorii čísel . Prouhet však sekvenci výslovně nezmínil; toto bylo ponecháno Axelovi Thueovi v roce 1906, který jej použil k založení studia kombinatoriky slov . Sekvence se dostala do celosvětové pozornosti až s prací Marstona Morse v roce 1921, kdy ji aplikoval na diferenciální geometrii . Sekvence byla mnohokrát objevena nezávisle, ne vždy profesionálními matematiky výzkumu; například Max Euwe , šachový velmistr , který v letech 1935 až 1937 držel titul mistra světa, a učitel matematiky , jej objevil v roce 1929 v šachové aplikaci : pomocí vlastnosti bez kostek (viz výše) ukázal, jak obejít pravidlo trojnásobného opakování, jehož cílem je zabránit nekonečně zdlouhavým hrám, vyhlášením opakování tahů za remízu. V té době byly ke spuštění pravidla požadovány po sobě jdoucí shodné státy představenstva; pravidlo bylo později pozměněno tak, aby se stejná pozice desky opakovala třikrát za sebou v libovolném bodě, protože sekvence ukazuje, že po sobě jdoucímu kritériu lze navždy uniknout.

Viz také

• Dejeanova věta
• Funkce Fabius
• Šedý kód
• Konstanta Komornik – Loreti
• Konstanta Prouhet – Thue – Morse

Poznámky

Reference

Další čtení

• Bugeaud, Yann (2012). Distribuční modul jedna a diofantická aproximace . Cambridgeské tratě v matematice. 193 . Cambridge: Cambridge University Press . ISBN 978-0-521-11169-0. Zbl  1260.11001 .
• Lothaire, M. (2005). Aplikovaná kombinatorika na slova . Encyklopedie matematiky a její aplikace. 105 . Kolektivní dílo Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolp , Gregory Koucherov, Jean-Paul Allouche a Valérie Berthé. Cambridge: Cambridge University Press . ISBN 978-0-521-84802-2. Zbl  1133.68067 .

externí odkazy

• „Thue-Morseova sekvence“ , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Weisstein, Eric W. „Thue-Morseova sekvence“ . MathWorld .
• Allouche, J.-P .; Shallit, JO Všudypřítomná sekvence Prouhet-Thue-Morse . (obsahuje mnoho aplikací a nějakou historii)
• Sekvence Thue – Morse přes (1,2) (sekvence A001285 v OEIS )
• Sekvence OEIS A000069 (Podivná čísla: čísla s lichým počtem 1 v binární expanzi)
• Sekvence OEIS A001969 (Zlá čísla: čísla se sudým počtem 1 v jejich binární expanzi)
• Snížení vlivu posunu DC ofsetu v analogových IP pomocí Thue-Morseovy sekvence . Technická aplikace sekvence Thue – Morse
• MusiNum - Hudba v číslech . Freeware pro generování hudby podobné na základě sekvence Thue – Morse a souvisejících číselných sekvencí.
• Parker, Matt . „Nejférovější sekvence sdílení vůbec“ (video) . stoupenci . Citováno 20. ledna 2016 .