Als Kind kam ich nur selten mit Pfannkuchen in Berührung – dafür aber umso mehr mit der französischen Variante, der Crêpe. Weil es das Lieblingsessen meines Bruders war, bereitete meine Mutter sie fast jede Woche zu. Damals ahnte natürlich keiner von uns, dass die Mehlspeise mit Mathematik zusammenhängt. Doch das Pfannkuchenproblem beschäftigt die Fachleute seit den 1970er Jahren – bis heute.

Und tatsächlich hatte ich – ohne es zu wissen – in der Vergangenheit mit dem Pfannkuchenproblem zu tun. Für ein Fest an der Universität hatte ich mich bereit erklärt, einen Nachtisch mitzubringen, und dafür etliche Crêpes gebacken. Ich machte eine nach der anderen in der Pfanne fertig und stapelte sie dann auf einem Teller. Da ich nicht sehr geübt darin war und auch keine geeignete Pfanne hatte, variierte die Größe der Crêpes: Mal stach ein besonders großes Exemplar in der Mitte des Stapels heraus, während sich darüber eine kleinere Version versteckte. Schön war das nicht.

Das denken sich auch Mathematiker, die es bekanntlich lieben, Objekte zu sortieren. Und so veröffentlichte Jacob Eli Goodman 1975 in einer Ausgabe des »American Mathematical Monthly« folgende Aufgabe: »Der Koch in unserem Restaurant ist schlampig: Wenn er einen Stapel Pfannkuchen zubereitet, sind sie unterschiedlich groß. Wenn ich sie einem Kunden bringe, ordne ich sie auf dem Weg zum Tisch neu an (so dass der kleinste Pfannkuchen oben landet und so weiter, bis zum größten unten), indem ich mehrere von oben nehme, sie umdrehe und das so oft wie nötig wiederhole. Wenn es n Pfannkuchen gibt, wie oft muss ich sie maximal umdrehen, um sie wie gewünscht anzuordnen?«

Unordnung vermeiden

Goodman stieß auf dieses Problem, als er einen Stapel Handtücher in einen Schrank einräumte. Allerdings sah das Ergebnis so unordentlich aus, dass er sie der Größe nach sortieren wollte – aber keine Ablagefläche fand, um die Handtücher abzulegen und einen zweiten Stapel zu bilden. So war er gezwungen, die obersten paar Handtücher umzudrehen, die Situation neu zu bewerten, dann ein paar weitere umzudrehen und so weiter. Dabei wollte er natürlich gerne möglichst effizient vorgehen und so wenige Umdrehungen wie nötig vornehmen. Das schien ihm ein interessantes mathematisches Problem zu sein; eine Analogie mit Pfannkuchen klang für ihn jedoch ansprechender als seine Situation mit den Handtüchern. Goodman stand damals noch am Anfang seiner Karriere als Mathematiker und wollte nicht den Eindruck erwecken, sich nur für Probleme der Unterhaltungsmathematik zu interessieren. Deshalb veröffentlichte er seine Frage unter dem Pseudonym Harry Dweighter (was sich wie »harried waiter« liest, also gestresster Kellner).

Es gibt eine einfache Strategie, die immer zielführend ist: Falls sich der größte Pfannkuchen noch nicht ganz unten befindet, setzt man den Pfannenwender unterhalb des größten Pfannkuchens an und wendet den Stapel, damit der größte Pfannkuchen nach oben wandert. Dann dreht man den gesamten Stapel um und hat somit den größten Pfannkuchen an die richtige Stelle gesetzt: nach ganz unten. Danach sucht man den zweitgrößten Pfannkuchen heraus und wiederholt das Ganze: Man bringt ihn durch eine Drehung nach oben und wendet dann den gesamten Stapel bis auf den untersten Pfannkuchen, damit auch der zweitgrößte an der vorgesehenen Stelle landet. Auf diese Weise braucht man für einen Stapel mit n Pfannkuchen höchstens 2n − 3 Wendemanöver: Jeden Pfannkuchen muss man erst ganz nach oben und dann an den gewünschten Platz verfrachten (man braucht also je zwei Wendemanöver), außer den kleinsten und zweitkleinsten. Hat man alle Pfannkuchen auf diese Weise außer den zwei kleinsten sortiert, muss man im schlimmsten Fall nur noch einmal die Reihenfolge dieser beiden umkehren – so kommt man schließlich auf 2n − 3.

Bill Gates’ einzige akademische Veröffentlichung

Doch wie sich herausstellt, ist 2n − 3 nicht das Optimum. Man kann zwar auf diese Weise immer einen Stapel sortieren, allerdings geht es auch besser. In der Tat konnten Fachleute zeigen, dass sich jeder Stapel mit vier Pfannkuchen in maximal vier Zügen sortieren lässt – und nicht in 2 · 4 − 3 = 5. Für fünf Pfannkuchen braucht man nur 5 Züge statt 2 · 5 − 3 = 7 und so weiter.

Für so wenige Pfannkuchen lassen sich die einzelnen Situationen noch durchspielen: Zunächst kann man alle möglichen Anordnungen der n Pfannkuchen untersuchen; im Fall von n = 4 sind das 4! = 24 verschiedene Anordnungen. Für jede davon sucht man die effizienteste Methode, um sie der Größe nach zu sortieren. So stellt man fest, dass niemals mehr als vier Drehungen nötig sind. Mit fünf Pfannkuchen muss man allerdings 120 Anordnungen durchgehen, was deutlich aufwändiger ist. Sobald man sich noch mehr Pfannkuchen widmet, beispielsweise einem Stapel mit 20, wird eine direkte Bestimmung unmöglich: In diesem Fall gibt es 2,43 · 10¹⁸ verschiedene Anordnungen, also mehr als zwei Milliarden Milliarden!

Also suchten Fachleute nach besseren Abschätzungen als 2n − 3. Und bereits 1979, vier Jahre nach Goodmans Veröffentlichung, wurden Bill Gates und Christos Papadimitriou fündig. Ja, es geht wirklich um Microsoft-Gründer Bill Gates und nicht um einen Namensvetter. Bevor Gates eines der erfolgreichsten Softwareunternehmen der Welt gründete, hatte er sich während seines Studiums dem Pfannkuchenproblem gewidmet – und dazu seine einzige akademische Arbeit veröffentlicht. Darin gelang es ihm, die Mindestzahl an nötigen Wendemanövern einzugrenzen, um einen Pfannkuchenstapel zu sortieren: Man müsse mindestens ¹⁷ⁿ⁄₁₆ und höchstens ^(5 + 5n)⁄₃ Umdrehungen vornehmen.

Diese Lösung blieb 30 Jahre lang ungeschlagen. Inzwischen wurden schon einige Pfannkuchenzahlen exakt berechnet, allerdings nur bis n = 19. Die Pfannkuchenzahl für 20 Pfannkuchen ist noch immer unbekannt, man kann sie aber mit Gates’ Abschätzung immerhin eingrenzen: Die Mindestzahl an nötigen Umdrehungen liegt demnach zwischen 22 und 35. In den 2000er Jahren wurden neue Abschätzungen gefunden, die Gates’ Ergebnis jedoch nur minimal verbessern. Die Fachleute konnten zeigen, dass die optimale Anzahl an Wendungen, die man maximal für n Pfannkuchen braucht, zwischen ¹⁵ⁿ⁄₁₄ und ¹⁸ⁿ⁄₁₁ liegt. Im Fall von n = 20 entspricht das einer Zahl zwischen 22 und 32.

Der Versuch, exakte Lösungen des Pfannkuchenproblems für eine große Anzahl an Pfannkuchen zu finden, hat sich 2011 als aussichtslos erwiesen: Damals fanden drei Forschende heraus, dass die Aufgabe »NP-schwer« ist. Damit gehört sie zu den Problemen der Mathematik, deren Bearbeitungsdauer exponentiell mit der Größe n (in diesem Fall mit der Anzahl der Pfannkuchen) wächst. Wenn mehr Pfannkuchen dazukommen, explodiert irgendwann der benötigte Aufwand. Klassische Computer können solche Probleme ab einem bestimmten Punkt nicht mehr bewältigen – und es gibt wenig Hoffnung, dass es jemals einen Algorithmus geben wird, der diese Schwierigkeit überwindet.

Das Problem mit verbrannten Pfannkuchen

Doch anstatt sich davon abschrecken zu lassen, legte David X. Cohen, einer der Autoren der beliebten Comicserie »Die Simpsons«, zusammen mit dem Informatiker Manuel Blum 1995 sogar noch eine Schippe drauf: Sie gelten als Erfinder des »Problems der verbrannten Pfannkuchen«. In diesem Fall hat der schludrige Koch alle Pfannkuchen auf einer Seite verbrannt. Der Kellner versucht daher wieder, den chaotischen Stapel der Größe nach zu ordnen – und dabei alle verbrannten Seiten nach unten zeigen zu lassen. Schließlich soll der Gast nicht sehen, dass der Koch die Zeit aus den Augen verloren hat.

Und wirklich beschreibt dieses Problem meine eigene Situation, als ich Crêpes für meine Kommilitonen backte, etwas besser (ich bin keine besonders gute Köchin). Wie Sie sich wahrscheinlich vorstellen können, sind in diesem Fall mehr Wendemanöver nötig als beim klassischen Pfannkuchenproblem.

In ihrer Arbeit aus dem Jahr 1995 haben Cohen und Blum aber nicht nur das Problem vorgestellt, sondern auch eine Abschätzung angegeben: Demnach braucht man zwischen ³ⁿ⁄₂ und 2n − 2 Drehungen, um n > 9 verbrannte Pfannkuchen zu sortieren. Für n = 20 Pfannkuchen sind das zwischen 30 und 58 Wendemanöver. Auch diese Abschätzung konnte inzwischen leicht verbessert werden. Die bekannten verbrannten Pfannkuchenzahlen sind in dieser Tabelle zu finden:

So spannend alle diese Ergebnisse auch sind – bei meinem praktischen Problem hätten sie wohl kaum geholfen. Schließlich habe ich damals nicht nur vier oder fünf Crêpes gebacken, sondern um die 30. Die einfachste Lösung wäre für mich gewesen, einen zweiten (und vielleicht noch einen dritten) Teller zu holen und die Crêpes nach und nach zu sortieren. Tatsächlich habe ich damals aber nichts von alldem gemacht: Ich habe ja keine trockenen Crêpes serviert, sondern habe sie mit Nutella bestrichen und zu schmalen Röllchen geformt. Damit lässt sich eine verbrannte Seite hervorragend kaschieren und die Größenunterschiede fallen nicht mehr allzu sehr auf. Problem gelöst!