Kako Anonymous 4chan Post je pomagal rešiti 25-letno matematično puzzle


16. septembra, 2011, anime fan je objavil matematično vprašanje na spletni oglasni deski 4chan o kultni klasični televizijski seriji Melanholija Haruhi Suzumiya. Prva sezona predstave, ki vključuje časovni potek, je bila prvotno izšla v nehronološkem vrstnem redu, poleg tega pa sta ponovno izdali in DVD različico nadalje preuredili epizode. Navdušenci so se na spletu pogovarjali o najboljšem naročilu za gledanje epizod in se je 4chan plakat spraševal: Če gledalci želijo videti serijo v vseh možnih zaporedjih, kateri najkrajši seznam epizod bi morali gledati?

Revija Quanta


fotografija avtorja

O podjetju

Prvotna zgodba, ki jo je prejel z dovoljenjem revije Quanta, uredniško neodvisna publikacija fundacije Simons, katere poslanstvo je izboljšati razumevanje znanosti s področja javnega obveščanja tako, da pokriva raziskovalne dosežke in trende v matematiki ter fizikalnih in življenjskih znanostih.

V manj kot eni uri je anonimna oseba ponudila odgovor – ni popolna rešitev, temveč nižja omejitev števila potrebnih epizod. Argument, ki je obsegal serijo s katerim koli številom epizod, je pokazal, da bi morali gledalci za prvo sezono Haruhi z 14 epizodi gledati vsaj 93.884.313.611 epizod, da bi videli vse možne naročila. "Prosim poglej [the proof] za vse luknje, ki sem jih morda zamudil, "je napisal anonimni plakat.

Dokaz je padel pod radar matematične skupnosti za sedem let – očitno je samo en poklicni matematik opazil takrat, in ni skrbno preveril. Toda v preteklem mesecu se je avstralski romanopisec Greg Egan izkazal za novega zgornjega dela števila potrebnih epizod. Eganovo odkritje je ponovno poudarilo zanimanje za to težavo in opozorilo na spodnjo mejo, objavljeno anonimno v letu 2011. Obe dokazi so zdaj pozdravljeni, saj pomemben napredek pri uganki matematiki so študira vsaj 25 let.

Matematiki so hitro preverili Eganovo zgornjo zvezo, ki se, tako kot spodnja, nanaša tudi na serijo poljubne dolžine. Potem je Robin Houston, matematik v podjetju za vizualizacijo podatkov Kiln, in Jay Pantone iz Univerze Marquette v Milwaukeeju neodvisno preverili delo anonimnega plakata 4chan. "Potrebno je bilo veliko dela, da bi ugotovili, ali je bilo to pravilno ali ne," je dejal Pantone, ker ključne ideje niso bile posebej izražene.

Zdaj sta Houston in Pantone, ki sta se ji pridružila Vince Vatter na Univerzi na Floridi v Gainesvilleu, zapisali formalni argument. V svojem članku so prvega avtorja navedli kot "Anonymous 4chan Poster."

Permutation Cities

Če ima televizijska serija le tri epizode, jih je mogoče šestkrat ogledati: 123, 132, 213, 231, 312 in 321. Ti šest zaporedij lahko sestavite skupaj, da bi dobili seznam 18 epizod, ki vključuje vsako naročanje , vendar je na voljo veliko bolj učinkovit način: 123121321. Zaporedje, kot je ta, ki vsebuje vse možne prerazporeditve (ali permutacije) zbirke n simbolov, se imenuje "superpermutacija".

Leta 1993 sta Daniel Ashlock in Jenett Tillotson opazila, da če pogledate najkrajše superpermutacije za različne vrednosti n, se zdi, da se vzorec hitro pojavlja, v katerem so vključeni faktoriali – tiste številke, napisane v obliki n !, ki vključujejo množenje skupaj vseh številk do n (npr. 4! = 4 × 3 × 2 × 1).

Če ima vaša serija samo eno epizodo, najkrajša superpermutacija ima dolžino 1! (znan tudi kot navaden stari 1). Za serijo dveh epizod je najkrajša superpermutacija (121) dolžina 2! + 1 !. Za tri epizode (primer, ki smo si ga ogledali zgoraj), dolžina znaša 3! + 2! + 1 !, in za štiri epizode (123412314231243121342132413214321), je 4! + 3! + 2! + 1 !. Faktorialno pravilo za superpermutacije je postalo običajna modrost (čeprav nihče ni mogel dokazati, da je to veljalo za vsako vrednost n), matematiki pa jo je kasneje potrdil za n = 5.

Leta 2014 je Houston začel matematike, saj je pokazal, da se za n = 6 vzorec razbije. Pravilo factorial napoveduje, da bi za gledanje šestih epizod v vsakem možnem zaporedju moralo zahtevati 873 epizod, vendar je Houston našel način, kako to storiti v 872. In ker obstaja preprost način za pretvorbo kratke superpermutacije na n simbolih v kratko superpromutacijo na n + 1 simboli, Houstonov primer je pomenil, da faktorialsko pravilo ne uspe za vsako vrednost n nad 6.

Houstonova gradbena dela s prevajanjem problema superpermutacije v znamenitega potujočega prodajnega problema, ki išče najkrajšo pot skozi zbirko mest. Natančneje, superpermutacije so povezane s "asimetričnim" potujočim prodajnim problemom, pri katerem ima vsaka pot med dvema mestoma strošek (ki ni nujno enak v obeh smereh), cilj pa je najti najcenejšo pot skozi vse mesta.

