Zahlen, bitte! Superpermutationen von und für Anime-Fans

4chan ist eher selten eine Quelle mathematischer Erkenntnisse. Doch in einem anonymen Forum wurde jüngst ein kleines Juwel ausgegraben und poliert.

In Pocket speichern vorlesen Druckansicht 100 Kommentare lesen
872
Lesezeit: 6 Min.
Von
  • Dr. Harald Bögeholz
Inhaltsverzeichnis
Zahlen, bitte!

In dieser Rubrik stellen wir immer dienstags verblüffende, beeindruckende, informative und witzige Zahlen aus den Bereichen IT, Wissenschaft, Kunst, Wirtschaft, Politik und natürlich der Mathematik vor.

Als die japanische Zeichentrickserie Die Melancholie der Haruhi Suzumiya 2006 erstmals ausgestrahlt wurde, geschah dies nicht in chronologischer Reihenfolge. Vielmehr sah man zuerst Folge 11, dann 1, 2, 7, 3, 9, 8, 10, 14, 4, 13, 12, 5 und schließlich 6 – vielleicht um zu unterstreichen, dass in der Handlung Zeitreisen vorkommen.

(Bild: 4chan)

Jahre später – inzwischen war die Serie in anderer Reihenfolge auf DVD erschienen und anlässlich einer zweiten Staffel in wieder anderer Reihenfolge wiederholt worden – fragte jemand auf 4chan, einem anonymen Diskussionsforum: Wie viele Folgen muss man mindestens anschauen, um die 14 Folgen der ersten Staffel in allen möglichen Reihenfolgen hintereinander gesehen zu haben?

Eine harmlos klingende Frage, doch es stellt sich heraus, dass die Mathematik darauf bis heute keine exakte Antwort kennt. Aber im Laufe der Diskussion, die im September 2011 begann, postete ein anonymer User eine untere Schranke für die minimale Länge, die bis dorthin nicht bekannt war.

Doch der Reihe nach: Gesucht ist die minimale Länge einer sogenannten Superpermutation. Das ist ein String aus n verschiedenen Symbolen, in dem jede mögliche Permutation der n Symbole irgendwo als (zusammenhängender) Teilstring vorkommt. Eine Permutation ist eine Anordnung der Symbole ohne Wiederholung, und es gibt n! (n Fakultät = 1·2·3· ··· ·n) davon: n Möglichkeiten für das erste Symbol, n–1 für das zweite und so weiter.

Beispiel n = 3: Es gibt 3! = 6 mögliche Permutationen: 123, 132, 213, 231, 312, 321. Das sind insgesamt 18 Zeichen, aber durch geschickte Anordnung und "Zusammenschieben" kann man eine Superpermutation aus nur 9 Zeichen bauen:

123
231
312
213
132
321
123121321

Kürzer geht es nicht, was sich für n=3 noch per Computer mit einer Brute-Force-Suche nachprüfen lässt. Es gibt nun einen rekursiven Algorithmus, mit dem man aus einer Superpermutation aus n Symbolen eine mit n+1 Symbolen bauen kann, ein Kochrezept.

Man nehme dafür eine Superpermutation (Beispiel oben, n=3) und mache zunächst das Zusammenschieben rückgängig, schreibe also die n! Permutationen auf. Nun verdoppelt man jede davon und fügt in der Mitte das neue, (n+1)-te Symbol ein:

1234123|2314231|3124312|2134213|1324132|3214321

Das ergibt eine Superpermutation von n+1 Symbolen, wie man sich leicht überlegen kann (wer hasst sie nicht, diese Formulierung?). An allen oben der Klarheit halber mit | markierten Stellen lassen sich nun durch erneutes Zusammenschieben exakt so viele Zeichen einsparen, wie durch das Auseinanderziehen hinzugefügt wurden:

123412314231243121342132412314321

