Vorherige Aufgabe   Übersicht 2002   Nächste Aufgabe 

Lösungen der DENKmal-Knobelaufgaben

8. Aufgabe 2002

gestellt am 13. Mai 2002 in der Knobelecke von
Abenteuer Mathematik - die Welt des Knobelns

Kasimir und das Honiglabyrinth

  Aufgabe   Lösung   Antwort 

Aufgabe

Kasi-labyrinth Krabbelkäfer Kasimir hat von einem liebenswürdigen Mitdenker ein Honigtöpfchen geschenkt bekommen und Kasimir ist gerade auf dem Weg dahin.
Was Kasimir aber nicht wusste: Ein böser Bube hat das Honigtöpfchen in einem Labyrinth versteckt!
An jeder Verzweigung des Labyrinths überlässt es Kasimir dem Zufall, in welcher Richtung es weitergehen sollte.
Ob er dabei je den Honig erreichen wird oder wieder am Ausgang des Labyrinths landet ohne den Honig gesehen und davon genascht zu haben?

Mit welcher Wahrscheinlichkeit erreicht Kasimir den Honig?

(An den Verzweigungen geht Kasimir nicht rückwärts und die Wahrscheinlichkeit, in die eine oder andere Richtung weiter zu gehen ist jeweils 0,5. Kasimir kann sich nicht erinnern, ob er schon mal an einer Verzweigung war oder ob er einen Weg schon mal gegangen ist.)

Die Lösung muss ausreichend begründet werden (Tabelle, Formel, Programm etc.).

(eingesandt von Rolf Herrmann)

Lösung

Man kann sich das Labyrinth als einen gerichteten Graphen vorstellen mit Start (Eingang), Ziel (Honig) und Verzweigungen als Ecken und den Wegabschnitten dazwischen in jeweils beiden Richtungen als Kanten. Die Ecken des abgebildeten Labyrinths seien bezeichnet mit A für die Verzweigung links, B für die ganz rechts, C für die links daneben, D für die darunter liegende, S für den Start und Z für das Ziel.

Eine Abbildung p gebe für jeden gerichteten Wegabschnitt PQ an, mit welcher Wahrscheinlichkeit man das Ziel erreicht, wenn man sich auf ihm (von P nach Q) bewegt. Über die Werte von p lässt sich ein lineares Gleichungssystem erstellen, aus dem die gesuchte Wahrscheinlichkeit p(SA) ermittelt werden kann.

Es gibt zwei triviale Werte:
(1a) p(AS) = 0
(1b) p(DZ) = 1

Die folgenden Werte ergeben sich aus der Symmetrie des Graphen:
(2a) p(BC) = 1/2
(2b) p(CC) = 1/2 (wird nicht verwendet)
(2c) p(CB) = 1/2 (wird nicht verwendet)

Die übrigen Werte lassen sich mit Hilfe von bedingten Wahrscheinlichkeiten auf andere zurück führen:
(3a) p(SA) = (p(AB)+p(AD))/2
(3b) p(AB) = (p(BC)+p(BD))/2 = p(BD)/2+1/4 wegen (2a)
(3c) p(BA) = (p(AS)+p(AD))/2 = p(AD)/2 wegen (1a)
(3d) p(AD) = (p(DB)+p(DZ))/2 = p(DB)/2+1/2 wegen (1b)
(3e) p(DA) = (p(AS)+p(AB))/2 = p(AB)/2 wegen (1a)
(3f) p(BD) = (p(DA)+p(DZ))/2 = p(DA)/2+1/2 wegen (1b)
(3g) p(DB) = (p(BA)+p(BC))/2 = p(BA)/2+1/4 wegen (2a)
(3h) p(ZD) = (p(DA)+p(DB))/2 (wird nicht verwendet)

Diese Gleichungen bilden zwei unabhängige Gleichungssysteme, die sich einzeln lösen lassen:
(4a) p(AB) = 4/7 aus (3b), (3e) und (3f)
(4b) p(AD) = 5/7 aus (3c), (3d) und (3g)

Durch Einsetzen in (3a) ergibt sich dann die Lösung:
(5) p(SA) = (p(AB)+p(AD))/2 = (4/7+5/7)/2 = 9/14

Antwort

Kasimir erreicht den Honig mit einer Wahrscheinlichkeit von 9/14 (≈ 64,3%).