+- Foren / Forums (https://www.mathekalender.de/wp/forum)
+-- Forum: Lösungen / Solutions (https://www.mathekalender.de/wp/forum/forum-161.html)
+--- Forum: Aufgabe 4 / Challenge 4 (https://www.mathekalender.de/wp/forum/forum-173.html)
+--- Thema: 4 Lösung / Solution (/thread-1055.html)
Seiten:
1
2
RE: 4 Lösung / Solution - Batata - 12-13-2024
ist schon komisch die lösungswege anderer leute hier zu lesen weil mein gefühlt so viel simpler war
die wahrscheinlichkeit, dass er rauskommt, is die wahrscheinlichkeit dass er ein mal den richtigen weg wählt, plus die w. von 2 mal den richtigen weg usw… also eigentlich nur (1/3)^n mit n gegen unendlich
RE: 4 Lösung / Solution - marac - 12-13-2024
Ich hab mir hier eine simple Rekursion zuhilfe genommen:
Die Wahrscheinlichkeit p, aus dem Wald herauszufinden, ist
p = 1/3 + 2/3*p²
(1/3, dass ich direkt rauskomme, plus 2/3, dass ich einen falschen Weg nehme, von dort aus es aber zweimal schaffe, den Weg zurück zu finden)
Das lässt sich auflösen zu p1=1 und p2=1/2, und dass p=1 in dem Fall ausscheidet, ergibt sich trivial, ich kann mich ja blöd anstellen und jedes mal tiefer in den unendlichen Wald laufen.
RE: 4 Lösung / Solution - Linsen_mit_Spatzle - 12-16-2024
(12-13-2024, 04:39 PM)marac schrieb: Die Wahrscheinlichkeit p, aus dem Wald herauszufinden, ist
p = 1/3 + 2/3*p²
(1/3, dass ich direkt rauskomme, plus 2/3, dass ich einen falschen Weg nehme, von dort aus es aber zweimal schaffe, den Weg zurück zu finden)
Das lässt sich auflösen zu p1=1 und p2=1/2, und dass p=1 in dem Fall ausscheidet, ergibt sich trivial, ich kann mich ja blöd anstellen und jedes mal tiefer in den unendlichen Wald laufen.
So hab ich es auch gemacht - aber p=1 hatte ich von vorneherein ausgeschlossen, soviel wusste ich immerhin über Irrfahrten.
Dein Argument zeigt, dass es nicht ausgeschlossen ist, nie herauszufinden - aber die Wahrscheinlichkeit könnte trotzdem 0 sein (ohne Zusatzargument).
RE: 4 Lösung / Solution - Mathewichtel - 12-30-2024
(12-12-2024, 09:16 PM)pierrot schrieb: Ich habe es zum einen mit einer unendlichen Markowkette gelöst. Da die Übergangswahrscheinlichkeiten konstant sind, konnte man mit einer kleinen Umformung nachvollziehen, dass sich die Wahrscheinlichkeiten von Stufe zu Stufe halbieren müssen. Quasi ne diskrete DGL mit Anfangsbedingung.
In einer lösungsvariante habe ich mit einem cas Programm (Maple) die W-Keit direkt bestimmt.
Hier die Lösungsskizzen:
https://www.dropbox.com/scl/fi/y106dx28bvgupksqqwh0f/04_verloren-im-Wald.jpeg?rlkey=zp10cyws6gxqsedxj1rkj1efa&st=y5inwgkw&dl=0
Ich habe habe es wie in deinem zweiten Lösungsweg versucht und hatte aber Schwierigkeiten, die dabei auftretenden Zahlen a_n (1, 2, 5, 14, 42, 132, 429,…) in den Griff zu bekommen. Sie geben ja jeweils die Anzahl der möglichen Wege an, auf denen man genau nach n „Zügen“ den Ausgang erreichen kann und entstehen wohl aus einer Variante des Pascalschen Dreiecks.
Ich habe inzwischen nachgelesen, dass sie als Catalan-Zahlen bekannt sind.
Aber kommt man mit dem entstandenen Term auch ohne „Rechenknecht“ auf das Ergebnis 0,5? Da wusste ich zumindest nicht mehr weiter…
RE: 4 Lösung / Solution - marac - 12-31-2024
(12-16-2024, 10:23 PM)Linsen_mit_Spatzle schrieb: Dein Argument zeigt, dass es nicht ausgeschlossen ist, nie herauszufinden - aber die Wahrscheinlichkeit könnte trotzdem 0 sein (ohne Zusatzargument).
Schon richtig, die Wahrscheinlichkeit, aus dem Wald heraus zu finden, könnte auch dann (gerundet) 1 sein, wenn es Gegenbeispiele gibt, in der Auflösung der quadratischen Gleichung kommt aber eine "echte" 1 raus und keine gerundete, und das wäre in diesem Fall dann schon mit "ausnahmslos immer" gleichsetzbar.
RE: 4 Lösung / Solution - Linsen_mit_Spatzle - 01-01-2025
(12-31-2024, 12:18 AM)marac schrieb:(12-16-2024, 10:23 PM)Linsen_mit_Spatzle schrieb: Dein Argument zeigt, dass es nicht ausgeschlossen ist, nie herauszufinden - aber die Wahrscheinlichkeit könnte trotzdem 0 sein (ohne Zusatzargument).
Schon richtig, die Wahrscheinlichkeit, aus dem Wald heraus zu finden, könnte auch dann (gerundet) 1 sein, wenn es Gegenbeispiele gibt, in der Auflösung der quadratischen Gleichung kommt aber eine "echte" 1 raus und keine gerundete, und das wäre in diesem Fall dann schon mit "ausnahmslos immer" gleichsetzbar.
Ich wollte darauf hinaus, dass "Wahrscheinlichkeit=1" und "sicher" nicht gleichbedeutend sind. ("Sicher" impliziert "Wahrscheinlichkeit=1", aber nicht umgekehrt.)
Insbesondere führen einzelne Gegenbeispiele nicht dazu, dass die Wahrscheinlichkeit < 1 sein müsste. (Die Wahrscheinlichkeit für das Gegenbeispiel muss dann aber natürlich 0 sein.)
Noch insbesonderer hat das Gegenbeispiel "immer tiefer in den Wald hinein" die Wahrscheinlichkeit 0, so dass auch in diesem Fall die Wahrscheinlichkeit=1 durch dieses Gegenbeispiel nicht ausgeschlossen wird.
(Jedes Gegenbeispiel im Sinne eines einzelnen Weges hat die Wahrscheinlichkeit 0, da der Weg unendlich lang sein muss. Die Gesamtheit aller Gegenbeispiele hat natürlich die Wahrscheinlichkeit 0.5, das ist kein Widerspruch.)
RE: 4 Lösung / Solution - MatheJuergen - 01-02-2025
Ich habe zu Beginn auch viel zu kompliziert gedacht und die vielen Hin- und Herwege (tiefer in den Wald rein und dann wieder näher zum Ausgang usw.) betrachtet.
Dann habe ich einen Reset gemacht und mich überhaupt nicht dafür interessiert wie und nach wie vielen Schritten man auf eine bestimmte Lichtung (eigentlich Lichtungsstufe) kommt, sondern nur noch wie hoch die Wahrscheinlichkeit ist von dieser Lichtung ohne Umwege zum Ausgang zu kommen.
Das führt direkt auf die geometrische Reihe mit q = 1/3, allerdings ohne das Startglied q^0 = 1. Diese Reihe hat den Grenzwert 1/(1-q) - 1 = 3/2 - 1 = 1/2.
RE: 4 Lösung / Solution - Kosakenzipfel - 01-02-2025
(01-02-2025, 06:35 PM)MatheJuergen schrieb: Ich habe zu Beginn auch viel zu kompliziert gedacht und die vielen Hin- und Herwege (tiefer in den Wald rein und dann wieder näher zum Ausgang usw.) betrachtet.Die Idee verstehe ich überhaupt nicht. 42 geteilt durch 84 ist auch 1/2, aber hat nichts mit der Frage zu tun.
Dann habe ich einen Reset gemacht und mich überhaupt nicht dafür interessiert wie und nach wie vielen Schritten man auf eine bestimmte Lichtung (eigentlich Lichtungsstufe) kommt, sondern nur noch wie hoch die Wahrscheinlichkeit ist von dieser Lichtung ohne Umwege zum Ausgang zu kommen.
Das führt direkt auf die geometrische Reihe mit q = 1/3, allerdings ohne das Startglied q^0 = 1. Diese Reihe hat den Grenzwert 1/(1-q) - 1 = 3/2 - 1 = 1/2.
Warum ist es gleichwertig alle lichtungen ohne Umwege zusammenzuzählen, und alle Umwege von der ersten Lichtung?
RE: 4 Lösung / Solution - MatheJuergen - 01-03-2025
(01-02-2025, 09:56 PM)Kosakenzipfel schrieb:Na ja, welch Irrtum deinerseits(01-02-2025, 06:35 PM)MatheJuergen schrieb: Ich habe zu Beginn auch viel zu kompliziert gedacht und die vielen Hin- und Herwege (tiefer in den Wald rein und dann wieder näher zum Ausgang usw.) betrachtet.Die Idee verstehe ich überhaupt nicht. 42 geteilt durch 84 ist auch 1/2, aber hat nichts mit der Frage zu tun.
Dann habe ich einen Reset gemacht und mich überhaupt nicht dafür interessiert wie und nach wie vielen Schritten man auf eine bestimmte Lichtung (eigentlich Lichtungsstufe) kommt, sondern nur noch wie hoch die Wahrscheinlichkeit ist von dieser Lichtung ohne Umwege zum Ausgang zu kommen.
Das führt direkt auf die geometrische Reihe mit q = 1/3, allerdings ohne das Startglied q^0 = 1. Diese Reihe hat den Grenzwert 1/(1-q) - 1 = 3/2 - 1 = 1/2.
Warum ist es gleichwertig alle lichtungen ohne Umwege zusammenzuzählen, und alle Umwege von der ersten Lichtung?
42 ......usw. hat natürlich mit der Frage zu tun...... (denn bekanntlich ist ja 42 die Antwort auf alle Fragen).Doch jetzt ernsthaft:
Man kann sich das Problem wie einen linearen "random walk" mit unendlich vielen Zuständen vorstellen. Sagen wir mal links ist der Ausgang und nach rechts geht es tiefer in den Wald hinein. Die Wahrscheinlichkeit sich von einer der Lichtungen L_k nach links zu bewegen ist 1/3 und nach rechts 2/3.
Zunächst habe ich nur die Wege, die direkt von L_k zum Ausgang führen betrachtet, um eine untere Schranke für die gesuchte Wahrscheinlichkeit zu erhalten. Mit dieser unteren Schranke kann man ja auch schon einige Antwortmöglichkeiten (Die Antworten 1 bis 5) ausschließen. Danach habe ich versucht die "indirekten" Wege zu untersuchen, also z.B. L_1 --> L_2 --> L_1 -->Ausgang usw.
Dabei kam zumindest ich schnell an meine Grenzen, denn das sind schon verdammt viele Möglichkeiten. Aber dann schaute ich mir den oben betrachteten Weg mal genauer an und da fiel mir auf, dass da ja auch der direkte Weg von L_2 zum Ausgang mit enthalten ist. Diesen Weg zähle ich also doppelt, genau genommen noch n-fach, denn schließlich beinhalten alle indirekten Wege zum Ausgang auch die Sequenz L_2 --> L_1 --> Ausgang.
Also entschied ich mich "intuitiv" nur die direkten Wege zu zählen.
Dann hab ich zur "Absicherung" einen endlichen linearen "random walk" betrachtet, der außer dem absorbierenden Zustand links (Ausgang) noch einen absorbierenden Zustand rechts (verloren im Wald) einführte.
Ich habe dann den Startvektor ( 0 ; 1 ; 0 ; .....; 0) für verschiedene n mit der n x n Übergangsmatrix sehr sehr oft multipliziert (natürlich mit einem technischen Hilfsmittel: GTR CG-50). Und dann führte dieses symmetrische Problem zu für große n zu einer Wahrscheinlichkeit von 0,5 am linken Ende zu landen (also Ausgang). Das ist praktisch die gleiche Situation wie bei Aufgabe 20 im 1.Jahr.
Natürlich ist in meiner Erläuterung kein exakter Beweis enthalten, dass sich das genau ausgleicht, aber offensichtlich ist es so.
RE: 4 Lösung / Solution - Kosakenzipfel - 01-03-2025
Ok, danke, mit der zweiten Variante hab ich es auch gemacht. Mir fehlte der Grund warum beides gleich ist.
Ich habe recht schnell die Version mit der quadratischen gleichung gehabt, aber brauchte dann eine Entscheidung für (bzw gegen) eine der Lösungen. Und dann habe auch ich den Rechner angeschmissen und ein Monte Carlo Experiment programmiert. Ich habe jeweils nur 100 Schritte genommen, das reicht um eine schöne normalverteilung für die erreichte Lichtung zu bekommen.
Da die w-keit für raus und rein verschieden sind, bewegt sich der Erwartungswert mit jedem Schritt in den Wald rein: delta=-1/3+2/3. Gleichzeitig wird die Kurve mit jedem Schritt breiter, da jedesmal die Varianz um 1/3*(4/3)^2+2/3*(2/3)^2 zunimmt.
Damit war klar, dass die w-keit rauszukommen nicht 1 sein kann. Und als Nebenprodukt kam raus, dass in der Hälfte der Versuche der Ausgang bereits in den ersten 100 Schritten gefunden wurde, analog zu deinem random-walk. Aber da mit jedem erfolglosen Schritt eh die w-keit rauszufinden sinkt, reichten die 100 Schritte.