Direkt zum Inhalt

Die fabelhafte Welt der Mathematik: Das Geheimnis der Pfannkuchenzahlen

Viele Mathematiker haben sich den Kopf darüber zerbrochen, wie man Pfannkuchen richtig sortiert. Wichtige Fortschritte konnten Bill Gates und ein Autor der »Simpsons« leisten.
Ein Stapel Pfannkuchen auf einem Teller
Nur selten fallen Pfannkuchen so gleichmäßig aus. Will man sie der Größe nach sortieren, kann die richtige Mathematik helfen.

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.

Viele Menschen denken, Mathematik sei kompliziert und öde. In dieser Serie möchten wir das widerlegen – und stellen unsere liebsten Gegenbeispiele vor: von schlechtem Wetter über magische Verdopplungen hin zu Steuertricks. Die Artikel könnt ihr hier lesen oder das Buch kaufen.

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).

Pfannkuchen sortieren | Wenn man einen chaotischen Pfannkuchenstapel hat (oben links), kann man durch geschicktes Wenden (von links oben nach rechts unten) die Pfannkuchen der Größe nach sortieren.

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 · 1018 verschiedene Anordnungen, also mehr als zwei Milliarden Milliarden!

Pfannkuchen n2345678910111213141516171819
Drehungen13457891011131415161718192022

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 17n16 und höchstens (5 + 5n)3 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 15n14 und 18n11 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 3n2 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:

verbrannte Pfannkuchen n23456789101112
Drehungen4681012141517181921

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!

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.