Unterabschnitte

• Der $3 \times 3$-Würfel
• Der 4x4 Würfel

Projektarbeit

Um sich bei der Projektarbeit problemlos miteinander verständigen zu können, haben wir folgende Notation vereinbart. Wir denken uns den Würfel auf der Hand vor uns liegend und bezeichnen die Ansichten des Würfels mit

$$l=$$left$$, \quad r=$$rigth$$, \quad f=$$front$$, \quad b=$$back$$, \quad u=$$up$$, \quad d=$$down

Unter einem Elementarzug verstehen wir im Folgenden eine Drehung der entsprechenden Scheibe im Uhrzeigersinn um $90^\circ$. Sie werden in Anlehnung an die Ansichten mit $L$, $R$, $F$, $B$, $U$, $D$ bezeichnet. Beim $4 \times 4$- bzw. $5 \times 5$-Würfel werden für die zweiten Scheiben analog folgende Abkürzungen festgelegt: $L_2$, $R_2$, $F_2$, $B_2$, $U_2$, $D_2$. Die Mittelscheiben werden je nach Ansicht $M_L$, $M_R$, $M_F$, $M_B$, $M_U$, $M_D$ benannt.

Diese Bezeichnungen wurden auch in einem Simulationsprogramm (dankenswerterweise von Werner Knoben programmiert) verwendet. Diesem Programm werden unsere Nerven ewig dankbar sein, denn mit einem einfachen Befehl konnten die Würfel problemlos in den Ausgangszustand, an dem man die erarbeiteten Züge besser erkennen kann, gebracht werden.

Wir weichen im Folgenden von der zuvor getroffenen Konvention ab und führen die Zugfolgen von links nach rechts durch, also beispielsweise in $RF$ führen wir zuerst den Elementarzug $R$ und dann $F$ durch.

Der $3 \times 3$-Würfel

Eckkubies des $\mathbf{3 \times 3}$-Würfels

Kerstin Bauer, Mélanie Neises, Anja von Olnhausen, Miriam Schneider

Sonntag Nachmittag. Die Gruppenarbeit beginnt. Wir sind die ,,Eckgruppe`` des $3 \times 3$-Würfels. Nach Erhalt unserer Aufgabenstellung sind wir erstmal erleichtert, weil es ziemlich einfach aussieht. Gut, fangen wir an! Das Computerprogramm ist eigentlich recht leicht zu verstehen. Jetzt gilt es nur noch auszuprobieren!

Nach einigem erfolglosem Herumdrehen kommen wir endlich auf die Idee, etwas unserer erlernten mathematischen Kenntnisse anzuwenden, den Kommutator. Diese Zugfolge ist hilfreich, da sie nur vier Ecken vertauscht und den Rest unverändert lässt. Unsere Aufgabe 1 ist jedoch, nur drei Ecken zu vertauschen. Schade!

Bis Sonntag Abend haben wir also noch kein Ergebnis. Am nächsten Tag setzen wir uns voller Elan vor den Computer und probieren weiter aus. Nur nicht die Geduld verlieren! Am Dienstag Morgen kommt uns endlich die Erleuchtung: Die Zugfolge $Z_1$ bewirkt die Vertauschung dreier Eckkubies mit gleichzeitiger Änderung der Orientierung zweier Eckkubies.

$Z_1=R^{-1}\, F^{-1}\, L^{-1}\, F\, R\, F^{-1}\, L\, F$

Die zweite Aufgabe stellte uns vor das Problem, drei Eckkubies zu vertauschen, ohne ihre Orientierung zu ändern (Zugfolge $Z_2$). Zur Lösung dieses Problems verwendeten wir die Zugfolge $Z_1$ aus Aufgabe 1 und eine weitere Zugfolge $Z_0$.

$$\begin{array}{r@{\;}c@{\;}l} Z_0&=&[R,F^{-1}]^2 \\ Z_2&=&Z_1\, Z_0\, U\, Z_0^2 \, U^{-1} \end{array}$$

In Problem 3 sollten wir nur die Orientierung zweier Eckkubies realisieren (Zugfolge $Z_3$). Dies lösten wir mit Hilfe der Zugfolge $Z_0$:

$Z_3=Z_0 \, U \, Z_0^2\, U^{-1}$

