Ich musste erstmal über sehr, sehr viele Versuche hinweg scrollen, meine Lösung für die Aufgabe 18 zu beweisen, um meine Notizen zu dieser Aufgabe zu finden...
Man muss für den Erfolg ja an einer der unteren Ecken starten (und an der anderen enden.) Mit einer Wahrscheinlichkeit von 3/5 fängt er an der falschen Ecke an und hat keine Chance mehr. Also muss ich mir nur noch den Fall ansehen, dass er an einer unteren Ecke startet.
Ich habe die Ecken von oben nach unten und links nach rechts mit ABCDE benannt. Aus Symmetriegründen kann ich davon ausgehen, dass er bei D startet - der andere Fall wird genau dieselbe Erfolgswahrscheinlichkeit haben. Das Einzige, das jetzt noch schiefgehen kann, ist, dass er die Ecke E zum zweiten Mal besucht, bevor er alle anderen Wege durch hat, und dann von dort nicht mehr weg kommt. Von allen anderen Ecken aus kann er seinen Weg wegen der geraden Anzahl an Kanten immer fortsetzen, wenn er erst einmal dorthin gekommen ist. Also habe ich mir überlegt, wie hoch die Wahrscheinlichkeit hat, dass er zu früh zu E zurückkehrt.
Sein Weg ist durch die Reihenfolge der besuchten Ecken eindeutig bestimmt, man kann diesen also z.B. als DBACEBCDE identifizieren. Es gibt übrigens am Anfang auch keinen Unterschied zwischen den Ecken B und C - beide sind mit allen anderen Ecken verbunden - und ich muss z.B., wenn ich DB als Start schon durchgerechnet habe, nicht noch DC betrachten.
Erstmal habe ich mir überlegt, wann und wie er das erste Mal zu E kommen kann. Da gibt es:
DE
DBE
DBCE
DBACE, DBCDE
DBACBE, DBACDE, DBCABE
Bei den zuletzt genannten kann er sicher nicht mehr fehlschlagen, da nur noch 3 Schritte übrig sind und man mindestens 3 Schritte braucht, um von E wieder zu E zu kommen. Wenn man das Haus aufmalt und die bereits benutzten Kanten löscht, sieht man den Optionen DBCE, DBACE, DBCDE aber auch an, dass er hier nicht frühzeitig zu E zurückkommen kann, da der verbleibende Graph nur noch ein Kreis ist.
Wenn er bei D startet, kann er also nur dann noch fehlschlagen, wenn er E als zweiten oder dritten Knoten besucht.
Von DBE aus besteht der Graph aus zwei Dreiecken ABC und CDE, die sich in C treffen. Er kann nun entweder direkt zu C, oder erst zu D und dann zu C weitergehen. In jedem Fall kommt er am Punkt C an und hat dann von dort aus 3 Optionen: Über A oder über B in das Dreieck aus ABC gehen und damit sicher alle anderen Knoten vor E besuchen, oder (je nach Ausgangspfad direkt oder über D) zu E zurückkehren und scheitern. Die Erfolgswahrscheinlichkeit von DBE aus ist also 2/3.
Von DE aus kann man aus Symmetriegründen davon ausgehen, dass er danach zu B geht. Dann geht es zu A, C oder D weiter.
von DEBA wird man erzwungenermaßen zu C weitergeschickt und dort gibt es mit einer Chance von 2/3 das zum Erfolg führende Dreieck DBC, oder mit einer Chance von 1/3 den direkten Weg zu E.
Von DEBD sieht es genau so aus, man muss zu C weitergehen und hat dann das Dreieck ABC oder E zur Auswahl.
Von DEBC aus landet man ähnlich dazu zu 2/3 über A oder D im Kreis aus DBAC oder zu 1/3 direkt wieder bei E.
Egal, welchen Weg er von DE aus nimmt, er kommt dann immer mit einer Chance von 2/3 in einen Kreis, der alle verbleibenden Knoten besucht, bevor er zu E zurückkommt, sodass er das Haus erfolgreich zeichnet, oder mit einer Chance von 1/3 direkt zurück zu E und scheitert. Die Erfolgswahrscheinlichkeit von DE aus ist also 2/3.
Jetzt fehlt nur noch, mit welcher Wahrscheinlichkeit er von D aus DBE (bzw. DCE, den identischen Fall) oder DE erreicht.
Von D aus kommt er zu 1/3 zu DE (Erfolgswahrscheinlichkeit ab da 2/3) und zu 2/3 zu DB bzw DC. Von da aus kommt er zu 1/3 zu DBE bzw DCE. Er hat also von D aus eine Chance von 1/3 + 2/3*1/3 = 5/9, einen der Pfade mit Fehlschlagschance zu nehmen.
Insgesamt erreicht er daher von D aus zu 5/9*2/3 + 4/9*1 = 22/27 das Ziel. Ebenso von E aus.
Die Gesamtchance für einen Erfolg ist also 2/5 (nicht sofort zu verlieren) * 22/27 = 44/135. Das ist 0.3[259], die 100ste Nachkommastelle ist also 9.
Ich hatte übrigens diese Aufgabe als "zu schwer" bewertet, was im Nachhinein völliger Unsinn war - wenn überhaupt eine Aufgabe "zu schwer" war (Spaß hatte ich auch an den ganz schwierigen), dann sicher nicht diese, die schwierigkeitsmäßig eher im Mittelfeld liegt. Ich war an dem Tag nur irgendwie zu paranoid, dass ich mich irgendwo mittendrin verrechnet habe und es nicht merke, weil man hier nicht an den Antwortmöglichkeiten erkennen kann, wenn man einen Fehler gemacht hat... Offenbar sind andere aber auch auf dasselbe Ergebnis gekommen.
Man muss für den Erfolg ja an einer der unteren Ecken starten (und an der anderen enden.) Mit einer Wahrscheinlichkeit von 3/5 fängt er an der falschen Ecke an und hat keine Chance mehr. Also muss ich mir nur noch den Fall ansehen, dass er an einer unteren Ecke startet.
Ich habe die Ecken von oben nach unten und links nach rechts mit ABCDE benannt. Aus Symmetriegründen kann ich davon ausgehen, dass er bei D startet - der andere Fall wird genau dieselbe Erfolgswahrscheinlichkeit haben. Das Einzige, das jetzt noch schiefgehen kann, ist, dass er die Ecke E zum zweiten Mal besucht, bevor er alle anderen Wege durch hat, und dann von dort nicht mehr weg kommt. Von allen anderen Ecken aus kann er seinen Weg wegen der geraden Anzahl an Kanten immer fortsetzen, wenn er erst einmal dorthin gekommen ist. Also habe ich mir überlegt, wie hoch die Wahrscheinlichkeit hat, dass er zu früh zu E zurückkehrt.
Sein Weg ist durch die Reihenfolge der besuchten Ecken eindeutig bestimmt, man kann diesen also z.B. als DBACEBCDE identifizieren. Es gibt übrigens am Anfang auch keinen Unterschied zwischen den Ecken B und C - beide sind mit allen anderen Ecken verbunden - und ich muss z.B., wenn ich DB als Start schon durchgerechnet habe, nicht noch DC betrachten.
Erstmal habe ich mir überlegt, wann und wie er das erste Mal zu E kommen kann. Da gibt es:
DE
DBE
DBCE
DBACE, DBCDE
DBACBE, DBACDE, DBCABE
Bei den zuletzt genannten kann er sicher nicht mehr fehlschlagen, da nur noch 3 Schritte übrig sind und man mindestens 3 Schritte braucht, um von E wieder zu E zu kommen. Wenn man das Haus aufmalt und die bereits benutzten Kanten löscht, sieht man den Optionen DBCE, DBACE, DBCDE aber auch an, dass er hier nicht frühzeitig zu E zurückkommen kann, da der verbleibende Graph nur noch ein Kreis ist.
Wenn er bei D startet, kann er also nur dann noch fehlschlagen, wenn er E als zweiten oder dritten Knoten besucht.
Von DBE aus besteht der Graph aus zwei Dreiecken ABC und CDE, die sich in C treffen. Er kann nun entweder direkt zu C, oder erst zu D und dann zu C weitergehen. In jedem Fall kommt er am Punkt C an und hat dann von dort aus 3 Optionen: Über A oder über B in das Dreieck aus ABC gehen und damit sicher alle anderen Knoten vor E besuchen, oder (je nach Ausgangspfad direkt oder über D) zu E zurückkehren und scheitern. Die Erfolgswahrscheinlichkeit von DBE aus ist also 2/3.
Von DE aus kann man aus Symmetriegründen davon ausgehen, dass er danach zu B geht. Dann geht es zu A, C oder D weiter.
von DEBA wird man erzwungenermaßen zu C weitergeschickt und dort gibt es mit einer Chance von 2/3 das zum Erfolg führende Dreieck DBC, oder mit einer Chance von 1/3 den direkten Weg zu E.
Von DEBD sieht es genau so aus, man muss zu C weitergehen und hat dann das Dreieck ABC oder E zur Auswahl.
Von DEBC aus landet man ähnlich dazu zu 2/3 über A oder D im Kreis aus DBAC oder zu 1/3 direkt wieder bei E.
Egal, welchen Weg er von DE aus nimmt, er kommt dann immer mit einer Chance von 2/3 in einen Kreis, der alle verbleibenden Knoten besucht, bevor er zu E zurückkommt, sodass er das Haus erfolgreich zeichnet, oder mit einer Chance von 1/3 direkt zurück zu E und scheitert. Die Erfolgswahrscheinlichkeit von DE aus ist also 2/3.
Jetzt fehlt nur noch, mit welcher Wahrscheinlichkeit er von D aus DBE (bzw. DCE, den identischen Fall) oder DE erreicht.
Von D aus kommt er zu 1/3 zu DE (Erfolgswahrscheinlichkeit ab da 2/3) und zu 2/3 zu DB bzw DC. Von da aus kommt er zu 1/3 zu DBE bzw DCE. Er hat also von D aus eine Chance von 1/3 + 2/3*1/3 = 5/9, einen der Pfade mit Fehlschlagschance zu nehmen.
Insgesamt erreicht er daher von D aus zu 5/9*2/3 + 4/9*1 = 22/27 das Ziel. Ebenso von E aus.
Die Gesamtchance für einen Erfolg ist also 2/5 (nicht sofort zu verlieren) * 22/27 = 44/135. Das ist 0.3[259], die 100ste Nachkommastelle ist also 9.
Ich hatte übrigens diese Aufgabe als "zu schwer" bewertet, was im Nachhinein völliger Unsinn war - wenn überhaupt eine Aufgabe "zu schwer" war (Spaß hatte ich auch an den ganz schwierigen), dann sicher nicht diese, die schwierigkeitsmäßig eher im Mittelfeld liegt. Ich war an dem Tag nur irgendwie zu paranoid, dass ich mich irgendwo mittendrin verrechnet habe und es nicht merke, weil man hier nicht an den Antwortmöglichkeiten erkennen kann, wenn man einen Fehler gemacht hat... Offenbar sind andere aber auch auf dasselbe Ergebnis gekommen.