Würfelschlange

Die Würfelschlange ist ein Experiment des Mathematikums in Gießen, das sich auch als Zaubertrick aufführen lässt.

Ein Zauberkünstler bittet einen Zuschauer, etwa 50 Spielwürfel zu werfen und in einer Reihe aneinanderzulegen, etwa so:

6 4 2 5 3 2 1 6 1 4 4 4 1 3 3 2 6 2 4 1 3 1 1 5 5 5 1 3 6 1 5 6 1 3 5 4 1 3 3 4 5 1 5 1 3 5 4 1 2 1

Der Zuschauer soll sich nun heimlich einen der ersten sechs Würfel aussuchen. Er wählt beispielsweise den zweiten Würfel. Dessen Augenzahl ist 4. Entsprechend dieser Augenzahl soll er auf der Würfelschlange weiterspringen. So gelangt er zum sechsten Würfel mit der Augenzahl 2. Dieses Springen entsprechend der Augenzahl soll der Zuschauer so lange wiederholen, bis er einen Sprung nicht mehr innerhalb der Würfelschlange ausführen kann. Im obigen Beispiel werden die folgenden Würfel nacheinander ausgewählt:

6 4 2 5 3 2 1 6 1 4 4 4 1 3 3 2 6 2 4 1 3 1 1 5 5 5 1 3 6 1 5 6 1 3 5 4 1 3 3 4 5 1 5 1 3 5 4 1 2 1

Der Zaubertrick besteht darin, dass der Zauberkünstler den letzten gewählten Würfel errät. Im Beispiel wäre das der vorletzte Würfel mit der Augenzahl 2.

Auflösung des Tricks

Wie findet der Zauberkünstler den letzten vom Zuschauer gewählten Würfel heraus? Er fängt einfach beim ersten Würfel an und vollführt heimlich Sprünge auf die gleiche Art wie der Zuschauer. Im Beispiel sähe das so aus:

6 4 2 5 3 2 1 6 1 4 4 4 1 3 3 2 6 2 4 1 3 1 1 5 5 5 1 3 6 1 5 6 1 3 5 4 1 3 3 4 5 1 5 1 3 5 4 1 2 1

Bereits beim 8. Würfel trifft der Zauberkünstler auf den Würfel des Zuschauers und von da an wählt er immer die gleichen Würfel wie er.

Berechnung der Wahrscheinlichkeit

Offensichtlich funktioniert der Trick nicht immer. Würfelt der Zuschauer beispielsweise folgende Zahlen

6 6 6 6 6 6 6 6 6 6 6 ...

so kann der Zauberkünstler den letzten gewählten Würfel nur raten, wenn er den ersten gewählten Würfel kennt. Zahlenfolgen, bei denen die Sprungfolgen von Zauberkünstler und Zuschauer nicht zusammenlaufen, sind aber sehr selten.

Abschätzung

Es folgt eine Abschätzung dafür, wie wahrscheinlich der Trick mindestens funktioniert. Dazu berechnet man eine obere Abschätzung dafür, dass der Trick nicht funktioniert. Man greift sich die Situation vor einem Sprung heraus, beispielsweise

6 1 4 4 4 1 3 .

Da Sprünge maximal sechs Würfel umfassen, muss der Zuschauer wenigstens eine der Zahlen 1 4 4 4 1 3 gewählt haben. Die Wahrscheinlichkeit, dass darunter die letzte 3 ist, ist wenigstens ${\frac {1}{6}}$ . Also ist die Wahrscheinlichkeit, dass der Zauberkünstler den Würfel des Zuschauers in diesem Schritt verfehlt, höchstens ${\frac {5}{6}}$ .

Der Zauberkünstler wird im Durchschnitt 50/3.5 Sprünge absolvieren. Also ist die Wahrscheinlichkeit, die Würfel des Zuschauers bei jedem Sprung zu verfehlen, höchstens $\left({\frac {5}{6}}\right)^{50/3.5}$ . Damit ist die Wahrscheinlichkeit für das Gelingen des Tricks mindestens $1-\left({\frac {5}{6}}\right)^{50/3.5}$ , was etwa 92 % entspricht.

Genaue Berechnung

Die Wahrscheinlichkeit für das Gelingen des Tricks lässt sich auch genau ausrechnen. Es ist $e_{0}^{T}\cdot M^{n}\cdot v$ die Wahrscheinlichkeit dafür, dass Zauberkünstler und Zuschauer genau beim (n+1). Würfel aufeinandertreffen (also nicht schon vorher). Die Wahrscheinlichkeit dafür, dass beide bis zum n. Würfel aufeinandertreffen, ist also

