Schachbrettlabyrinth

Neue Frage »

leoclid Auf diesen Beitrag antworten »
Schachbrettlabyrinth
Ich habe heute mal ein kniffliges Rätsel für euch. (Oder übersehe ich eine einfache Lösung??))


Anja spielt das Spiel Schachbrettlabyrinth.
Gegeben sei ein Schachbrett mit 10*10 Feldern.
Jedes Feld wird auf zufällige Weise in genau einer der drei Farben rot, blau oder grün eingefärbt.
Anjas Spielfigur steht zu Beginn auf dem Feld in der linken oberen Ecke.

Ein Spielzug besteht darin, dass Anja ihre Spielfigur vom aktuellen Feld auf ein waagrecht oder senkrecht (nicht diagonal) angrenzendes Feld rückt. Dabei gilt aber folgende Regel:
Von einem roten Feld darf sie nur auf ein blaues Feld rücken,
Von einem blauen Feld darf sie nur auf ein grünes Feld rücken.
Von einem grünen Geld darf sie nur auf ein rotes Feld rücken.

Berechne die Wahrscheinlichkeit, dass Anja in endlich vielen Spielzügen das Feld in der rechten unteren Ecke erreichen kann.


Wer Lust hat, kann das Rätsel ja auch im Allgemeinen lösen, statt einem 10*10 Schachbrett haben wir dann ein m*n Schachbrett und statt 3 Farben x Farben.
HAL 9000 Auf diesen Beitrag antworten »

Wenn man sonst keine Idee hat, kann man es ja mal mit Simulation versuchen. Augenzwinkern
Helferlein Auf diesen Beitrag antworten »

Da das ganze im Rätselbereich steht, wird leoclid die Antwort sicher kennen Augenzwinkern
HAL 9000 Auf diesen Beitrag antworten »

Nach dieser Anmerkung

Zitat:
Original von leoclid
(Oder übersehe ich eine einfache Lösung??))

habe ich da so meine Zweifel. Augenzwinkern
Helferlein Auf diesen Beitrag antworten »

Nicht nur Du, aber ich lasse das noch mal offen, bis er es bestätigt oder widerlegt.
Dopap Auf diesen Beitrag antworten »

was ist nun der Wortsinn der letzten beiden Posts ? an was wird gezweifelt.?
 
 
Helferlein Auf diesen Beitrag antworten »

@Dopap: Ein Posting im Rätselforum setzt voraus, dass der Fragesteller die Antwort auf das Rätsel kennt (Vergleiche Rätselregeln).
Und genau das bezweifeln HAL und ich bei leoclid.

Die Frage gehört also vermutlich in ein anderes Unterforum. Aufklärung kann hier aber nur leoclid bringen.
Dopap Auf diesen Beitrag antworten »

Zitat:
Original von Helferlein
[...] Ein Posting im Rätselforum setzt voraus, dass der Fragesteller die Antwort auf das Rätsel kennt.


das war mir schon bekannt! Habe selbst schon Rätsel gepostet.

Aber jetzt ist ja alles klar.
HAL 9000 Auf diesen Beitrag antworten »

Gestützt auf eine inzwischen durchgeführte eigene Simulation stelle ich mal im Günther-Jauch-Schema folgende Testfrage Die gesuchte Wahrscheinlichkeit

(A) ist größer als 1%,
(B) liegt zwischen 0.1% und 1%,
(C) liegt zwischen 0.01% und 0.1%, oder
(D) ist kleiner als 0.01% .
leoclid Auf diesen Beitrag antworten »

Könnte ein Moderator das Thema verschieben???
Sorry, aber hatte das mit der Rätselpostregel nicht mehr in Erinnerung.

Übrigens, die Wahrscheinlichkeit ist aufjedenfall größer als 0.0000047431 %
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von leoclid
Übrigens, die Wahrscheinlichkeit ist aufjedenfall größer als 0.0000047431 %