In Problem 4 sollten wir Problem 3 mit weniger als 33 Elementarzügen lösen. Doch mit Erstaunen stellten wir fest, dass wir diese Aufgabe bereits mit $Z_3$ gelöst hatten.

Eine weitere Aufgabe war, einen Algorithmus zu entwickeln, der mit Hilfe der Zugfolge 1 und einem weiteren Zug alle Eckkubies in ihr korrektes Kubizil bringt, (wobei wir davon ausgehen, dass der Würfel lösbar ist):

Durch Durchführung der Zugfolge $Z_1$ auf den seitlichen Ebenen bringt man alle Kubies in die Ebene, wo sich ihr korrektes Kubizil befindet. Man betrachtet nun die obere Ebene. Sind alle vier Eckkubies falsch, führt man $Z_1$ einmal, bzw. maximal zweimal durch, so dass ein Eckkubie richtig ist. Anschließend führt man mit den anderen drei Eckkubies die Zugfolge $Z_1$ nochmals einmal, bzw. zweimal durch, sodass auch diese ihr richtiges Kubizil einnehmen. Ist zu Beginn bereits ein Eckkubie richtig, wendet man gleich die Zugfolge $Z_1$ auf die anderen drei Eckkubies ein- bzw. zweimal an. Mit der unteren Ebene verfährt man ebenso.

Die folgende Aufgabe geht davon aus, dass alle Kantenkubies in ihren richtigen Positionen sind und diese nicht verändert werden dürfen. Ist es immer möglich, mit Hilfe der Zugfolge $Z_1$ alle Eckkubies in ihre korrekten Kubizile zu bringen?

Man fasst die Ausgangsposition des Würfels als Permutation der Eckkubies zu ihren Kubizilen auf (die Kantenkubies seien bereits in ihren richtigen Kubizilen). Ist diese Permutation gerade (Signum ist $1$), ist der Würfel lösbar. Ist die Permutation ungerade (Signum ist $-1$), ist der Würfel nicht lösbar. Die Zugfolge $Z_1$ ist ein $3$-Zykel, also ist das Signum $1$. Verknüpft man mehrere $3$-Zykeln, so erhält man wieder eine Permutation mit Signum $1$. Also kann man den Würfel lösen, wenn die Ausgangspermutation gerade ist.

In der letzten Aufgabe sollten wir ein Kriterium entwickeln, nach welchem man entscheiden kann, ob man alle Eckkubies mit Hilfe von $Z_3$ richtig orientieren kann, wobei die Eckkubies sich bereits in ihrem richtigen Kubizil befinden und die Kantenkubies nicht verändert werden dürfen.

Sei $r$ die Summe aller Rechtsdrehungen, die benötigt wird, um alle Eckkubies in ihre richtige Orientierung zu bringen. Bei einem Zug $Z_3$ führt man genau eine Rechtsdrehung eines Eckkubies und eine Linksdrehung eines Eckkubies aus. Da eine Linksdrehung zwei Rechtsdrehungen entspricht, führt man bei jedem Zug drei Rechtsdrehungen durch. Jeder Zug ändert die Orientierung immer nur um ein Vielfaches von drei. Also kann man nur dann alle Kubies richtig orientieren, wenn $r$ ein Vielfaches von drei ist, denn die Orientierung aller Eckkubies ist nur bei $r=0$ richtig.

Im Folgenden gehen wir davon aus, dass die Kantenkubies im richtigen Kubizil und richtig orientiert sind. Nun muss noch gezeigt werden, dass der Würfel immer lösbar ist, wenn das Kriterium 2 erfüllt ist.

Schritt 1: Ecke 8 wird mit Hilfe von Ecke 7 richtig orientiert.
Schritt 2: Ecke 7 wird mit Hilfe von Ecke 6 richtig orientiert.
Schritt 3: Ecke 4 und 5 werden mit Hilfe von Ecke 1 richtig orientiert.
Schritt 4: Ecke 3 und 6 werden mit Hilfe von Ecke 2 richtig orientiert.

Nun stimmen alle Ecken bis auf die Ecken 1 und 2. Bei ihnen gilt nach Kriterium 2, dass die Summe der benötigten Rechtsdrehungen 0 oder $3$ ist (höhere Zahlen kommen bei zwei falsch orientierten Ecken nicht vor).

