Genau diese Frage hatte ich mir auch schon gestellt und hatte endlich Anlass am 6.12 ihr auf den Grund zu gehen.
Klassisches Beispiel für einen Eulerweg. Man muss unten starten und unten ankommen (ungerade Knoten nur unten).
Also Obergrenze 2/5. Nun sind aber nicht alle Wege, die unten starten, gut!
Wenn man unten startet, kann man zeigen (siehe Lösungsskizze unten), dass
- 2/3 der Wege erfolgreich sind, wenn man unten zur anderen unteren Ecke startet
- 8/9 der Wege erfolgreich sind, wenn man nach oben geht: egal ob gerade nach oben oder diagonal nach oben.
Insgesamt führen dann 2/5*(1/3*2/3 + 2/3*8/9)= 44/135=0,3 259 259 259 259... zum Ziel. Also ist die 100. Ziffer die 9: 100 kongruent 4 mod 3.
Meine Lösung basiert auf der Erkenntnis, dass es ingesamt 54 Möglichkeiten geben kann, die erfolgreich sind (wenn man unten startet; die anderen Fälle gehen ja logischerweise nicht). Von diesen 54 Möglichkeiten malt man sich auf, dass 10 nicht gehen und erhält dann 44/54 Möglichkeiten, die gehen und die nimmt man analog zu dir mit 2/5 mal...
Meine Lösung ist die 5:
Da man an den Knoten mit ungerader Kantenzahl starten muss, besteht für die richtige Wahl des Anfangspunktes die Wahrscheinlichkeit 2/5. An den Knoten mit gerader Kantenzahl geht es immer weiter, weil zu jedem Weg rein auch ein Weg raus existiert. Das vollständige Haus kann also nur dann nicht gezeichnet werden, wenn das obere Giebeldreieck weggelassen wird. Das kann aber nur passieren, wenn an den beiden mittelhohen Knoten jeweils beim ersten Eintreffen genau 1 von 3 möglichen Wegen gewählt wird, also mit einer Wahrscheinlichkeit von 1/9. Folglich wird das Haus mit einer Wahrscheinlichkeit von 2/5 * 8/9 = 16/45 =0,35555... richtig gezeichnet.
Edit: diese Lösung ist leider falsch, weil nicht nur das Giebeldreieck, sondern auch andere geschlossene Pfade weggelassen werden können, um das Haus unvollständig zu zeichnen, siehe Antwort auf Post #5, sobald sie freigegeben wurde.
(12-16-2025, 02:03 AM)rs3095 schrieb: Meine Lösung ist die 5:
Da man an den Knoten mit ungerader Kantenzahl starten muss, besteht für die richtige Wahl des Anfangspunktes die Wahrscheinlichkeit 2/5. An den Knoten mit gerader Kantenzahl geht es immer weiter, weil zu jedem Weg rein auch ein Weg raus existiert. Das vollständige Haus kann also nur dann nicht gezeichnet werden, wenn das obere Giebeldreieck weggelassen wird. Das kann aber nur passieren, wenn an den beiden mittelhohen Knoten jeweils beim ersten Eintreffen genau 1 von 3 möglichen Wegen gewählt wird, also mit einer Wahrscheinlichkeit von 1/9. Folglich wird das Haus mit einer Wahrscheinlichkeit von 2/5 * 8/9 = 16/45 =0,35555... richtig gezeichnet.
Ich denke, du hast etwas übersehen. Nämlich die folgende Situation: Du startest unten links. Dann zeichnest du: nach unten rechts, nach oben rechts, nach oben links, nach unten rechts. Dann bist du in einer Sackgasse, weil du zu früh zum Endpunkt kommst. Dann fehlt aber neben dem Dach noch die linke Seite und eine Diagonale.
(12-16-2025, 02:03 AM)rs3095 schrieb: Meine Lösung ist die 5:
Da man an den Knoten mit ungerader Kantenzahl starten muss, besteht für die richtige Wahl des Anfangspunktes die Wahrscheinlichkeit 2/5. An den Knoten mit gerader Kantenzahl geht es immer weiter, weil zu jedem Weg rein auch ein Weg raus existiert. Das vollständige Haus kann also nur dann nicht gezeichnet werden, wenn das obere Giebeldreieck weggelassen wird. Das kann aber nur passieren, wenn an den beiden mittelhohen Knoten jeweils beim ersten Eintreffen genau 1 von 3 möglichen Wegen gewählt wird, also mit einer Wahrscheinlichkeit von 1/9. Folglich wird das Haus mit einer Wahrscheinlichkeit von 2/5 * 8/9 = 16/45 =0,35555... richtig gezeichnet.
Ich denke, du hast etwas übersehen. Nämlich die folgende Situation: Du startest unten links. Dann zeichnest du: nach unten rechts, nach oben rechts, nach oben links, nach unten rechts. Dann bist du in einer Sackgasse, weil du zu früh zum Endpunkt kommst. Dann fehlt aber neben dem Dach noch die linke Seite und eine Diagonale.
Tatsächlich, nicht nur das Giebeldreieck kann ausgelassen werden, sondern bei gewähltem Ausgangspunkt auch noch zwei andere geschlossene Pfade, deren Auslassung mit einer Wahrscheinlichkeit von jeweils 1/27 eintritt. Die hatte ich in der Tat übersehen. Damit kommt man dann auch auf 2/5 * (1 - 1/9 - 2/27) = 44/135.
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.
