Im Jahr 1975 veröffentlichte Jacob E. Goodman unter dem Pseudonym Harry Dweighter (gesprochen wie harried waiter, englisch für gequälter Ober) ein Problem, das seither als Pfannkuchen-Problem bekannt ist und für einige hundert Seiten mathematischer Forschung gesorgt hat. Wie so oft in der Mathematik ist das Problem einfach zu verstehen, aber alles andere als einfach zu lösen. Hier ist die Problemstellung: Sie haben vor sich einen Stapel kreisrunder und verschieden grosser Pfannkuchen und sollen diese der Grösse nach sortieren, vom grössten Pfannkuchen ganz unten bis zum kleinsten ganz oben. Um das zu erreichen, dürfen Sie einzig einen Spatel benutzen. Ein einzelner Schritt besteht darin, den Spatel unter einen beliebigen Pfannkuchen zu schieben, die darüber liegenden Pfannkuchen anzuheben und diesen Teilstapel umgedreht wieder auf die restlichen Pfannkuchen zu legen. Würde man wie in der Abbildung den Spatel unter Kuchen 2 schieben und dann den oberen Teilstapel umdrehen, so wäre die Reihenfolge nachher von oben nach unten gelesen: 2, 1, 4, 3. Freilich ist dieser Schritt nicht gerade günstig im Hinblick auf die Zielsetzung. Das Pfannkuchen-Problem besteht nun darin herauszufinden, in wie vielen Schritten der Stapel in jedem Fall sortiert werden kann, ganz unabhängig von der konkreten Anordnung der Kuchen. Enthält der Stapel n Kuchen und bezeichnet Pn die kleinste Zahl von Schritten, die immer ausreicht, so ist also gefragt, ob man für Pn eine Formel angeben kann. Klar ist: P₁ = 0, denn ein einzelner Pfannkuchen ist immer schon sortiert. Klar ist auch: P₂ = 1, weil zwei Kuchen entweder schon sortiert sind oder in einem Schritt sortiert werden können. Rasch klar ist auch: P₃ = 3. Man muss dazu nur alle Fälle durchspielen. Aber was kann man allgemein über P_n sagen? Nun, man kann immer den grössten Pfannkuchen in einem Schritt ganz nach oben befördern, falls er nicht schon dort ist. Dazu schiebt man den Spatel unter den grössten Kuchen und dreht den oberen Teil um. Danach schaufelt man mit dem Spatel den gesamten Stapel um, und schon liegt der grösste Kuchen zuunterst, wo er hingehört. Nach zwei Schritten befindet sich also der grösste Pfannkuchen an seinem definitiven Platz. Mit den restlichen n – 1 Kuchen verfährt man ebenso: In höchstens zwei weiteren Schritten gelangt der zweitgrösste Kuchen an seinen definitiven Platz. Fährt man so fort, so wird klar, dass der ganze Stapel spätestens nach 2n Schritten sortiert ist; es gilt also: P_n < 2n. Bill Gates hat sich auch mit diesem Problem beschäftigt. 1979, vier Jahre nach dem Abbruch seines Mathematik-Studiums in Harvard und kurz vor seinem Durchbruch bei IBM, bewies er zusammen mit Christos Papadimitriou die folgende Formel: Pn < (5n+5)/3. Bei 4 Pfannkuchen wie in der Abbildung sollten demnach 8 Schritte immer ausreichen. Tatsächlich geht es aber mit weniger Schritten. Können Sie herausfinden, wie viele Schritte in jedem Fall ausreichen?

Armin P. Barth ist Gymnasiallehrer an der Kantonsschule Baden und Autor. Die Lösung erscheint am nächsten Dienstag auf der Seite Leben&Wissen.