Fall 1: Ecke 1 und Ecke 2 sind richtig orientiert.
Fall 2: Ecke 1 braucht eine Rechtsdrehung und Ecke 2 braucht zwei Rechtsdrehungen. Führt man $Z_3$ zweimal durch, so sind beide Ecken richtig orientiert.

Fall 3: Ecke 1 braucht zwei Rechtsdrehungen und Ecke 2 braucht eine Rechtsdrehung. Führt man $Z_3$ einmal durch, so sind beide Ecken richtig orientiert.

Also können alle Ecken richtig orientiert werden, wenn Kriterium 2 erfüllt ist.

In der nächsten Aufgabe sollten wir zeigen, dass Kriterium 2 auch für die Zugfolgen $Z_1$ und $Z_2$ gilt. Bei $Z_2$ erfolgt gar keine Orientierungsänderung, deshalb erfüllt diese Zugfolge das Kriterium. Bei der Zugfolge $Z_1$ ändert sich bei einem Eckkubie die Orientierung um eine Drehung nach rechts, beim zweiten Eckkubie um zwei Drehungen nach rechts und beim 3. Eckkubie ändert sich die Orientierung überhaupt nicht. Also ist die Gesamtorientierungsänderung ,,drei`` und die Zugfolge entspricht somit Kriterium 2.

Kantenkubies des $\mathbf{3 \times 3}$-Rubik-Würfels

Sophia Börner, Daniel de Jong, Christoph Lehmann, Stefan Walter

In diesem Abschnitt wollen wir näher auf die Kantenkubies des $3 \times 3$-Rubik-Würfels eingehen. Ziel soll es sein, Kriterien für die Lösbarkeit des Würfels aufzustellen sowie geeignete Lösungsalgorithmen vorzustellen.

Im folgenden werden wir dazu zunächst zwei wichtige Zugfolgen definieren, die für das weitere Vorgehen essentiell sind. Im Anschluss daran werden wir anhand dieser Zugfolgen Schlüsse auf die Lösbarkeit ziehen.

Zugfolgen

Wie im vorigen Abschnitt bereits angedeutet, definieren wir nun zwei wichtige Zugfolgen, mit denen im weiteren Verlauf gearbeitet wird.

$$\begin{array}{r@{\;}c@{\;}l} Z_1 &=& L \, R^{-1} F \,L^{-1} R \,U^2 L \,R^{-1} F \,L^{-1} R \end{array}$$

Durch die Zugfolge $Z_1$ erreichen wir das Vertauschen dreier Kantenkubies, wobei sich bei zwei Kubies gleichzeitig die Orientierung ändert.

Die Zugfolge $Z_2$ bewirkt die Orientierungsänderung zweier Kantenkubies. Dabei verharren alle Kubies in ihrem Kubizil.

$$\begin{array}{r@{\;}c@{\;}l} Z_2 &=& [U , (R \, M_D)^4]\\ &=& U \, (R \, M_D)^4 \,U^{-1} \,(R \,M_D)^{-4} \end{array}$$

Platzierung der Kantenkubis

Wir wollen nun darstellen, wann man bei einem durchmischten Würfel (unter einem durchmischten Würfel verstehen wir hier alle möglichen Permutationen, wobei diese nicht immer durch Zugfolgen erreicht werden müssen) die Kantenkubies mit Hilfe der Zugfolge $Z_1$ in ihr richtiges Kubizil bringen kann, ohne die Eckkubies zu verändern. Die Orientierung der Kantenkubies lassen wir dabei außer Acht. Wir unterscheiden zwei Fälle: Es gibt a) eine gerade, b) eine ungerade Anzahl von Transpositionen ($2$-Zykeln).

Da die Zugfolge $Z_1$ ein $3$-Zykel ist, somit also eine gerade Permutation, folgt: Die Kantenkubies in einem durchmischten Würfel lassen sich durch die Zugfolge $Z_1$ nur bei einer geraden Anzahl von Transpositionen in ihr richtiges Kubizil bringen, wenn die Eckkubies nicht verändert werden sollen (gerades Signum der Permutation). Darf man aber die Eckkubies verändern, so kann man durch Einfügen eines Elementarzuges auch ungerade Permutationen lösen, denn durch den Elementarzug führen wir einen $4$-Zykel, den man wiederum durch drei Transpositionen darstellen kann, durch. Zwei ungerade Anzahlen von Transpositionen ergeben durch Hintereinanderführung eine gerade Anzahl.

