Homers letzter Satz: Die Simpsons und die Mathematik (German Edition)

Wie oft (als Funktion f( n ) ausgedrückt) muss ich n Pfannkuchen maximal wenden, bis sie sortiert sind?
    Oder anders ausgedrückt: Wenn Homer ins städtische Pfannkuchenhaus geht wie in »Marge und das Brezelbacken« (1997) und der Kellner ihm n Pfannkuchen in zufälliger Reihenfolge serviert, wie oft muss man sie im schlimmsten Fall wenden, bis sie nach Größe sortiert sind? Die Anzahl, wie oft man wenden muss, wird als Pfannkuchenzahl P n bezeichnet. Das Problem besteht darin, eine Formel zu finden, die P n voraussagt.
    Das Pfannkuchen-Sortierproblem weckte das Interesse von Mathematikern aus zwei Gründen: Erstens konnte es zur Lösung von Problemen in der Informatik führen, weil das Sortieren von Pfannkuchen gewisse Parallelen zum Sortieren von Daten aufweist. Zweitens war es überraschend schwer zu lösen, und Mathematiker lieben Probleme, die möglicherweise unlösbar sind.
    Einige einfache Beispiele verdeutlichen das Problem: Wie lautet die Pfannkuchenzahl für einen einzigen Pfannkuchen? Die Antwort ist null, weil ein Pfannkuchen nicht in der falschen Reihenfolge liegen kann. Also gilt: P 1 = 0.
    Wie lautet die Pfannkuchenzahl für zwei Pfannkuchen? Die Pfannkuchen kommen entweder in der richtigen Reihenfolge aus der Küche oder in der umgekehrten Reihenfolge. Der ungünstigere der beiden Fälle ist offensichtlich, und man muss nur einmal beide Pfannkuchen gleichzeitig wenden, um sie in die richtige Reihenfolge zu bringen. Also gilt: P 2 = 1.
    Wie lautet die Pfannkuchenzahl für drei Pfannkuchen? Das ist schon schwieriger, weil es sechs Ausgangsmöglichkeiten gibt. Je nach Ausgangsreihenfolge muss man die Pfannkuchen null- bis, im schlimmsten Fall, dreimal wenden, um sie in die richtige Reihenfolge zu bringen. Damit ist P 3 = 3.

    In den meisten Fällen bekommt man selbst heraus, wie man die Pfannkuchen mit möglichst wenigen Wendemanövern in die richtige Reihenfolge bringt. Doch wie der Fall mit drei Pfannkuchen bereits gezeigt hat, ist der Sortiervorgang im schlimmsten Fall nicht immer sofort ersichtlich. Im Bild oben rechts ist in jeder Zeile dargestellt, wo beim nächsten Wenden der Pfannenwender eingeschoben wird und in welcher Reihenfolge sich die Pfannkuchen nach der Aktion befinden.
    [f]
    Je größer der Pfannkuchenstapel ist, umso schwieriger ist das Problem, weil es immer mehr mögliche Ausgangsreihenfolgen gibt und immer mehr verschiedene Möglichkeiten, die Pfannkuchen zu wenden. Vor allem aber gibt es kein erkennbares Muster in der Reihe der Pfannkuchenzahlen (P n ).
    Nachfolgend sind die ersten 19 Pfannkuchenzahlen aufgelistet:
n
1
2
3
4
5
6
7
8
9
10
P
0
1
3
4
5
7
8
9
10
11

n
11
12
13
14
15
16
17
18
19
20
P
13
14
15
16
17
18
19
20
22
?
    Die zwanzigste Pfannkuchenzahl konnte bisher nicht berechnet werden, weil nicht einmal die leistungsstärksten Computer alle möglichen Pfannkuchen-Permutationen und Wende-Strategien durchgehen konnten. Und auch nach mehr als drei Jahrzehnten hat noch niemand eine Gleichung gefunden, um Pfannkuchenzahlen vorherzusagen. Daher hängt ihre Berechnung auch weiterhin von schierer Rechenleistung ab. Als einziger Durchbruch in diesem Bereich konnten Gleichungen gefunden werden, mit denen sich die Pfannkuchenzahl eingrenzen lässt. Im Jahr 1979 wurde bewiesen, dass eine Pfannkuchenzahl immer weniger als (5 n +5)/3 beträgt. Das bedeutet, dass man bei einer wahnwitzig großen Anzahl an Pfannkuchen, etwa 1000, auf jeden Fall weiß, dass die zugehörige Pfannkuchenzahl (d.h. wie oft man die Pfannkuchen im schlimmsten Fall wenden muss, bis man sie nach Größe sortiert hat) weniger beträgt als:

    Da man Pfannkuchen nicht ⅓-mal wenden kann, ist P 1000 daher kleiner gleich 1688. Dieses Ergebnis ist berühmt, weil es in einem Artikel veröffentlicht wurde, den William H. Gates gemeinsam mit Christo H. Papadimitriou verfasste. William H. Gates ist besser bekannt unter dem Namen Bill Gates und der Mitbegründer von Microsoft. Er hat nur diesen einen Fachartikel veröffentlicht. 29
    In diesem Artikel, der auf Gates’ Arbeit als Student in Harvard basiert, wird auch eine verzwickte Variation des Problems erwähnt. Beim Verbrannte-Pfannkuchen-Problem geht es um Pfannkuchen, die auf einer Seite verbrannt sind. Die Herausforderung besteht darin, sie mit der richtigen (der nicht verbrannten) Seite nach oben und der Größe nach zu sortieren. Mit diesem Problem beschäftigte sich David S. Cohen in Berkeley.
    Cohen veröffentlichte im Jahr 1995 einen Artikel über das