Das sind 33 Zeichen für eine Superpermutation von n=4 Symbolen. Um wie viele Zeichen macht der Schritt von n auf n+1 die Superpermutation länger? Wie gesagt ist das Auseinanderziehen und erneute Zusammenschieben längenneutral. Durch das Verdoppeln der n! Permutationen kommen n!·n Zeichen hinzu sowie n!-mal das neue, n+1-te Symbol. Das ergibt in Summe n!·(n+1) = (n+1)! zusätzliche Zeichen.

Startet man das Verfahren also mit der trivialen Superpermutation "1", dann ergibt sich die Länge der Superpermutation mit n Symbolen zu L(n) = 1! + 2! + 3! + ··· + n!. Lange wurde vermutet, dass diese Konstruktion optimal ist. Prima, Problem gelöst, man muss 93.928.268.313 Haruhi-Folgen schauen.

Doch halt: Die Formel stimmt leider nur bis n=5. Hier beträgt die Länge 153 Zeichen und Ben Chaffin hat mit einer vollständigen Computersuche nachgewiesen, dass es nicht kürzer geht. Er fand neben der nach obigem Verfahren konstruierten Superpermutation sieben weitere, es gibt also insgesamt acht verschiedene (Näheres im Blog von Nathaniel Johnston).

Für n=6 sagt die Formel die Länge 873 voraus. Doch im August 2014 veröffentlichte Robin Houston eine Superpermutation von 6 Symbolen mit nur 872 Zeichen (Paper auf arXiv: Tackling the Minimal Superpermutation Problem). Er hatte die Aufgabe in ein bekanntes Optimierungsproblem übersetzt, das Problem des Handlungsreisenden (Englisch Travelling Salesman Problem), und eine darauf spezialisierte Software zur Lösung verwendet.

Damit ist die Vermutung nicht nur für n=6 widerlegt, sondern auch für alle größeren n, denn aus Houstons Superpermutation kann man ja durch den obigen Algorithmus längere konstruieren, die allesamt um ein Zeichen kürzer sind als L(n).

Es geht für größere n aber noch kürzer. Bereits 2013 veröffentlichte Aaron Williams ein Paper über die Hamiltonizität eines Cayley-Graphen der symmetrischen Gruppe. Da brauchte es nur noch einen mathematisch begabten Science-Fiction-Autor, um in diesem Jargon den Zusammenhang mit Superpermutationen zu erkennen und allgemeinverständlich aufzubereiten: Greg Egan. Er adaptierte Williams' Methode und beschrieb eine Konstruktion für Superpermutationen der Länge L2(n) = n! + (n–1)! + (n–2)! + (n–3)! + n – 3. Das ist für n≥7 kürzer als L(n):

n L0(n) L2(n) L(n)
1 1
2 3 3
3 9 10 9
4 33 34 33
5 152 154 153
6 867 873 873
7 5.884 5.908 5.913
8 46.085 46.205 46.233
9 408.246 408.966 409.113
10 4.032.007 4.037.047 4.037.913
11 43.908.488 43.948.808 43.954.713
12 522.547.209 522.910.089 522.956.313
13 6.745.939.210 6.749.568.010 6.749.977.113
14 93.884.313.611 93.924.230.411 93.928.268.313

Wie man sieht, sparen sich Hardcore-Haruhi-Fans mit dieser Konstruktion immerhin 4 Millionen Folgen. Aber es ist mitnichten klar, ob dies das Minimum ist. Und hier kommt nun wieder das 4chan-Forum ins Spiel. Dort postete ein anonymer Mathematiker (gibts dafür eigentlich Selbsthilfegruppen?) einen Beweis, dass die Länge einer Superpermutation von n Symbolen mindestens L0(n) = n! + (n–1)! + (n–2)! + n – 3 beträgt.

Robin Houston, Jay Pantone und Vince Vatter haben den Beweis schön mit LaTeX aufgeschrieben (A lower bound on the length of the shortest superpattern); vielleicht das erste Paper, das als Hauptautor "Anonymous 4chan Poster" hat. Zusammenfassend kann man über die Haruhi-Frage also sagen: Die Antwort ist definitiv größer als 42. Sie liegt zwischen 93.884.313.611 und 93.924.230.411. (bo)