Folgender Algorithmus zeigt, wie man alle Kantenkubies mit Hilfe der Zugfolge $Z_1$ an die richtige Stelle bringen kann. Man betrachtet zuerst die Oberseite des Würfels und kontrolliert, ob die Kantenkubies, die in diese Ebene gehören, schon vorhanden sind. Wenn dies nicht der Fall ist, lassen sich durch Anwendung der Zugfolge $Z_1$ auf die Seiten die falsch platzierten Kantenkubies mit den richtigen austauschen. Gegebenenfalls muss man dies durch Elementarzüge der oberen und unteren Scheibe unterstützen. Man kann nun mit der Zugfolge $Z_1$ auf der oberen Ebene die Kantenkubies noch an ihren richtigen Ort tauschen. Mit dem selben Verfahren kann man die untere Ebene vervollständigen (der Würfel sollte dabei gewendet werden). Da immer nur drei Kantenkubies vertauscht werden, bringt man die schon fertige Ebene nicht mehr durcheinander. Man muss jedoch darauf achten, dass nun auch schon die Kantenkubies der Seite in die farblich richtige Reihenfolge gebracht werden.

Orientierung der Kantenkubies

Im folgenden wollen wir zeigen, wann die in ihrem richtigen Kubizil befindlichem Kantenkubies mit Hilfe der Zugfolge $Z_2$ richtig orientiert werden können.

Wir unterscheiden zwei Fälle: Es gibt a) eine gerade, b) eine ungerade Anzahl an falsch orientierten Kantenkubies.

Beim ersten Fall müssen wir zeigen, dass sich zwei beliebige falsch orientierte Kantenkubies richtig orientieren lassen. Sind beide benachbart, so ist der Nachweis trivial.

Wie wir wissen, lässt sich mit der Zugfolge $Z_2$ die Orientierung zweier benachbarter Kantenkubies ändern. Sind nun zwei nicht benachbarte Kantenkubies falsch orientiert, so kann man durch mehrfaches Anwenden der Zugfolge $Z_2$ auch diese wieder richtig orientieren. Eines der beiden Kubies wird richtig orientiert. Dadurch bekommt ein anderes automatisch eine falsche Orientierung. Dies lässt sich fortführen, bis die zwei falsch orientierten Kubies benachbart sind. Ein letztes Durchführen der Zugfolge $Z_2$ bringt nun diese beiden Kantenkubies in ihre richtige Orientierung. Sind vier, sechs, oder mehr gerade Kantenkubies falsch orientiert, kann man dieses Prinzip ohne weiteres übertragen.

Im zweiten Fall müssen wir nur den Fall eines falsch orientierten Kantenkubies betrachten. Ein einzelnes Kantenkubie können wir aber durch Z2 nie richtig orientieren, da immer ein schon richtig orientierter Kantenkubie wieder verdreht wird und wir nach dem Zug wieder genau einen falsch orientierten Kantenkubie haben. Somit lassen sich eine ungerade Anzahl von falsch orientierten Kantenkubies nie richtig drehen.

Somit lässt sich folgendes Lösungskriterium formulieren:

Satz 40  

Wenn man von einer richtigen Platzierung aller Kubies und zusätzlich von der richtigen Orientierung der Eckkubies ausgeht, ist der Würfel genau dann lösbar, wenn eine gerade Anzahl von falsch orientierten Kantenkubies vorliegt.

Beweis:

In eine Richtung haben wir das Kriterium soeben bewiesen. Nun ist noch folgende Richtung zu zeigen: Wenn der Würfel lösbar ist, ist eine gerade Anzahl von Würfeln falsch orientiert.

Betrachtet man einen Würfel von oben, so lassen sich die Farborientierungen der Kantenkubies folgendermaßen beschreiben: Man betrachtet die Farborientierung auf den von oben gesehenen Mittelebenen im Uhrzeigersinn. Dadurch hat jedes Kantenkubie eine bestimmte Orientierung der Farben. Dreht man nun die obere Scheibe einmal, so ändert sich bei zweien diese Orientierung. Somit ändert sich bei jedem Elementarzug immer die Orientierung von zwei Kantenkubies. Werden verschiedene Elementarzüge hintereinander ausgeführt, erhält man in jedem Fall eine gerade Anzahl an anders orientierten Kantenkubies. Da der Würfel lösbar ist, muss er durch Hintereinanderausführung von Elementarzügen in den Ausgangszustand zurückzuführen sein. Im Ausgangszustand haben alle Kantenkubies (also eine gerade Anzahl) die richtige Orientierung. Da man bei jeder Hintereinanderausführung von Elementarzügen eine gerade Anzahl von Kantenkubies anders orientiert, darf bei jeder lösbaren Permutation nur eine gerade Anzahl von Kantenkubies falsch orientiert sein. Somit ist also das Kriterium in beide Richtungen gültig. $\Box$

