AlleRezepteKnow-howMenschenTrends&KulturBuch&FilmAktuelles

Pancake numbers

Trends&Kultur | 11. Februar 2019

 

 

Wusstet ihr dass sich die höhere Mathematik mit Pfannkuchen beschäftigt?
Es gibt die sogenannte Pancake number, bzw. Pfannkuchenzahl. Dabei geht es nicht darum,  Rekorde im Pfannkuchen essen zu brechen, sondern hier zerbrechen sich schlaue Leute den Kopf:

 

Wir haben einen Stapel mit unterschiedlich großen Pfannkuchen und diese sollen der Größe nach sortiert werden. Wir dürfen nur mit einem Pfannenwender Teile des Stapels abheben und umdrehen. Wie oft müssen wir die (Teil-)Stapel dann mit dem Pfannenwender wenden? Der größte Pfannkuchen soll unten liegen, der Kleinste oben.

 

Wikipedia versucht zu erklären:

Die Anzahl der nötigen Schritte, um einen Stapel aus n Pfannkuchen in jedem Fall zu sortieren, wird als Pn  bezeichnet. Die Werte sind für kleine n bekannt, für größere gibt es Abschätzungen. Offensichtlich gilt P1=0, da ein Stapel aus einem Pfannkuchen bereits sortiert ist, und P2=1, da im Fall, dass der größere Pfannkuchen zu Beginn oben liegt, der Stapel dadurch sortiert werden kann, dass er einfach umgekehrt wird.
Ein einfacher Algorithmus zeigt Pn+1<=2+Pn : Dazu wird der größte Pfannkuchen zunächst an die Spitze gebracht, anschließend wird der Stapel umgewendet, dass er sich ganz unten befindet. Nach diesen zwei Schritten wird der restliche Stapel sortiert, ohne den untersten Pfannkuchen zu beachten, dies geschieht in Pn Schritten. Zusammen mit P2 =1 gilt also Pn<=2n -3.


Seid ihr noch da?

Man hat diese Formel im Laufe der Zeit immer weiter verbessert. Von Bill Gates und seinem Kollegen Christos Papadimitriou stammt dies:
Pn < (5n +5)/3
Das nannte sich dann nicht Pfannkuchenzahl, sondern 'Bounds for sorting by prefix reversal'.
Aha!

n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Pn

0

1

3

4

5

7

8

9

10

11

13

14

15

16

17

18

19

Hier ist die Aufstellung der kleinen Zahlen, für die großen Zahlen lassen die Mathematiker immer noch die Computer heiß laufen. So weiß man noch nicht, wie sich das Ganze bei schlappen 20 Pfannkuchen verhält...

Die Mathematikerin Katie Steckles hat die Sache mit den Pfannkuchen in ihrem Video sehr anschaulich erklärt.
 

Danke Katie! Wir werden das jetzt mal ausprobieren. Das dürfte jedoch nicht so schwer sein, denn unsere Pfannkuchen sind so begehrt, dass der Stapel nicht über die kleinen Zahlen hinauswächst!


Wer sich mehr für die kulturellen Aspekte des Pfannkuchens interessiert, sollte hier weiterlesen.

 

Ähnliche Beiträge aus "Alle"