Find the princess

Autor:: MismatchEta

Problemstellung

Eine Prinzessin lebt in einem Schloss mit 4 nebeneinanderliegenden Schlafzimmern. Jedes der Schlafzimmer hat genau einen Eingang. Jede Nacht schläft die Prinzessin in einem der Zimmer. Sie folgt dabei folgenden Regeln:

Sie schläft in der 1. Nacht in einem beliebigen der 4 Räume.
Sie schläft keine zwei Nächte in Folge im gleichen Raum.
Sie wechselt immer nur in eines der benachbarten Zimmer.

Schläft die Prinzessin in der ersten Nacht beispielsweise in Raum 2, kann sie in der Nacht danach also nur in Raum 1 oder Raum 3 schlafen. Jede Nacht möchte ein Prinz die Prinzessin (aus jugendfreien Gründen) besuchen. Dabei darf er jede Nacht aber nur genau eine Tür öffnen und nachsehen, ob die Prinzessin in diesem Raum ist. Wenn Sie im gewählten Raum ist, ist die Suche vorbei und der Prinz und die Prinzessin leben glücklich bis ans Ende ihrer Tage. Wenn Sie nicht im gewählten Raum ist, muss der Prinz in der Nacht danach wiederkommen.

Frage

Ohne eine Strategie könnte der Prinz die Prinzessin ewig suchen. Entsprechend stellt er sich folgende Frage: Mit welcher Strategie findet der Prinz die Prinzessin mit Sicherheit? Wie viele Nächte braucht er mit dieser Strategie höchstens?

Anleitung

Versetze dich in die Rolle des Prinzen. Klicke nacheinander auf eine der Türen im Applet unten. Wenn du die Tür mit der Prinzessin findest, erscheint im Koordinatensystem ein grüner Punkt, um die Anzahl deiner Versuche zu markieren (x-Achse = Spielrunde, y-Achse = Anzahl der Versuche). Das Spiel startet dann automatisch von vorne. Um ganz vorne zu beginnen, klicke den "Spiel neustarten" Button.

Deine Strategie

Beschreibe die Strategie, die du beim Anklicken der Türen verwendet hast. (Schreibe zum Beispiel auf, in welcher Reihenfolge die Türen zu öffnen sind)

Maximale Anzahl der Nächte

Wie viele Nächte brauchst du mit deiner Strategie höchstens, um die Prinzessin zu finden?

Die optimale Strategie

Überlege dir, wie deine Strategie verbessert werden kann. Ausprobieren kannst du sie am Applet oben. Beschreibe deine optimierte Strategie. Wie viele Nächste brauchst du jetzt höchstens?

Erweiterung und Lösung

In diesem Video (englisch) wird das Problem nochmals geschildert und die Lösung erläutert. Zum Nachdenken:

Wie sieht die optimale Strategie für 5,6,... Türen aus? (Hinweis: Eine Unterscheidung zwischen einer geraden und ungeraden Anzahl von Türen mag hilfreich sein)
Kann die Strategie für n Türen erweitert werden?