Matematická řešení lze nalézt na překvapivých místech, včetně temných říší internetu. V roce 2011 anonymní plakát na nyní neslavně kontroverzní obrazové desce 4chan představoval matematickou hádanku o kultovní klasické anime sérii Melancholie Haruhi Suzumiya. Přestože se Bulletinová deska stala posypanou nenávistným, násilným a extrémním obsahem, tento původní příspěvek vedl k řešení sofistikovaného matematického problému.
První sezóna této série Anime se skládá ze 14 epizod, které byly navrženy tak, abyste je mohli sledovat v libovolném pořadí, které se vám líbí. (Pro lidi, kteří jsou s anime světem stejně obeznámeni jako já: volal osmidílný živý thriller Kaleidoskop Na Netflixu sleduje stejný princip.) V určitém okamžiku v diskusi o sérii z roku 2011 se někdo zeptal na minimální počet epizod, které by museli sledovat, aby to viděli v každém možném pořadí.
Tato otázka ve skutečnosti souvisí s tzv. Superpermutacemi. A jak se ukázalo, tato matematická oblast drží mnoho hádanek: dodnes nejsou matematici stále schopni plně odpovědět na problém, který 4chan uživatel představoval.
O podpoře vědecké žurnalistiky
Pokud se vám tento článek líbí, zvažte podporu naší oceněné žurnalistiky předplatné. Zakoupením předplatného pomáháte zajistit budoucnost působivých příběhů o objevech a myšlenkách, které dnes formují náš svět.
V této diskusi však jeden z anonymních uživatelů v této diskusi odhadl minimální množství všech epizod, který je třeba sledovat s přístupem, který byl dříve matematikům neznámý. „Budu to muset (rozpracovat) ve více příspěvcích.“ Prosím, podívejte se na to pro všechny mezery, které jsem mohl chybět, “napsal uživatel, který v několika krocích vysvětlil, jak dospěli k jejich odhadu. Ostatní uživatelé pak převzali argumenty a diskutovali o nich – ale mimo 4chan, nic z toho neproběhlo žádné vlny. Zdálo se, že si nikdo nevšiml.
Extrémní sledování
V matematice se dva objekty permutují, když jsou přeskupovány nebo rekombinovány. Například můžete permutovat AB na BA. Pokud série Anime sestávala pouze ze dvou částí, můžete buď sledovat první a poté druhou epizodu (1-2) nebo druhou a poté první (2-1).
Pokud chcete sledovat sérii ve více uspořádáních – možná zjistit, která sekvence epizod dává největší smysl – potřebujete superpermutaci. Toto je posloupnost všech možných permutací. Představte si maraton, který ukazuje, kde sledujete první epizodu, následovanou druhou, a poté sledujte druhou epizodu, následuje první (1-2-2-1). Abychom se vyhnuli sledování druhé epizody dvakrát v řadě, kratší superpermutace by byla 1-2-1; Museli byste jen sledovat tři epizody, abyste stále měli všechny možné objednávky.
Pokud se řada skládá ze tří epizod, je trochu složitější najít nejkratší superpermutaci. V tomto případě jsou 3! = 6 různých sekvencí: 1-2-3, 1-3-2, 2-3-1, 2-1-3, 3-1-2, 3-2-1. Naštěstí nemusíte sledovat 3 × 6 = 18 dílů, ale v tomto případě můžete najít chytrou zkratku: 1-2-3-1-2-1-3-2-1. Tato objednávka obsahuje všechny možné permutace čísel 1, 2 a 3, ale musíte jen sledovat devět epizod!
Matematici také vypočítali nejkratší superpermutace pro sérii sestávající z n = 4 a n = 5 epizod (33 a 153 epizod). Kromě toho jsou však ve tmě. Nejkratší superpermutace pro n > 5 není známo.
Výzva se ve skutečnosti týká jednoho z nejvíce nevyřešitelných problémů v algoritmice: Problém pro prodejce. V tomto problému chce člověk navštívit různá města a skončit zpět v jejich rodném městě. Úkolem je najít nejkratší trasu, která spojuje všechna města. Nejkratší superpermutace je variace tohoto problému, ve kterém jednotlivé permutace představují různá města. V tomto případě přiřadíte různé vzdálenosti mezi městy stanovením překrývání permutací. Například města 1-2-3 a 2-3-1 mají velké překrývání: poslední dvě číslice první permutace odpovídají prvním dvěma číslicím druhého, takže lze kombinovat za vzniku 1-2-3-1. Můžeme proto přiřadit krátkou vzdálenost mezi těmito dvěma městy. Na druhé straně se 1-2-3 a 2-1-3 nepřekrývají. (Chcete -li vidět obě sekvence, musíte se podívat na celých šest částí; není možná žádná zkratka.) Takže tato města mají mezi sebou velkou vzdálenost.
Chcete -li najít nejkratší trasu v rámci permutací, připojíte permutace, které se nejvíce překrývají. Existuje pouze jedna potíže: neexistuje žádný známý algoritmus, který by rychle řešil cestující prodejce. Pokud jednáme s několika městy – nebo v případě série anime několika epizod – to není hlavní nevýhoda. Ale jakmile n stávají se velkými, počítače selhávají při úkolu, protože doba výpočtu roste exponenciálně n.
Počítače jsou schopny vypočítat superpermutace pro n = 4 a n = 5, ale ne za nic jiného. A ačkoli je možné vypočítat propracované superpermutace pro větší počet, zjištění nejkratší superpermutace je obtížnější.
Odborníci se proto musí vyrovnat s odhady. Například existuje algoritmus, který pomáhá odhadnout délku nejkratší možné superpermutace pro n Objekty: 1! + 2! + 3! + … + n! Pomocí tohoto algoritmu, pokud n = 2, získáte superpermutaci délky 1 + 2 = 3. n = 3, to má za následek délku 1 + 2 + 6 = 9. pro n = 4, dostanete 33. a pro n = 5, dostanete 153, což odpovídá nejkratší superpermutaci v každém případě.
Pro větší n, Tento algoritmus se však již neplatí: počítače byly schopny najít kratší superpermutace, než by naznačovalo, že existuje. Ve skutečnosti vzorec 1! + 2! + 3! + … + n! masivně nadhodnocuje délku nejkratší superpermutace n. Ačkoli algoritmus nabízí pouze přibližnou odpověď, matematici ji používají jako výchozí místo, s cílem zúžit možnosti k nalezení přesnějších odpovědí.
Náhody a znovuobjevení
V roce 2013 Nathaniel Johnston, nyní profesor matematiky na Mount Allison University v New Brunswicku, přistál na a Melancholie Haruhi Suzumiya Fandom Page. Sám Johnston nebyl anime fanouškem. Na web dorazil poté, co Googling několik vyhledávacích výrazů souvisejících s superpermutacemi. Tam narazil na diskusi, která se konala 4chan téměř před dvěma lety, kterou uživatel zkopíroval na fandom web.
Johnston se neobtěžoval dělat matematiku ale na svém blogu citoval příspěvek Fandom. Také tento komentář byl několik let bez povšimnutí.
Poté v říjnu 2018 matematik Robin Houston narazil na blogový příspěvek svého kolegy prostřednictvím zvědavé náhody. Houston se právě dozvěděl, že australský autor sci -fi Greg Egan našel nový maximum Délka pro nejkratší superpermutace, vyjádřená jako:
n! +(n –1)! + (n – 2)! + (n – 3)! + n – 3
To samo o sobě bylo bizarní. Když se však Houston začal o tomto výsledku dozvědět více, uvědomil si, že minimální délku superpermutace byla dána novou hodnotou anonymního uživatele anime fandom (v té době nevěděl o původu 4chan). Vzorec pro minimální délku je:
n! +(n – 1)! + (n – 2)! + n – 3
Houston sdílel Jeho objev na Twitteru (nyní x) 23. října téhož roku. „Zvědavá situace.“ Nejznámější spodní hranice pro minimální délku superpermutací byl prokázán anonymním uživatelem wiki věnované hlavně anime, “napsal.
Spolu se svými kolegy, matematiky Jay Pantone a Vince Vatter se Houston rozhodl zkontrolovat důkaz 4chanu a zapisovat jej matematickým způsobem. Vědci zveřejnili matematickou práci na online encyklopedii celočíselných sekvencí ve stejný měsíc a první autor je uveden jako „Anonymous 4chan plakát“.
Co nám tedy říkají tyto vzorce? Pokud chcete sledovat všechny epizody n-Part Series Ve všech možných kombinacích, musíte sedět alespoň n! +(n – 1)! + (n – 2)! + n – 3 epizody – to je příspěvek uživatele 4chanů – a nanejvýš n! +(n – 1)! + (n – 2)! + (n – 3)! + n – 3, které víme prostřednictvím Eganovy práce.
V případě série osmi epizod Kaleidoskop, Museli byste sledovat alespoň 46 085 a nanejvýš 46 205 epizod. Pro Melancholie Haruhi Suzumiya, nebo Haruhi, Se 14 epizodami se počet drasticky zvyšuje: minimálně 93 884 313 611 epizod a maximálně 93 924 230 411. Připomeňme, že se nejedná o úplné řešení – jen to nastavuje rozsah pro velikost superpermutace, která vám umožní efektivně sledovat sérii v každém možném pořadí.
Naštěstí Egan také poskytl algoritmus pro konstrukci odpovídající superpermutace. To umožňuje Haruhi Fanoušci vypracovat nejlepší pořadí epizod. Ale s průměrnou délkou epizody asi 24 minut, trvalo by to asi 4 miliony let, než se posadí touto superpermutací.
