Anonimowy 4chanowiec rozwiązał problem matematyczny, a my go wyjaśnimy na cyckach (poniekąd)

25 października 2018 roku na stronie OEIS.org - On-Line Encyclopedia of Integer Sequences (internetowej encyklopedii ciągów liczb całkowitych) pojawił się dowód matematyczny, którego współautorem został anonimowy użytkownik 4chana. Brzmi absurdalnie? To czytajcie dalej, bo zrobi się jeszcze ciekawiej. Ale najpierw o samym problemie matematycznym, którego kwestia dotyczy. Z góry przepraszam za uproszczenia i ewentualne nieścisłości.


Permutacja to nic innego jak przekształcenie jakiegoś uszeregowanego zbioru w inny zbiór o takich samych elementach, lecz przedstawiony w innej kolejności. Uznajemy, że elementy te się nie powtarzają (jest to osobny przypadek, opisany przez holenderskiego niderlandzkiego matematyka de Bruijina ponad 70 lat temu). Najlepszym przykładem permutacji z życia wziętym jest tasowanie kart. Dalej postaram się operować w terminologii znanej wszystkim Bojownikom, czyli w cyckach - w tym przypadku: kolejności poszczególnych cycków, które chcielibyście pomiętosić. Jeżeli mamy do dyspozycji dwie pary, możemy je pościskać na dwa różne sposoby:


Bojownikom mniej zainteresowanych piersiami tłumaczę w formie liczbowej – zbiór liczb 1 i 2 można przedstawić na dwa sposoby: jako {1,2} oraz {2,1}.
Superpermutacja natomiast to taki zbiór, który zawiera w sobie wszystkie permutacje danego zbioru, przy czym poszczególne permutacje mogą się na siebie nakładać. Już tłumaczę o co chodzi na podstawie dwuelementowego zbioru par cycków:


Innymi słowy, jeżeli nie potrafilibyście się zdecydować na to, w jakiej kolejności chcielibyście pomacać piersi, to chcielibyście to zrobić we wszystkich możliwych kolejnościach. Oczywiście moglibyśmy to zrobić najpierw na pierwszej parze, potem na drugiej, następnie znów na drugiej, a później na pierwszej (wykonując cztery ruchy), ale możemy zrobić to samo, wykonując możliwie najmniejszą ilość ruchów (niestety, jakaś granica musi istnieć). W takim przypadku mówimy o superpermutacji – tutaj jest ona zbiorem o trzech elementach. Należy przy tym zaznaczyć, że nie interesuje nas ile razy dany element występuje w superpermutacji, zatem z punktu widzenia problemu powyższy przykład niczym nie różni się od tego:


W wersji liczbowej: superpermutacją zbioru liczb 1 i 2 jest jednocześnie zbiór {1,2,1} jak i {2,1,2}.
Sytuacja robi się jeszcze ciekawsza, gdy nasz zbiór powiększy się o kolejny biust. Zbiór trzyelementowy tworzy sześć różnych permutacji (co bardziej zainteresowanych Bojowników zapraszam do sprawdzenia), ale ile elementów będzie zawierać nasza superpermutacja? Jak się okazuje – dziewięć:


Ponownie w wersji liczbowej: dla zbioru liczb 1, 2 i 3, który posiada permutacje {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2} i {3,2,1} superpermutacją jest zbiór {1,2,3,1,2,1,3,2,1}.
Sprawa komplikuje się, i to dosyć szybko, kiedy próbujemy do zbioru dodawać kolejne elementy. Przy zbiorze czteroelementowym nasza superpermutacja posiada już 33 elementy, a dla zbioru pięcioelementowego – aż 153. Pozornie te liczby wydają się być niepowiązane, ale matematycy zauważyli, że kieruje nimi pewien wzór:


Zakładam, że wiecie czym jest silnia, ale mimo wszystko przedstawię to na przykładzie:
Zbioru 4-elementowego: 4!(czyli 24) + 3!(6) + 2!(2) + 1!(1) = 33
Zbioru 5-elementowego: 5!(120) + 4!(24) + 3!(6) + 2!(2) + 1!(1) = 153

Idąc tym tokiem rozumowania, superpermutacja zbioru sześcioelementowego powinna zawierać 873 elementy. I taką właśnie hipotezę – że superpermutacje podążają według powyższego wzoru - uznawano za hipotezę naukową (czyli takie rozwiązanie problemu, które wydaje się być prawdziwe, ale nie zostało potwierdzone żadnymi dowodami). Hipotezy jednak mogą zostać obalone pojedynczym dowodem, który im zaprzecza. W tym przypadku taki dowód obalający pojawił się w 2014 roku, kiedy to matematyk Robin Houston pokazał, że dla sześcioelementowego zbioru superpermutacja może zawierać mniej niż 873 elementy – dokładniej 872. Niewykluczone, że może istnieć mniejsza liczba (powiedzmy, że 800). Warto również byłoby zastanowić się – jeśli faktycznie chcemy zadanie wykonać przy użyciu jak najmniejszej ilości ruchów – czy istnieje jakaś górna granica. Czyli ile razy najmniej, a ile najwięcej musielibyśmy miętosić cycki, aby zrobić to w każdej możliwej kolejności. Cały problem został bardzo dobrze opisany w filmie na kanale Numberphile – Bojowników posługujących się mową Shakespeare'a zachęcam do obejrzenia:

https://www.youtube.com/watch?v=wJGE4aEWc28
W tym momencie opuszczamy część matematyczno-cyckową i przechodzimy do mięsa, czyli jaki dowód przeprowadził anonim z 4chana.

Mamy 20 października 2018 roku, Greg Egan, pisarz SF i jednocześnie matematyk z zamiłowania, publikuje dowód na istnienie górnej granicy długości superpermutacji. Wciąż jednak brakowało dowodu potwierdzającego istnienie dolnej granicy. Sama publikacja sprowokowała wcześniej wspomnianego Robina Houstona – tego samego, który zaprzeczył istniejącej w matematycznym środowisku hipotezie – do poszukiwania informacji na ten temat. No i znalazł. Na stronie o tematyce związanej z anime:


Ciekawa sprawa. Najlepsza znana nam dolna granica minimalnej długości superpermutacji została dowiedziona przez anonimowego użytkownika wiki poświęconej głównie anime.

Robin dotarł również do źródła - wątku na 4chanie, w którym użytkownik zastanawiał się nad tym, na ile sposobów jest w stanie obejrzeć jeden serial. Bądźmy szczerzy - sytuacja jest dosyć niecodzienna, nieczęsto znajduje się dowód matematyczny na forum internetowym, na którym niejednokrotnie wylewa się bluzgi na innych użytkowników. Nic dziwnego zatem, że pomimo swojej wartości, niewielu matematyków byłoby skłonnych odnosić się do niego w swoich pracach. Dlatego właśnie Robin podzielił się swoim odkryciem z kolegami po fachu i razem ulepszyli oraz „przetłumaczyli” dowód na bardziej naukowy język. Kilka dni później opublikowano go na wspomnianej stronie OEIS-u.

The Melancholy of Haruhi Suzumiya (pol. Melancholia Haruhi Suzumiyi) jest mangą, która została zaadaptowana jako anime w 2006 roku. Co ciekawe, odcinki nie były ze sobą powiązane, a wersja na DVD, wypuszczona w 2007 roku, prezentowała zupełnie inną kolejność odcinków niż ta publikowana w telewizji. Brak chronologii spowodował, że w środowisku fanów tej animacji standardem stało się oglądanie jej w dowolnej kolejności. 13 września 2011 roku jedna osoba na 4chanie zapytała:


Ok /sci/ (podgrupa 4chana dyskutująca na tematy naukowe),
Macie do obejrzenia 14 odcinków serialu i chcecie obejrzeć je w każdej możliwej kolejności. E(n) jest najmniejszą liczbą odcinków, które musicie obejrzeć, aby zrealizować cel. Dla przykładu, jeśli n=3, E=9, ponieważ możecie obejrzeć je w kolejności 1,2,3,1,2,1,3,2,1 aby zobaczyć wszystkie 6 permutacji.

Z perspektywy powyższego wyjaśnienia superpermutacji brzmi znajomo, prawda? Problem został okraszony grafiką, która została później umieszczona na wspomnianej przez Houstona wiki, i dzięki której otrzymał on swoją nazwę: „Problem Haruhi”. Cztery dni później, 17 września 2011 roku (siedem lat przed jego odkryciem przez środowisko naukowe!) anonimowy internauta udostępnił rozwiązanie tego problemu. Problemu, nad którym głowiono się od 15 lat i który przez kolejne 7 lat uznawany był za nierozwiązany, mimo że to rozwiązanie tkwiło w czeluściach internetu i nikt nie zdawał sobie z tego sprawy. Do dzisiaj, notabene, nie odnaleziono owego anonimowego 4chanowca, który opublikował dowód. Być może nie zdawał on sobie sprawy z tego, jak istotny to był problem, a być może o tym wiedział, ale miał to gdzieś. Nie wiemy tego i nie dowiemy się, dopóki się on nie odnajdzie. Od opublikowania dowodu minęło prawie 1,5 roku i póki co nikt nie przyznał się do tego matematycznego odkrycia, sygnowanego tą oto grafiką:



Podsumowując, dokonano matematycznego przełomu dzięki weebowi (mówiąc po polsku - mangozjebowi), który chciał obejrzeć anime w każdej możliwej kolejności odcinków.

Świat nigdy nie przestanie mnie zaskakiwać.