e_{0}^{T}\cdot (E+M+\dots +M^{n-1})\cdot v

oder vereinfacht

e_{0}^{T}\cdot (E-M^{n})\cdot (E-M)^{-1}\cdot v

.

Für die Berechnung der Matrixpotenz $M^{n}$ gibt es verschiedene effiziente Verfahren basierend auf Eigenwertzerlegung oder binärer Exponentiation.

Die verwendeten Matrizen und Vektoren sind

der Einheitsvektor $e_{0}$ mit $e_{0}^{T}=(1,0,\dots ,0)$ ,
der Startvektor $v$ mit $v^{T}={\frac {1}{6}}\cdot (1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$ ,
die Übergangsmatrix $M$ mit $M={\frac {1}{6}}\cdot \left({\begin{array}{ccccccccccccccccccccc}0&1&0&0&0&0&6&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&1&1&0&0&0&0&6&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&1&0&1&0&0&0&0&6&0&0&0&0&0&0&0&0&0&0&0&0\\0&1&0&0&1&0&0&0&0&6&0&0&0&0&0&0&0&0&0&0&0\\0&1&0&0&0&1&0&0&0&0&6&0&0&0&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&0&1&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0&0\\0&0&1&1&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0&0\\0&0&1&0&1&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0&0\\0&0&1&0&0&1&0&0&0&0&0&0&0&0&6&0&0&0&0&0&0\\0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&6&0&0&0&0&0\\0&0&0&1&1&0&0&0&0&0&0&0&0&0&0&0&6&0&0&0&0\\0&0&0&1&0&1&0&0&0&0&0&0&0&0&0&0&0&6&0&0&0\\0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&6&0&0\\0&0&0&0&1&1&0&0&0&0&0&0&0&0&0&0&0&0&0&6&0\\0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&6\\0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\end{array}}\right)$ .

Für 50 Würfel erhält man so die Wahrscheinlichkeit 99,17 % für das Gelingen des Tricks.

Die Berechnung funktioniert wie folgt: Man verfolgt, wie Zauberkünstler und Zuschauer simultan die Würfelschlange entlang springen. Man betrachtet einen Abschnitt von 6 aufeinanderfolgenden Würfeln und verschiebt diesen Abschnitt mit jeder Matrixmultiplikation um einen Würfel nach rechts. Der Vektor $M^{n}\cdot v$ beschreibt den Abschnitt vom (n+1). zum (n+6). Würfel. In diesem Vektor ist für jede mögliche Position von Zauberkünstler und Zuschauer ein Element enthalten, wobei Zauberkünstler und Zuschauer nicht unterschieden werden. Deswegen hat der Vektor ${7 \choose 2}$ (Binomialkoeffizient) Elemente, also 21. Im Vektor sind die möglichen Paare lexikographisch sortiert angeordnet.

Wenn einer der Teilnehmer genau am Beginn des Abschnitts steht, darf er einmal würfeln und den entsprechenden Sprung ausführen. In der Matrix $M$ sind alle möglichen Übergänge mit ihrer Wahrscheinlichkeit verzeichnet. Es gibt zwei Fälle:

Einer der Teilnehmer steht am Beginn des Abschnitts und würfelt. Es gibt 6 verschiedene Möglichkeiten für eine neue Konstellation. Dieser Fall ist mit den Übergangswahrscheinlichkeiten ${\frac {1}{6}}$ in der Matrix $M$ verzeichnet.
Keiner der Teilnehmer steht am Beginn eines Abschnitts. Relativ zum Abschnittbeginn rutschen beide Teilnehmer um eine Position nach links. Diese Fälle sind in die Matrix $M$ mit der Wahrscheinlichkeit $1$ eingetragen.

Genauere Abschätzung

Der Spektralradius der Matrix $M$ ist ungefähr 0.9083578428. Auf diese Weise erhält man eine sehr gute Näherung für die Wahrscheinlichkeit für das Gelingen des Tricks, die umso besser wird, je mehr Würfel man verwendet.

1-1.016919180422709\cdot 0.9083578428^{n}

Siehe auch

Kruskals Kartentrick: Ein sehr ähnlicher Trick mit Karten, aber weit schwierigerer Analyse der Wahrscheinlichkeiten

Weblinks

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.