Angenommen, man möchte eine Fernsehserie ansehen, die aus einer bestimmten Anzahl von Episoden besteht. Jede Episode befindet sich auf einer eigenen DVD, die alle unmarkiert sind. Wir wissen daher nicht, in welcher Reihenfolge die Episoden angesehen werden sollen. Wie lange dauert es, herauszufinden, was die richtige Ordnung der Folgen ist?

Diese Aufgabenstellung (die vom Mathematiker Nathaniel Johnston stammt) ist typisch für die Mathematik. Es klingt wie ein alltägliches Problem, aber in Wahrheit würde niemals jemand auf die Idee kommen, sich so zu verhalten. In diesem Fall beruht die Frage aber ausnahmsweise auf einem realen Problem.

2011 wurde auf dem Internetforum »4chan« über die Anime-Fernsehserie »Die Melancholie der Suzumiya Haruhi« diskutiert. Die erste Staffel wurde im Fernsehen nicht in einer chronologischen Reihenfolge gesendet und bei weiteren Ausstrahlungen und der Veröffentlichung auf DVD wurden die Folgen (in denen es passenderweise um Zeitreisen geht) jedes Mal anders sortiert. Die im Forum diskutierte Frage lautete: Wenn man sich alle möglichen Reihungen der Episoden ansehen will, wie viele Folgen muss man mindestens anschauen?

Auf den ersten Blick klingt die Aufgabe einfach. Die erste Staffel hat 14 Episoden und daraus lassen sich schnell die möglichen Permutationen (Vertauschungen) berechnen. Aber das Ergebnis entspricht nicht zwangsweise der optimalen Anzahl. Angenommen, es gibt nur zwei Folgen A und B. Dann gibt es nur zwei Möglichkeiten, sie anzuordnen, nämlich AB und BA – man muss also insgesamt vier Folgen ansehen, um alle möglichen Reihenfolgen abzudecken. Wenn man aber schlau ist, sieht man sich Folge B nicht doppelt an. Mit der Kombination ABA braucht man nur drei Episoden zu schauen, um alle Möglichkeiten abzudecken. Wenn die Zahl der Folgen größer ist, macht sich der Unterschied schnell bemerkbar. Drei Episoden kann man auf sechs Arten sortieren: ABC, ACB, BAC, BCA, CAB und CBA. Das macht insgesamt 18 Möglichkeiten, aber man kann sich leicht davon überzeugen, dass die Sequenz ABCABACBA alle sechs Möglichkeiten enthält: Statt 18 muss man also nur 9 Folgen ansehen.

Man nennt solche Reihenfolgen auch Superpermutationen. Aus mathematischer Sicht stellt sich die Frage nach der kürzesten möglichen Superpermutation für eine gegebene Zahl an Symbolen. Dieses Problem ist bisher ungelöst, aber ein anonymer Nutzer hat auf 4chan einen Beweis veröffentlicht, der zumindest eine untere Grenze für die Anzahl angibt. Sie lässt sich durch diese Formel berechnen:

Jede Superpermutation für eine Menge von n Objekten hat also mindestens die Länge, die durch diese Gleichung gegeben ist. Für den Fall von drei Folgen ergibt die Formel den korrekten Wert von neun für die Länge der entsprechenden Superpermutation.

Der Post des anonymen Users blieb lange unentdeckt. Doch irgendwann stolperte Nathaniel Johnston zufällig über die Rechnung, wodurch auch andere Fachleute darauf aufmerksam wurden. Der Beweis auf 4chan wurde geprüft und 2018 erschien eine Arbeit mit dem Titel »A lower bound on the length of the shortest superpattern«, verfasst von Robin Houston, Jay Pantone, und Vince Vatter. Als Erstautor wird aber auch dort der »Anonymous 4chan Poster« aufgeführt.

Man hat mittlerweile auch eine Formel für eine obere Grenze des Problems gefunden. Eine exakte Bestimmung für den allgemeinen Fall mit n Objekten steht aber noch aus. Ob die Gleichung des anonymen Posters beim ursprünglichen Problem der Anime-Serie hilfreich war, ist allerdings zweifelhaft. Die Länge der Superpermutation liegt irgendwo zwischen 93 884 313 611 und 93 924 230 411 – man müsste auf jeden Fall über 4 Millionen Jahre vor dem Fernseher verbringen.