Direkt zum Inhalt

Freistetters Formelwelt: Vier Millionen Jahre vor dem Fernseher

Durch Anime zur Mathematik: Wer beim Binge-Watching nicht allzu viel Zeit verschwenden möchte, sollte sich mit der Theorie der Superpermutationen beschäftigen.
Eine Fernbedienung, im Hintergrund ein Fernseher mit verschiedenen Filmen zur Auswahl
Eine Anime-Serie hat zu einer mathematischen Entdeckung geführt.

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?

Die legendärsten mathematischen Kniffe, die übelsten Stolpersteine der Physikgeschichte und allerhand Formeln, denen kaum einer ansieht, welche Bedeutung in ihnen schlummert: Das sind die Bewohner von Freistetters Formelwelt.
Alle Folgen seiner wöchentlichen Kolumne, die immer sonntags erscheint, finden Sie hier.

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.

WEITERLESEN MIT »SPEKTRUM +«

Im Abo erhalten Sie exklusiven Zugang zu allen Premiumartikeln von »spektrum.de« sowie »Spektrum - Die Woche« als PDF- und App-Ausgabe. Testen Sie 30 Tage uneingeschränkten Zugang zu »Spektrum+« gratis:

Jetzt testen

(Sie müssen Javascript erlauben, um nach der Anmeldung auf diesen Artikel zugreifen zu können)

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.