12: Frosch und Kröte / Frog and Toad

  • Exzellente Aufgabe! Goßes Dankeschön an Jesper Nederlof!!!

    Durch die bedingte Wahrscheinlichkeit (Voraussetzung: beide kommen im Laufe des Tages an) herrscht komplette Symmetrie: Gleichverteilung, p=0,5.

    Dies liegt daran, dass ohne die Bedingung „beide kommen an“, die Wahrscheinlichkeitsverteilungen („irgendwann“ mal auf die Null zu springen) der beiden proportional zu einander sind (gleich viele Wege führen auf die Null), auch wenn die W-keit für Fridolin jeweils (nach x-Sekunden anzukommen) viel viel vieeeel größer ist, aber eben um einen KONSTANTEN Faktor: 2^100.


    Dadurch, dass aber beide hundertprozentig im Laufe des Tages ankommen, muss man die W-Verteilung (im Tagesbereich) auf 100 Prozent hochziehen: Der „ganze Kuchen (100 Prozent)“ wird dann aber aufgrund der Proportionalität genau gleichverteilt.


    Hier ein Lösungsvorschlag formal-mathematisch aufgezogen:

    https://www.dropbox.com/s/cfbt…12_Frosch_Kroete.JPG?dl=0

  • Ich habe es zurerst durch einen Quasi-Buteforce-Ansatz gelöst. Dann ist mir aufgefallen, dass die Wahrscheinlichkeiten, dass Kriemhilde nach N Zügen angekommen ist genau gleich der Wahrscheinlichkeit ist, dass Friedolin noch nicht angekommen ist. Das ergibt die schöne Symmetrie in der Aufgabe.

  • Dieses war die einzige Aufgabe, die ich nicht in der 5-Punkte-Zeit gelöst hatte. Ich musste mir erst klar darüber werden, dass die Zahlen an den Rändern eines links- und ein rechts-abbrechenden, unsymmetrischen Pascalschen Dreiecks im selben Verhältnis stehen - hier 2100. Damit gibt es hier für mich nur einen Punkt.

  • Diese Aufgabe hat mich am längsten beschäftigt und ich bin nach wie vor unsicher, ob meine Lösung stimmt.

    Bezüglich der Größenordnung bin ich auf ein ähnliches Ergebnis wie die Vorredner gekommen.

    Dennoch mag ich mich der hier geführten Argumentation (noch) nicht anschließen.


    "Komplett" symmetrisch ist die Sache nicht, denn Frosch Fridolin soll die Null erst nach Kröte Kriemhilde erreichen. Er muss also zumindest 2 Sekunden und darf maximal ca 16 h länger als sie brauchen.

    Ein spannender Grenzfall liegt demnach z.B. vor, wenn Kriemhilde die Null zwei oder drei Sekunden vor Tagesende erreicht. Dass die Wahrscheinlichkeit für Fridolin in diesem Fall genau zwei Sekunden später anzukommen genau 0,5 betragen soll, kann ich so noch nicht nachvollziehen. Meines Erachtens müsste p<0,5 sein.


    Meine Rechenlösung lässt mich sogar vermuten, dass Fridolins Wahrscheinlichkeit nach Kriemhilde anzukommen insgesamt nur 1/3 beträgt.

    Leider fehlt mir das mathematische Rüstzeug, diese Behauptung zu beweisen und Rundungsfehler auszuschließen.

    Von der Größenordnung her liegen p=1/3 und p=0,5 glücklicherweise im gleichen Intervall (0,256 < p<= 0,512) .


    Ich hoffe auf weitere Beiträge hier und bin sehr gespannt, wie die Musterlösung aussieht.

  • Ich hatte die gleichen Überlegungen wie pierrot: Die bedingten Wahrscheinlichkeitsverteilungen für die Ankunftszeit (gegeben, dass sie überhaupt im Laufe des Tages die 0 erreichen und dies nicht gleichzeitig tun) sind für Fridolin und Kriemhilde genau gleich. Da die Verteilungen außerdem unabhängig sind, hat jeder der beiden die gleiche Wahrscheinlichkeit, als erster anzukommen. Daraus folgt p = 0,5.


    Aber die Aufteilung des Intervalls nach 2er-Potenzen ist schön irreführend.

  • Ich verwende die (unbekannten) Sprungreihenfolgen S_1 und S_2, mit der Friedolin und Kriemhilde jeweils zur Mitte kommen. Das solche Reihenfolgen existieren ist durch die Aufgabenstellung vorgegeben. Statt links/rechts verwende ich mitte/außen.


    Etwas rechnen zeigt P(S_1 gehört zu Friedolin und S_2 gehört zu Kriemhilde) = P(S_2 gehört zu Friedolin und S_1 gehört zu Kriemhilde).

    Das zeigt die Symmetrie und damit p = 0,5

  • Meine Begründung lautet einfach:


    Alle gespiegelten Pfade die zur 0 führen unterscheiden sich für die beiden um den Faktor 2^100. Wenn aber sicher ist, dass beide die 0 erreicht haben, kann man den Faktor ignorieren, also 50%.


    Mir ist nicht klar, wieso das gelten soll. Die Info, dass Kriemhilde und Fridolin nicht zur gleichen Zeit bei der Null ankommen, sorgt m.E. dafür, dass die Verteilungen voneinander abhängen.


    Zeichne dir einfach mal ein paar Pfade auf, die zur 0 führen (nicht für 100 Sprünge, sondern für n=3, 4 oder 5), und zwar immer zu einem Pfad von Fridolin auch den gespiegelten Pfad von Kriemhilde. Dann siehst du, dass insgesamt immer bei Kriemhilde der Faktor 0.5^n dazukommt.

  • Das nicht zur gleichen Zeit musste da nur stehen, damit auch 1/2 rauskommt. Ansonsten hätte man ja erst die W. benötigt, dass sie nicht gleichzeitig ankommen und davon die Hälfte nehmen müssen. Durch den Kunstgriff fallen alle Rechnungen weg.

  • Mir ist nicht klar, wieso das gelten soll. Die Info, dass Kriemhilde und Fridolin nicht zur gleichen Zeit bei der Null ankommen, sorgt m.E. dafür, dass die Verteilungen voneinander abhängen.

    Man nimmt erst nur die Bedingungen, dass beide an dem Tag noch die 0 erreichen. Dann sind die Wahrscheinlichkeiten noch unabhängig, man kann also für die gemeinsame Verteilung (Friedolin erreicht die 0 nach k Sekunden, Kriemhild nach l Sekunden) die Produktverteilung nehmen. Dann erst betrachtet man die bedingte Verteilung mit der Bedingung dass die Ankunftszeiten verschieden sind.

  • Ich habe eine Lösung auf Papier versucht. Ich bin zwar auf interessante Fakten gestoßen, aber leider nicht auf einen Lösungsnachweis. Letztendlich habe ich es dann simuliert. Dabei war es unumgänglich, die 100 auf etwas kleineres zu reduzieren, denn sonst erreicht Kriemhilde fast nie das Ziel und man kann die Lösung verwerfen. Ebenso habe ich die 16h etwas eingekürzt (auf wenige Sekunden), da die Zeit hier komplett willkürlich gewählt ist und die Lösung nicht verändert. Es reicht, eine Zahl zu nehmen, die groß genug ist, um das Ergebnis stabil auf einem Wert zu halten.

    Man muss ein wenig darauf achten, dass man neben den günstigen Fällen auch diejenigen Fälle nicht mit in die Gesamtmenge zählt, die nicht die gestellten Bedingungen erfüllen (beide müssen es schaffen, nicht gleichzeitige Ankunft).

    Letztendlich fällt aber auf, dass - egal wie weit die beiden von der 0 entfernt sind - die Wahrscheinlichkeit immer 0,5 ist.


    Quellcode kommt hier. x ist Fridolin, y ist Kriemhilde ('tschuldigung für die schlechte Variablenbezeichnung). Beide stehen auf -2 bzw. 2, Zeitspanne sind 8 Sekunden (weil es ausreicht. Das Ergebnis ändert sich nicht, wenn man sie länger spingen lässt).

    Dieser Beitrag wurde bereits 2 Mal editiert, zuletzt von DrEGZo () aus folgendem Grund: Kommentierung im Code ergänzt

  • Also ich hab mir das folgendermaßen überlegt:


    Zur Vereinfachung spiegle ich K, sodass beide auf der 100 starten, F springt mit Wk 2/3 Richtung Null, K springt dann mit Wk 1/3 Richtung Null.

    Unter der Bedingung, dass beide die Null im Laufe des Tages erreichen, aber nicht gleichzeitig, jedoch gleichzeitig starten, gibt es nun eine positive Zahl k, bei der sie zum letzten Mal gleichzeitig sind. Danach springen beide in unterschiedliche Richtungen, es geht einer der beiden "in Führung" (näher zur Null, während der andere sich entfernt) und erreicht irgendwann als erster die Null, da sie sich ja davor nicht mehr treffen, also nicht mehr gleichzeitig auf einem Feld landen.

    Betrachten wir nun diesen Punkt, an dem einer der beiden "in Führung" geht.

    Mit Wk 4/9=2/3*2/3 ist dies F (F zur Null, K weg), mit Wk 1/9=1/3*1/3 ist es K (K zur Null, F weg, das möchten wir). Da wir wissen, dass dies die einzigen Möglichkeiten sind, weil sie auf jeden Fall in unterschiedliche Richtungen springen (sonst wären sie nicht zum letzten Mal gleichzeitig auf einer Zahl gewesen), ist die gesuchte Wk die, dass K zur Null springt und F weg, also 1/9, unter der Bedingung, dass beide in unterschiedliche Richtungen springen, was ja mit Wk 1/9+4/9=5/9 passiert. Somit also p=(1/9)/(5/9) = 1/5 = 0,2.


    Kann mir jemand meinen Denkfehler erklären?

    Ich habe die Symmetrie in der Aufgabe noch nicht wirklich gesehen oder verstanden.

  • Ich bin auch nicht auf irgendeine Symmetrie gekommen, also hab ich programmiert.

    Ich wollte wollte aber nicht nur endlich viele Versuche simulieren um doofe Zufälle auszuschließen.

    Daher habe ich eine Art nichtdeterministischen Endlichen Automaten geschrieben:

    Zwei dictionaries beinhalten in jeder Sekunde die Wahrscheinlichkeiten dass F bzw K auf der entsprechenden Zahl ist.

    Also zB [10:0.5 ; 15:0.5] heißt dass F zu je 50% auf den Zahlen 10 und 15 ist.

    Dann hab ich 16h hüpfen simuliert und gezählt wie wahrscheinlich K vor F ankommt.

    (weil K gegen negativ unendlich läuft hab ich bei -16*60*30 abgeschnitten, von da aus ist 0 unerreichbar).

    Das Ergebnis war ca. 0.51, also wahrscheinlich nur ein paar Rundungsfehler von der 0.5 weg :)

    Laufzeit war im 10-20min Bereich.

    Quellcode kann ich erst in ein paar Tagen zeigen falls es wen interessiert.