Beweis, dass n>=1 Pfannkuchen mit maximal 2n-2 Umdrehmanövern sortiert werden können? mit vollständiger Induktion.

Question

Wie kann man mit induktion nach n beweisen, dass n>=1 Pfannkuchen mit maximal 2n-2 Umdrehmanövern sortiert werden können? Es soll von unten nach oben sortiert sein. Der größte unten der kleinste oben.

Comments

Kannst du die " Umdrehmanöver " etwas genauer beschreiben? Gibt es nur einen Stapel / Berg von Pfannkuchen?

---

Ja genau es gibt einen Stapel Pfannkuchen und der "Kellner" kann beliebig viele Pfannkuchen nehmen und diese dann einmal umdrehen. Das wiederholt er so oft bist der Stapel sortiert ist.

---

Verankerung:

n=1: Man muss nichts umdrehen. 2*1-2 = 0

n=2: Wenn nötig dreht man 1 mal den ganzen Stapel. Das ist weniger als 2*2 - 2 = 2

Ab jetzt wird's schwieriger. Fortsetzung, wenn ich dazukomme: Morgen.

---

Alles klar, danke :)

Soweit hab ich es sogar geschafft, nur wie du sagst wird es ab dann schwieriger....

Answer 1

Verankerung: Kommentare zur Fragen.

Induktionsschritt: n --> n+1 Pfannkuchen. Behauptung: max. 2(n+1) - 2 = 2n  Drehungen.

Gegeben: Berg mit n+1 Pfannkuchen.

Jetzt muss der grösste ganz nach unten kommen, wenn er noch nicht dort ist. Man dreht als Erstes so, dass der Grösste zuoberst landet. Nun (2. DREHUNG) wird der ganze Stapel gedreht. 

Nun muss man nur noch den Stapel der Höhe n oberhalb vom Grössten sortieren: Braucht nach Induktionsvoraussetzung maximal 2n-2 Drehungen.

Drehungen im Ganzen: Maximal 2 + (2n-2) = 2n q.e.d.

Comments

Danke für die schnelle Antwort ich geh das nochmal durch und versuche es alles nachzuvollziehen. Aber das hört sich ja schon gut an.

---

Ich muss nochmal ganz dumm fragen, wie kommst du auf 2(n+1) - 2 = 2n ?

Ab da ist dann alles schlüssig, nur verstehe ich diesen schritt noch nicht.

---

nwm...ist einfach aufgelöst. Ist wohl schon zu spät, dass ich sowas übersehe -.-

---

Die Behauptung ist:

Für n Pfannkuchen sind maximal 2n-2 Drehungen nötig.

Die Behauptung oben im Induktionsschritt ist daher:

Für n+1 Pfannkuchen sind maximal 2(n+1) - 2 Drehungen nötig.

---

Und wie zeigt man dann, dass der induktionsanfang stimmt?

---

Das ist die Verankerung oben in den Kommentaren! Das genügt. 

Das Prinzip der Induktion sagt ja nun, 

wegen dem Induktionsschritt von n nach n+1:

Es stimmt für n=2, darum stimmt es für n=3.

Es stimmt für n=3, darum stimmt es für n=4.

Es stimmt für n=4, darum stimmt es für n=5.

Es stimmt für n=5, darum stimmt es für n=6.

Es stimmt für n=6, darum stimmt es für n=7.

Es stimmt für n=7, darum stimmt es für n=8.

Es stimmt für n=8, darum stimmt es für n=9.

Es stimmt für n=9, darum stimmt es für n=10.

usw.