Zusammenhang zwischen Eck- und Kantenkubies

Kerstin Bauer, Anja von Olnhausen, Melanie Neises, Miriam Schneider

Für die weiteren Aufgaben haben wir uns in den beiden Projektgruppen zum $3 \times 3$-Würfel zusammengesetzt und einen Zusammenhang zwischen den Kanten- und den Eckkubies gefunden und als Lösungskriterium formuliert.

Satz 41   Wenn man von der Orientierung absieht, ist der Würfel genau dann lösbar, wenn das Signum der Permutationen der Kanten- und Eckkubies gleich ist.

Beweis:

Eine Richtung des Satzes haben wir schon gezeigt. Sind beide Signa gleich 1, können wir einfach die Plazierungszüge wie beschrieben anwenden; sind beide Signa gleich $-1$ können wir einen Elementarzug (Drehung einer Scheibe um $90^\circ$) durchführen, so dass beide Signa gleich 1 werden.

Nun ist noch folgende Richtung zu beweisen: Wenn der Würfel lösbar ist, sind die Signa der vorliegenden Permutationen der Kanten- und Eckkubies gleich. Eine lösbare Permutation muss durch Hintereinanderausführung von Elementarzügen in den Ausgangszustand zurückzuführen sein. Bei jedem Elementarzug werden sowohl bei den Eck- als auch bei den Kantenkubies drei Transpositionen ausgeführt. Also ändert sich bei jedem Zug sowohl das Signum der Eck- als auch das Signum der Kantenkubies. (Wenn das Signum gerade war, wird es durch drei weitere Transpositionen ungerade und wenn es ungerade war, wird es nun gerade.) Beim gelösten Würfel sind die Signa gleich (beide gerade). Da sich bei jedem Zug beide Signa verändert haben, müssen auch bei der lösbaren Permutation beide Signa gleich sein. Somit ist das Kriterium in beiden Richtungen bewiesen. $\Box$

Lösungsmöglichkeiten

In der letzten Aufgabe solten wir herausfinden, wie viele mögliche Positionen der $3 \times 3$-Rubik-Würfel annehmen kann. Es gibt 12! Möglichkeiten, die Kantenkubies auf die Kantenkubizile zu verteilen. Die Kantenkubies können jeweils zwei verschiedene Orientierungen annehmen. Für die ersten elf Kantenkubies gibt es also $2^{11}$ Möglichkeiten. Der letzte Kantenkubie muss dann so liegen, dass Satz 40 erfüllt ist. Für ihn gibt es also nur eine mögliche Orientierung. Bei den Eckkubies gibt es für die ersten sechs Eckkubies $8!/2$ Möglichkeiten. Für die beiden letzten Eckkubies gibt es nur noch genau eine Position, da nach Satz 41 Kanten und Ecken das gleiche Signum haben müssen. Für jeden Eckkubie gibt es jeweils drei Orientierungsmöglichkeiten. Also gibt es für die ersten sieben Eckkubies genau $3^7$ verschiedene Orientierungen. Der letzte Eckkubie muss dann so orientiert sein, dass das Kriterium 2 aus Abschnitt  erfüllt ist. Also gibt es insgesamt

$$12! \cdot 2^{11} \cdot 8!/2 \cdot 3^7 = 12! \cdot 8! \cdot 2^{10} \cdot 3^7 = 43\, 252 \, 003\, 274\, 489 \, 856 \, 000$$

Möglichkeiten.

Der 4x4 Würfel

Eck- und Mittelkubies des $\mathbf{4 \times 4}$-Würfels

Markus Balthasar, Marie Gille, Mareike Heinrich, Tim Offermann

Unser Ziel war es, Lösungsalgorithmen für den $4 \times 4$-Würfel zu entwickeln. Es folgt nun eine Beschreibung dieser zweiten Kurshälfte, wobei wir uns hier nur mit den elementaren Problemen beschäftigen werden.