Stimmt - auf Basis welcher Abschätzung kommst du auf dieses Resultat? (EDIT: Ich kann's mir denken entlang der Hauptdiagonale - aber da hast du dich um Eins verzählt, denn das liefert bereits . Augenzwinkern )

-------------------

Zum Simulationsergebnis: Erfolge bei Wiederholungen. Das ergibt eine Schätzung von bzw. ein -Konfidenzintervall (d.h. 99.5% Sicherheit) von .
leoclid Auf diesen Beitrag antworten »

Ich komme auf diese Abschätzung über vollständige Induktion:

Wir betrachten zunächst ein 2*2 Schachbrett.

Hier gibt es einen Weg durch das Labyrinth, wenn die Färbung folgendermaßen aussieht

12
23

12
33

12
13

11
23

13
23

Oder einer der zyklischen Vertauschungen dieser Einfärbungen. Insgesamt gibt es also 5*3=15 Möglichkeiten. Insgesamt gibt es bei einem 2*2 Schachbrett aber 81 Einfärbungen, was bei einem 2*2 Schachbrett eine Wahrscheinlichkeit von p(A)=15/81 = 5/27 macht.


Angenommen wir haben nun ein n*n Schachbrett mit n>1. Die Wahrscheinlichkeit, dass es einen Weg durch dieses Labyrinth gibt bezeichnen wir mit p(B). Wir erweitern nun das Schachbrett zu einem (n+1)*(n+1) Schachbrett. Die Wahrscheinlichkeit, dass es hier einen Weg vom Feld in der ersten Spalte/erste Zeile zum Feld in der nten Spalte / nten Zeile gibt beträgt p(B). Wir betrachten nun das Schachbrett, dass die Felder (n)/(n), (n+1)/n, (n)/(n+1) und (n+1)/(n+1) enthält. Da dies ein zweier Schachbrett ist, beträgt die Wahrscheinlichkeit, dass es einen Weg vom Feld (n)/(n) zum Feld (n+1)/(n+1) gibt p(A). Insgesamt ist also die Wahrscheinlichkeit, dass es es vom Feld in der linken oberen Ecke einen Weg gibt, der zum Feld in der rechten unteren Ecke gibt, größer als p(A)*p(B), da wir ja nur die Wahrscheinlichkeit für einen speziellen Weg ausgerechnet haben.

Wenn wir von einem 2*2 Schachbrett zu einem 10*10 Schachbrett übergehen, führen wir
2>3
3>4
4>5
5>6
6>7
7>8
8>9
9>10

8 Vergrößerungsschritte durch.

Insgesamt ist die Wahrscheinlichkeit für einen Weg vom linken oberen Feld zum rechten unteren Feld größer als

(5/27)*(5/27)^8= 2.56127471*10^(-7) entspricht 0.00002561274 %
HAL 9000 Auf diesen Beitrag antworten »

Ja, ich hatte es mir inzwischen selber zusammengereimt (siehe EDIT).
leoclid Auf diesen Beitrag antworten »

Ich hatte deinen Edit nicht bemerkt, bzw. meinen Beitrag währenddessen geschrieben.

Aber diese Abschätzung ist eben nur eine Abschätzung.

Mich würde interessieren, ob es eine Möglichkeit gibt, die Wahrscheinlichkeit mathematisch exakt zu berechnen.

Ich hätte dazu zwei Ideen:

Idee 1: Die 3^(100) Möglichen Einfärbungen des Schachbretts auf verschiedene Arten von Einfärbungen zurückzuführen, für die man sehr leicht die Wahrscheinlichkeit berechnen kann.

Idee 2: Das Spiel mit vollständiger Induktion noch weitertreiben, allerdings brauch man dazu wahrscheinlich auch unzählige Fallunterscheidungen.
HAL 9000 Auf diesen Beitrag antworten »

Ja, versuchen kannst du es, keine Frage.

Zitat:
Original von leoclid
Idee 2: Das Spiel mit vollständiger Induktion noch weitertreiben, allerdings brauch man dazu wahrscheinlich auch unzählige Fallunterscheidungen.

Ich hatte es auch kurz erwogen, etwa so: Man kann im ersten Schritt nach rechts oder nach unten gehen. Leider reduziert sich aber das Spielfeld nach diesem einen Schritt nicht wesentlich, also etwa zu oder , da eine Pfad zum Zielfeld auch wieder "zurück" (also nach links bzw. oben) gehen kann - das macht die Sache hier im Gegensatz zu einigen anderen ähnlichen Problemen so unheimlich schwer.

Deswegen ja auch mein sofortiger Verweis auf Simulation, da eine erfolgversprechende exakte Berechnung m.E. in weiter Ferne liegt.


Um diese Schwierigkeiten mal im "kleineren" Fall 4x4 zu illustrieren, ein Beispiel:

1 3 3 1
2 1 2 2
3 3 2 3
1 2 2 1


Der kürzeste Pfad umfasst hier sage und schreibe 12 Schritte (bzw. 13 Felder).
leoclid Auf diesen Beitrag antworten »

Ich habs! Tanzen Tanzen

Glaube ich zumindest.
Noch überprüfen ob das mit deinem Simulationsergebnis übereinstimmt, und ich wirklich keinen Fehler gemacht habe und dann JAP!

Ich verrate den Lösungsweg noch nicht, ich lasse euch noch den Spaß und überlegen, wenn es bis Morgen niemand raushat, gibts den ersten Hinweiß.
HAL 9000 Auf diesen Beitrag antworten »

Na dann hoffe ich mal, dass du nicht zu früh feierst.

Zur Kontrolle mal das kleinere 4x4-Feld: Dort ist die gesuchte Wahrscheinlichkeit exakt .

Oder das 3x6-Feld: Dort ist es exakt .

Kommt das mit deiner Methode auch raus? verwirrt
leoclid Auf diesen Beitrag antworten »

Meine Idee war falsch unglücklich
HAL 9000 Auf diesen Beitrag antworten »

Es ist einfach verflucht schwer, hier eine exakte theoretische Rechnung hinzukriegen. Mir ist allenfalls - ähnlich wie bei dir oben - eine rekursive Abschätzung nach unten eingefallen:

Sei die Erfolgswahrscheinlickeit in einem -Rechteck, von links oben nach rechts unten einen Weg unter den genannten Regeln zu finden, dann ist offenbar , wir können also o.B.d.A. betrachten.

Mit Wahrscheinlichkeit 1/3 können wir vom Anfangsfeld einen Schritt nach unten gehen und finden von dort mit einer Wahrscheinlichkeit größer einen Weg zum Ziel. Warum "größer"? Nun, jeder Weg im verbleibenden -Rechteck ist auch ein gangbarer Weg in unserem Ausgangsrechteck, aber nicht umgekehrt: Schließlich kann ein Weg auch die erste Zeile passieren.

Ok, in allen anderen Fällen (2/3) ist der Weg vom Anfangsfeld nach unten versperrt, mit Wahrscheinlichkeit 1/3 aber geht der Weg nach rechts, in diesem Unterfall ist analog die Wahrscheinlichkeit für einen Weg größer als .


Wir haben damit die Abschätzung

für

mit den Startwerten . Das ergibt z.B.

,

was leider fast eine ganze Zehnerpotenz unter dem obigen Simulationswert (ca. 0.00009) ist. Eine untere Abschätzung, gewiss, aber eine nicht sonderlich gute.
leoclid Auf diesen Beitrag antworten »

An sich kann man das Problem schon mathematisch lösen.

Dazu brauch man aber unzählige Fallunterscheidungen, die man mit einem händischen Beweis nicht abhandeln kann.

Und ich glaube ein einfacher Beweis, der mit maximal 2 Seiten auskommt ist nicht möglich.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von leoclid
An sich kann man das Problem schon mathematisch lösen.

Ja sicher, es ist ja schließlich endlich. Aber endlich kann auch sehr, zu groß sein. Es wäre schon eine erstaunliche Leistung, das für mittelgroße Felder wie 10x10 mit Computerhilfe exakt ausrechnen zu können.
leoclid Auf diesen Beitrag antworten »

Man kann höchstens die Anzahl der Möglichkeiten runterrechnen.

So sind es zum Beispiel insgesamt nicht mehr Mögliche Spielfelder, sondern [latex]3^{99} Spielfelder da man die Farben von einem Spielfeld zyklisch vertauschen kann und das somit erhaltene Spielfeld auch einen Weg von oben links nach unten rechts besitzt.

Auf diese Weise kann man bestimmt noch mehr Vereinfachungen machen.
HAL 9000 Auf diesen Beitrag antworten »

Na dann warte ich mal geduldig ab, bis du etwas präsentierst, was etwas konkreter als dieses "bestimmt" ist - damit ich die obigen Ergebnisse der stochastischen Simulation endlich mal vergleichen kann. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen