Wie schwer ist es, Rubiks Würfel zu klettern?

Rubik’s Cube ist seit 40 Jahren eines der beliebtesten Rätsel der Welt. Es wurden verschiedene Methoden entwickelt, um es zu lösen, wie in unzähligen Büchern erklärt. Expert „Speedcubers“ kann es in Sekundenschnelle lösen.

Zusätzlich zu solchen Kunststücken erstaunlicher Geschicklichkeit gibt es viele faszinierende mathematische Fragen im Zusammenhang mit Rubiks Würfel. Eine Bewegung des Würfels besteht darin, eine der sechs Flächen um 90, 180 oder 270 Grad zu drehen. Eine Staffelung 43.252.003.274.489.856.000 mögliche Zustände können durch Anwendung von Sequenzen von Bewegungen auf den gelösten Zustand erhalten werden.

Trotz dieser Komplexität wurde 2010 gezeigt, dass Zauberwürfel unabhängig vom Ausgangszustand immer in 20 Zügen oder weniger gelöst werden können. Diese Zahl wird als „Gotteszahl“ bezeichnet, da alle bekannten Lösungsmethoden, die von Menschen verwendet werden, typischerweise deutlich mehr Züge als diesen optimalen Wert verwenden.

Zauberwürfel im gelösten Zustand. Mike Gonzalez (TheCoffee)

Aber was ist mit der entgegengesetzten Frage: Wie viele Züge sind erforderlich, um einen gelösten Würfel zu lösen? Auf den ersten Blick klingt das nach einer viel einfacheren Frage als die Berechnung der Zahl Gottes. Schließlich erfordert das Scrambling im Gegensatz zum Lösen eines Würfels keinerlei Fähigkeiten.

Ähnliche Fragen wurden für das Kartenmischen erfolgreich beantwortet. Ein berühmtes Beispiel ist die Studie des „Riffle Shuffle“ der Mathematiker Dave Bayer und Perci Diaconis aus dem Jahr 1990. Ein Kartenspiel wird als „gemischt“ definiert, wenn seine Reihenfolge zufällig ist, wobei jede mögliche Reihenfolge die gleiche Wahrscheinlichkeit hat, zu erscheinen. Bayer und Diaconis zeigten, dass sieben Riffelmischungen notwendig und ausreichend sind, um ein Standardspielkartendeck ungefähr zu mischen.

Letztes Jahr veröffentlichten Mathematiker eine ähnliche Studie des 15-Puzzles, das aus einem 4×4-Quadrat besteht, das mit 15 Schiebekacheln und einem leeren Raum gefüllt ist.

Was bedeutet es, dass ein Würfel verschlüsselt wird?

Eine typische Person, die versucht, einen Zauberwürfel zu knacken, würde wiederholt zufällige Züge darauf ausführen. Die resultierende zufällige Folge von Zuständen ist ein Sonderfall dessen, was Mathematiker eine Markov-Kette nennen. Die Schlüsseleigenschaft ist, dass angesichts des aktuellen Zustands die Wahrscheinlichkeit, wie der nächste Zustand aussehen wird, von keinem der vorherigen Zustände abhängt.

Wenn man die Theorie der Markov-Ketten auf das Würfel-Scrambling anwendet, folgt daraus, dass mit zunehmender Anzahl zufälliger Bewegungen die Wahrscheinlichkeit, sich in einem bestimmten der möglichen Zustände zu befinden, immer näher kommt 1/43,252,003,274,489,856,000. Mathematiker nennen dies eine „gleichmäßige Wahrscheinlichkeitsverteilung“, da jeder mögliche Zustand mit der gleichen Wahrscheinlichkeit auftritt.

Nach einer beliebigen Anzahl zufälliger Züge ist der Zustand des Würfels zufällig, aber seine Wahrscheinlichkeitsverteilung ist nicht genau einheitlich.

d(t) beschreibe, wie sehr sich die Wahrscheinlichkeitsverteilung nach t Zufallszügen von der gleichmäßigen Wahrscheinlichkeitsverteilung unterscheidet. Mit zunehmender Anzahl zufälliger Züge (t) nimmt der Wert von d (t) ab. Der Würfel, der verschlüsselt wird, entspricht d (t), das klein ist.

Markov-Kette Monte Carlo

In der Theorie der Markov-Ketten wird diese Abnahme von d(t) als „Mischen“ bezeichnet. Neben Kartenmischen und Puzzle-Scrambling hat die Theorie des Markov-Kettenmischens auch sehr ernsthafte praktische Anwendungen. Eines der wichtigsten Rechenwerkzeuge in der modernen Wissenschaft und Technik ist die Monte-Carlo-Methode. Diese Methode beruht, wie das berühmte Casino, nach dem sie benannt ist, grundsätzlich auf dem Zufall. Im Wesentlichen versucht es, harte mathematische Probleme mit mehreren zufälligen Vermutungen annähernd zu lösen.

In der Praxis werden häufig Markov-Ketten verwendet, um diese Zufallszustände zu erzeugen. Um die Genauigkeit dieser Monte-Carlo-Methoden der Markov-Kette zu verstehen, besteht die Hauptaufgabe darin, abzuschätzen, wie schnell d (t) mit zunehmendem t abnimmt.

Der Pocket Cube

Pocket cube im verschlüsselten Zustand. Mike Gonzalez (TheCoffee)

Das Scrambling-Problem für den Standard-3x3x3-Zauberwürfel zu untersuchen, ist derzeit eine faszinierende ungelöste Herausforderung. Es wird jedoch ziemlich überschaubar, wenn wir unsere Aufmerksamkeit auf eine kleinere 2x2x2-Version richten, die als Pocket Cube bezeichnet wird.

In diesem Würfel fehlen die Rand- und Mittelstücke und nur die Eckstücke bleiben übrig. Der Pocket Cube hat nur 3.674.160 mögliche Zustände und seine Gotteszahl ist nur 11.

In der folgenden Grafik zeichnen wir d(t) für den Pocket Cube. Nach 11 Zügen ist d (t) immer noch sehr groß, bei 0,695. Der erste Wert von t, der einen d (t) -Wert unter 0,25 ergibt (in der Markov-Kettentheorie oft als „Mischzeit“ bezeichnet), ist 19. Nach 25 Zügen ist d (t) 0,092; nach 50 Zügen ist es 0,0012; und nach 100 Zügen ist es 0,00000017.

Abstand der Pocket cube Verteilung von uniform nach t bewegt. Eric Zhou

Wie viele Züge sollten Sie also verwenden, um einen Pocket Cube vollständig zu scrambeln? Die Antwort hängt davon ab, wie klein d (t) sein soll. Es ist jedoch sicherlich wahr, dass Gottes Anzahl von Bewegungen unzureichend ist. Als absolutes Minimum sollte man nicht weniger als 19 Züge verwenden. Weitere Details, einschließlich Code zur Berechnung von d (t), finden Sie hier .

Und natürlich, sobald Sie Ihren Würfel verschlüsselt haben, müssen Sie ihn nur noch einmal lösen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.