Zunächst sollten wir Zugfolgen finden, um die Ecken zu tauschen. Dabei gab uns Olaf den gut gemeinten Ratschlag, die Zugfolgen besser durch Ausprobieren zu finden, da es auf mathematische Weise zu lange dauern würde. Wir haben dann also fleißig ausprobiert und sind auf eine Zugfolge gestoßen, die drei Ecken vertauscht, wobei gleichzeitig die Orientierung zweier Ecken mitvertauscht wird. Unser stolzes Ergebnis lautet:

$$\begin{array}{r@{\;}c@{\;}l} Z_1 &=& [{R_1}^{-1} , [L_1 \ U... ...1} {U_1}^{-1} \ R_1 U_1 L_1 {U_1}^{-1} {L_1}^{-1} \end{array}$$

Vorausgesetzt, der Würfel wurde nicht auseinandergebaut, so schafft man es mit diesem Zug, alle Ecken auf die richtige Position zu bringen. Wurde er manipuliert, so dürfen im Vergleich zum lösbaren Würfel die Ecken nur auf die oben beschriebene Variante vertauscht worden sein.

Nun haben wir die Ecken in der richtigen Position, doch verdammt noch mal, wie können wir sie in sich drehen? Nach weiterem hin- und herprobieren haben wir dann eine Zugfolge gefunden, die die Orientierung zweier Ecken ändert, wobei die eine Ecke in sich einmal und die andere zweimal gedreht wird. Unsere nächste Heldentat:

$$\begin{array}{r@{\;}c@{\;}l} Z_3 &=& {[B_1, {R_1}^{-1}]}^4 ... ...^4 {U_1}^{-1} \ (B_1 R_1^{-1} B_1^{-1} \ R_1)^2 \end{array}$$

Die Lösungskriterien sind denen von Zug $Z_1$ sehr ähnlich. Es muss also darauf geachtet werden, dass die Ecken immer in $3$-Zykeln verdreht werden. Setzt man nun einfach beide Zugfolgen zusammen, so schafft man es alle Ecken mit richtiger Orientierung auf die richtige Position zu drehen. Und das geht so:

In einer Ebene liegen mindestens zwei Eckkubies mit der gleichen Farbe. Die Orientierung spielt dabei erst einmal keine Rolle. Nun bringt man mit Hilfe von $Z_1$ die restlichen zwei Eckkubies dieser Farbe von der Seite in die Ebene. Nun wendet man abermals $Z_1$ an, um zunächst einen Eckkubie dieser Ebene richtig zu positionieren und dann die anderen drei auf ihren Platz zu bringen (wenn sie da nicht schon sind). Dann kann man mit $Z_3$ diese vier Eckkubies in die richtige Ausrichtung bringen; somit hat man schon eine Ebene gelöst. Bei der unteren Ebene kann man dann durch Drehung $Z_1$ genau einen Eckkubie in die richtige Position bringen, und die anderen drei wiederum durch $Z_1$ richtig positionieren (oder sie liegen schon alle richtig). Nun kann man die untere Ebene wieder durch $Z_3$ in die richtige Ausrichtung bewegen, und anschließend liegen alle acht Eckkubies in ihrer richtigen Position und Ausrichtung.

Leider besteht so ein $4 \times 4$-Würfel jedoch nicht nur aus Ecken, was zur Folge hatte, dass wir noch lange nicht arbeitslos waren. Unsere nächste Aufgabe bestand darin, die Mittelkubies miteinander zu vertauschen.

$$\begin{array}{r@{\;}c@{\;}l} Z_4 &= & [[B_2 \ R_2] \ {U_1}^... ...^{-1} \ R_2 \ B_2 \ {R_2}^{-1} \ {B_2}^{-1} \ U_1 \end{array}$$

Da die Mittelkubies ihre Orientierung nicht verändern können, reicht uns dieser Zug schon aus, um alle auf ihre richtige Position zu bringen. Indem man mit Hilfe der Zugfolge $Z_4$ zuerst die Mittelkubies einer Farbe von der Seite hochdreht und dann so nach und nach die sechs Seiten aufbaut, braucht man außer der Zugfolge $Z_4$ nur noch gegebenenfalls die Drehung der zu bearbeitenden Drehscheibe, um die seitlichen Kubies in die richtige Ausgangsposition zu bringen.

Kantenkubies des $\mathbf{4 \times 4}$-Würfels

Birte Albrecht, Dominik Klein, Axel Kröner, Martin Sallge

Die voherige Projektgruppe analysierte die Vertauschung von Ecken- und Mittelkubies des $4 \times 4$-Würfels. Zur vollständigen Lösung fehlen noch Zugfolgen, die einzelne Kanten vertauschen und richtig orientieren.

Problem 42   Man suche eine Zugfolge $Z_1$, die genau drei Kantenkubies innerhalb einer Ebene vertauscht und zwei davon umorientiert.

Lösung: Durch Ausprobieren fanden wir einen Kommutator, der genau die gewünschte Konstellation erzeugt:

$$Z_1 = [[F_1, R_1^{-1}], R_2^{-1}].$$

Die endgültige Zugfolge nach Kürzen des vierten und des sechsten Zuges lautet

$$\begin{array}{r@{\;}c@{\;}l} Z_1 = F_1 R_1^{-1} F_1^{-1} R_2^{-1} F_1 R_1 F_1^{-1} R_2 \end{array}$$

Problem 43  

Man wandle $Z_1$ mittels Konjugation in eine Zugfolge um, die drei Kantenkubies innerhalb der Ebene $f_2$ vertauscht und zwei von diesen in ihrer Orientierung ändert.

Lösung:

Durch Konjugation von $Z_1$ mit $D_1^{-1}F_2^{-1}$ ergibt sich eine Zugfolge

$$\begin{array}{r@{\;}c@{\;}l} Z_2 &=& D_1^{-1} F_2^{-1} Z_1 F_2 D_1, \end{array}$$

die die genannten Bedingungen erfüllt.

Um die folgenden Probleme zu lösen, sind einige Sätze wichtig.

Satz 44  

Auf jeder Kubieseite eines gelösten Würfels sei ein Pfeil, der zur Mitte der jeweiligen Würfelseite zeigt. Durch Elementarzüge lassen sich die Richtungen der Pfeile auf den Würfelseiten nicht verändern.

Beweis:

Trivial. $\Box$

Im weiteren setzen wir voraus, dass auf die Seiten der Kubies im gelösten Zustand des Würfels Pfeile angebracht wurden, die auf die Mitte der Würfelseiten zeigen.

Satz 45  

Sei ein Würfel beliebig zusammengesetzt und alle Kantenkubies an ihrem richtigen Kubizil. Dann ist der Würfel entweder gelöst oder er ist nicht lösbar.

Beweis:

Wir betrachten ein beliebiges Kubie.

Fall 1: Einer der beiden Pfeile zeigt nicht auf die jeweilige Mitte der Würfelseite. Da durch Elementarzüge die Richtung der Pfeile auf den Würfelseiten beibehalten und der gelöste Würfel eindeutig bestimmt ist, lässt sich der Würfel nicht in den gelösten Zustand überführen.

Fall 2: Die Richtungen der Pfeile stimmen. Dann ist der Würfel bereits gelöst. $\Box$

Im folgenden gehen wir davon aus, dass der Würfel lösbar sei.

Problem 46  

Gegeben sei ein vollständig durchmischter Würfel. Ist es möglich, mit Hilfe der Zugfolge $Z_1$, dessen konjugierten Zugfolgen und maximal einem elementaren Zug, alle Kantenkubies in ihr korrektes Kubizil und ihre korrekte Orientierung zu bringen?

Lösung:

Es ist möglich. Da es sowohl Elementarzüge mit Signum $1$ (Drehung der Außenscheiben) als auch mit Signum $-1$ (Drehung der Innenscheiben) gibt, kann das Signum der Permutation der Kantenkubies entweder $1$ oder $-1$ sein. Da aber $Z_1$ und alle Konjugationen von $Z_1$ Signum $1$ haben, besteht im zweiten Fall die Notwendigkeit, die Würfelstruktur auf eine geradzahlige Permutation zurückzuführen. Dies erreicht man durch einmaliges Ausführen eines Elementarzugs mit Signum $-1$, also der Drehung einer mittleren Scheibe. Von einer Permutation mit Signum $1$ ist es nun durch Ausführen von $Z_1$ und allen Konjugationen dieser Zugfolge, insbesondere $Z_2$ und der Spiegelung $Z_1'$ von $Z_1$ an einer der Mittelachsen von $u_1$ möglich, alle Kubies an ihr korrektes Kubizil zu bringen. Da wir die Orientierung unbeachtet lassen können (vgl. Satz 45), ist es möglich, durch eine Folge von Elementarzügen jeden Kantenkubie an jedes andere Kubizil zu überführen; die Kantenkubies liegen also in derselben Bahn wie die Ausgangsstellung. Da nun aber die Konjugationsklassen, also die Bahnen der Konjugationsdarstellung, aus allen Elementen einer Zykelstruktur bestehen, ist es möglich, $Z_1$ durch Konjugation in jeden anderen $3$-Zykel zu überführen.

Der Algorithmus lautet also folgendermaßen: Mit $Z_2$ überführen wir alle acht beziehungsweise vier Kantenkubies in die entsprechende Ebene. Dort tauschen wir jeweils 3 Kubies mittels $Z_1$, so dass pro Zug ein Kubie richtig positioniert wird. Diesen Kubie bewegen wir nicht mehr. Wir führen innerhalb dieser Ebene solange Permutationen aus, bis sämtliche Kubies in ihr korrektes Kubizil überführt sind. Mit den übrigen Ebenen wird genauso verfahren. Dieser Algorithmus bringt schließlich jedes Kantenkubie in das richtige Kubizil.

Problem 47  

Gegeben sei ein Würfel, dessen Eckkubies alle in ihrem korrekten Kubizil sind. Ist es immer möglich, mit Hilfe von $Z_1$, dessen konjugierten Zugfolgen und maximal einem elementaren Zug alle Kantenkubies korrekt zu orientieren, ohne die Eckkubies zu ändern?

Lösung:

Es ist immer möglich. Bei der Lösung zu Problem 46 werden lediglich solche $3$-Zykeln verwendet, die nur Kantenkubies vertauschen und zusätzlich ein Elementarzug, der die inneren Scheiben dreht. Da die Ecken dabei nicht vertauscht werden, ist dieses Problem in der Lösung zu Problem 46 inbegriffen.

Problem 48  

Gegeben sei ein Würfel, dessen Eckkubies und Mittelkubies alle in ihrem korrekten Kubizil und ihrer korrekten Orientierung sind. Ist es immer möglich, mit Hilfe von Zugfolge $Z_1$, dessen konjugierten Zugfolgen, maximal einem elementaren Zug und maximal zwei anderen Zugfolgen alle Kantenkubies korrekt zu orientieren, ohne die Eck- und Mittelkubies zu ändern?

Lösung:

Es ist immer möglich. Die Vorgehensweise ähnelt der von Problem 46. Man muss jedoch beachten, dass bei der Drehung einer der beiden mittleren Ebenen Mittelkubies vertauscht werden. Daher müssen die Mittelkubies zum Schluss durch ein mehrmaliges Ausführen des Zuges $Z_4$ (vgl. vorheriger Abschnitt) geordnet werden.

Problem 49  

Wieviel mögliche, optisch unterscheidbare Positionen kann der $4 \times 4$-Würfel annehmen?

Lösung:

Jeder Kantenkubie kann in seinem Kubizil nur in einer Orientierung auftreten (vgl. Satz 44) und durch Elementarzüge an jedes andere Kubizil gebracht werden. Da der $4 \times 4$-Würfel $24$ Kantenkubies besitzt, gibt es $24!$ Möglichkeiten die Kantenkubies anzuordnen.

Ohne die Kantenkubies zu verändern, können die Eckkubies $8!$ Positionen und $3^7$ verschiedenen mögliche Orientierungen annehmen. Die Mittelkubies können $24!/4!^6$ optisch unterscheidbare Positionen einnehmen.

Da alle Zugfolgen Signum $1$ haben und wir somit nur die Hälfte aller Möglichkeiten durch Drehen erzeugen können, ergeben sich insgesamt

$$24! \cdot 24!/4!^6 \cdot 8!/2 \cdot 3^7$$

4mm mögliche, optisch unterscheidbare Positionen, d. h.

$$88\,814\,362\,098\,778\,822\,438\,489\,127\,693\,982\,892\,032\,000\,000\,000 \approx 8,9 \cdot 10^{46}$$

Möglichkeiten.