Würfelschlange

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.

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.

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 ${\displaystyle {\frac {1}{6}}}$ . Also ist die Wahrscheinlichkeit, dass der Zauberkünstler den Würfel des Zuschauers in diesem Schritt verfehlt, höchstens ${\displaystyle {\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 ${\displaystyle \left({\frac {5}{6}}\right)^{50/3.5}}$ . Damit ist die Wahrscheinlichkeit für das Gelingen des Tricks mindestens ${\displaystyle 1-\left({\frac {5}{6}}\right)^{50/3.5}}$ , was etwa 92 % entspricht.

Die Wahrscheinlichkeit für das Gelingen des Tricks lässt sich auch genau ausrechnen. Es ist ${\displaystyle 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

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

oder vereinfacht

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

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

Die verwendeten Matrizen und Vektoren sind

• der Einheitsvektor ${\displaystyle e_{0}}$  mit ${\displaystyle e_{0}^{T}=(1,0,\dots ,0)}$ ,
• der Startvektor ${\displaystyle v}$  mit ${\displaystyle 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 ${\displaystyle M}$  mit ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle {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 ${\displaystyle 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 ${\displaystyle {\frac {1}{6}}}$  in der Matrix ${\displaystyle 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 ${\displaystyle M}$  mit der Wahrscheinlichkeit ${\displaystyle 1}$  eingetragen.

Der Spektralradius der Matrix ${\displaystyle 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.

${\displaystyle 1-1.016919180422709\cdot 0.9083578428^{n}}$ 

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

• http://www.mathematikum-unterwegs.de/index.php?m=2&la=de&id=329
• http://www.bermuma.de/wuerfel.html
• http://gymnasiumkoenigsbrunn.de/mathe-zum-anfassen/articles/wuerfelschlange.html