Prevajanje je preprosto: pomislite na vsako permutacijo kot "mesto" in si predstavljate pot od vsake permutacije do permutacije. Pri problemu superpermutacije želimo najkrajšo možno zaporedje številk, ki navaja vse permutacije, zato je cilj potovati skozi permutacije na način, ki čim bolj dodaja čim manj začetnih permutacij. Zato izjavljamo, da so stroški vsake poti preprosto število števk, ki jih moramo pripeti do konca prve permutacije, da dobimo drugo. V primeru n = 3 na primer pot od 231 do 312 stane 1 $, saj moramo samo dodati 2 do konca 231, da dobimo 312, medtem ko pot od 231 do 132 stane 2 $, saj moramo dodajte 32. S to nastavitvijo najcenejša pot po mestih neposredno ustreza najkrajšemu superpermutaciji.

Lucy Reading-Ikkanda / Quanta Magazine

Ta prevod je pomenil, da bi Houston lahko spremenil moč prodajnih algoritmov na problem superpermutacije. Problem prodajalca je znana kot NP-težka težava, kar pomeni, da ni učinkovitega algoritma, ki bi lahko rešil vse primere tega. Ampak obstajajo algoritmi, ki lahko rešujejo nekatere primere učinkovito, in druge algoritme, ki proizvajajo dobre približne rešitve. Houston je uporabil enega od slednjih, da je proizvedel svojo 872-mestno superprepniranje.

Ker je izdelal le približno rešitev, morda ni najboljša superpermutacija. Matematiki zdaj vodijo velikansko računalniško iskanje najkrajše superpermutacije na šestih simbolih, je dejal Pantone. "Vemo, da bo naša preiskava končana v končni čas, vendar ne vem, ali je to en teden ali milijon let," je dejal. "Ni nobenega naprednega vrstice."

Napačen red

Do dela Houstonove anonimne 4chan post je skoraj tri leta sedel v svojem kotičku interneta. Eden matematik Nathaniel Johnston z Univerze Mount Allison je nekaj dni po tem, ko je bil objavljen, opazil kopijo delovnega mesta na drugem spletnem mestu – ne zato, ker je bil ljubitelj anime, temveč zato, ker je vnesel vrsto iskalnih izrazov, v Google.

Johnston je prebral argument in mislil, da se zdi verjeten, vendar se ni trudil skrbno preverjati. Matematiki so takrat verjeli, da je faktorska formula za superpermutacije verjetno pravilna, in ko menite, da natančno poznate odgovor na vprašanje, ni nižja vezava ni zelo zanimiva. Z drugimi besedami, epizode raziskav superpermutacije niso bile izvedene.

Johnston je pozneje omenil spodnjo vezavo na nekaj spletnih mestih, vendar pa "mislim, da nihče v resnici ne posveča nobenih posebnih pozornosti," je dejal Houston.

Nato je 26. septembra letos matematik John Baez z Kalifornijske univerze, Riverside, Objavljeno na Cvrkutati o Houstonovi ugotovitvi iz leta 2014, kot del serije tweets o očitnih matematičnih vzorcih, ki ne uspejo. Njegov tweet je ujel oči Egana, ki je pred desetletji predaval matematiko, preden je začel nagrajeno kariero kot novinarko znanstvene fantastike (njegov prodorni roman iz leta 1994, v srečni naključju, je bil imenovan Mesto permutacije). "Nikoli se nisem več zanimal [mathematics], "Egan napisal po elektronski pošti.

Egan se je spraševal, ali je bilo mogoče graditi superpermutacije celo krajše od Houstonove. Literaturo je prebral za dokumente o tem, kako zgraditi kratke poti skozi permutacijske mreže in po nekaj tednih je našel natančno, kaj mu je bilo potrebno. V enem dnevu ali dveh je prišel do nove zgornje meje na dolžino najkrajše superpermutacije za n simbolov: n! + (n-1)! + (n-2)! + (n – 3)! + n – 3. Podobno je s staro faktorsko formulo, vendar z mnogimi izrazi odstranjen.

"To je popolnoma razbil [previous] zgornji meji, "je dejal Houston.

Anonimni 4chan plakatni spodnji rob je bil medtem tantalizacijsko blizu novemu zgornji meji: deluje na n! + (n-1)! + (n-2)! + n – 3. Ko je Eganov rezultat postal javen, je Johnston druge matematike opozoril na dokaz anonimnega plakata, Houston in Pantone pa sta kmalu pokazala, da sta bila pravilna. Tako kot pri Houstonovem delu, nove spodnje in zgornje meje pridejo na superpermutacije s problemom trgovskega potnika: spodnja meja kaže, da mora pot skozi vsa mesta potovati po najmanjšem številu poti, ki stanejo več kot $ 1, medtem ko zgornja meja konstruira določeno pot za vsako n, ki uporablja samo 1 $ in 2 $ povezave.

Za Haruhi navijači, Eganova konstrukcija daje izrecna navodila, kako gledati vse možne naročil sezone 1 v samo 93.924.230.411 epizod. Gledalci bi lahko takoj začeli gledati gledanje, ali pa bi lahko počakali in videli, ali lahko matematiki izbrišejo to številko navzdol. Nizka vez anonimnega plakata dokazuje, da ta moteča navzdol ne bi mogla prihraniti več kot 40 milijonov epizod, toda to je dovolj za lep začetek sezone dve.

Prvotna zgodba, ki jo je prejel z dovoljenjem revije Quanta, uredniško neodvisna publikacija fundacije Simons, katere poslanstvo je izboljšati razumevanje znanosti s področja javnega obveščanja tako, da pokriva raziskovalne dosežke in trende v matematiki ter fizikalnih in življenjskih znanostih.


Več velikih WIRED zgodbe