Inhaltsverzeichnis

1 Einleitung 1

2 Rubik’s Zauberwurfel - eine Einfuhrung 3

2.1 Der Zauberwurfel - Funktionalitat und Beschreibung . . . . . . 3

2.2 Grundbegriffe der Gruppentheorie . . . . . . . . . . . . . . . . . 6

3 Mathematische Grundlagen 9

3.1 Wissenswertes zum Thema Permutationen . . . . . . . . . . . . 9

3.2 Konstruktionen aus der elementarenAlgebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.3 Notationsvereinbarungen fur den Zauberwurfel . . . . . . . . . . 15

4 Eigenschaften des Zauberwurfels 17

4.1 Positionen, Operationen und Manover . . . . . . . . . . . . . . 17

4.2 Operationen von Gruppen . . . . . . . . . . . . . . . . . . . . . 19

4.3 Beschreibung der Manovergruppen . . . . . . . . . . . . . . . . 22

5 Ausflug in die Manoverkunde - Konjugation und Kommuta-toren 27

5.1 Konjugationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.2 Kommutatoren . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

6 Weitere Begriffe und Resultate aus der Gruppentheorie 33

6.1 Homomorphismen, Nebenklassen, Faktorgruppen . . . . . . . . 33

6.2 Zyklische Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . 38

7 Die Rubiksche Gruppe 41

7.1 Ein Zugang uber die kleine Manovergruppe M . . . . . . . . . . 41

7.2 Die Struktur der Rubikschen Gruppe . . . . . . . . . . . . . . . 46

7.3 Bemerkungen zur Transitivitat imRubik Cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

i

8 Die Untergruppen des Zauberwurfels 528.1 Zyklische Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . 528.2 Bahnen, Stabilisatoren und der Satz von Sylow . . . . . . . . . 538.3 Untergruppen des Zauberwurfels . . . . . . . . . . . . . . . . . . 568.4 Cayley-Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . 618.5 Die Mittelscheibengruppe . . . . . . . . . . . . . . . . . . . . . 658.6 Untergruppen der Ordnung 2 . . . . . . . . . . . . . . . . . . . 708.7 Die Kommutatorgruppe . . . . . . . . . . . . . . . . . . . . . . 73

9 Die Losung des Wurfels 769.1 Wie und wie schnell man den Wurfel losen kann und warum es

uberhaupt so kompliziert ist . . . . . . . . . . . . . . . . . . . . 76

10 Andere mathematische Spielzeuge 8510.1 Der Superwurfel . . . . . . . . . . . . . . . . . . . . . . . . . . . 8510.2 Der 2× 2× 2-Wurfel . . . . . . . . . . . . . . . . . . . . . . . . 8910.3 Das magische Domino . . . . . . . . . . . . . . . . . . . . . . . 9110.4 Pyraminx - Die Zauberpyramide . . . . . . . . . . . . . . . . . . 92

ii

Kapitel 1

Einleitung

In den 70er Jahren des 19. Jahrhunderts wurde das sogenannte 15-Puzzle, einSchiebepuzzle, erfunden. Glaubt man der Legende, so hat eben dieses Puzzledie Vereinigten Staaten fur Wochen in Atem gehalten: Alle waren im Puzzle-Fieber, Kaufladen wurden nicht geoffnet, Arbeiter gingen nicht zur Arbeit. . . Der Grund dafur lag letztendlich darin, dass das Schiebepuzzle, so wie esdamals vorgestellt wurde, nicht losbar war.

Das Spiel besteht aus funfzehn durchnummerierten quadratischen Scheib-chen, die sich in einem 4 × 4-Rahmen, der stets ein leeres Feld enthalt, ver-schieben lassen. Dabei wird jeweils eine der neben dem leeren Feld befindlichenScheiben in das leere Feld geschoben. Ziel des Spieles war es, durch Schiebe-manover die Konstellation, bei der die Scheibchen 14 und 15 vertauscht waren,in den geordneten Zustand uber zu fuhren (s. Abb. 1.1).

Abbildung 1.1: Das 15-Puzzle in geordnetem Zustand (li.) und mit vertausch-ten Scheibchen (re.) (Quelle: http://de.wikipedia.org/wiki/15-Puzzle)

Um zu verstehen, warum dies nicht moglich sein kann und daher damalszahlreiche Puzzle-Spieler zur Verzweiflung brachte, bezeichnen wir das leereFeld mit

”16“ und konnen von nun an jede beliebige Konstellation als Permu-

1

tation von 1, 2, . . . , 16 auffassen. Damit sind alle in dem Spiel erlaubten ZugeTranspositionen: Eine Nummer, die dem leeren Feld benachbart ist, kann indieses hineingeschoben werden, sie wird nach unserer neuen Notation mit derNummer 16 vertauscht. Das leere Feld, die

”16“, wird bei jedem Zug bewegt.

In der Ausgangsstellung ist sie stets rechts unten und im geordneten Zustandebenfalls. Die Anzahl der Zuge (der Transpositionen), die man dazwischentatigt, muss also gerade sein. Dies impliziert, dass die Ausgangskonstellationnur dann geordnet werden kann, wenn sie einer geraden Permutation entspricht(C. Krattenthaler, 2004, S. 53 ff.). Da die Permutation (14, 15) offensichtlichungerade ist, war das Schiebepuzzle nicht losbar.

Circa 110 Jahre spater verursachte ein kleiner Wurfel, Rubik’s Cube ge-nannt, ein ahnliches Chaos in Mitteleuropa. Ursprunglich unter dem Namen

”Zauberwurfel“ auf den Markt gebracht, eroberte er Buros und Klassenraume.

Die mathematische Struktur, die diesem Spielzeug zugrunde liegt, ist um ei-niges komplexer als die des Schiebepuzzles und fasziniert die Wissenschaft bisheute, wie folgende, am 5. Juni 2007 erschienene Schlagzeile bezeugt:

Neuer Weltrekord mit Rubiks WurfelFur die Wissenschaft ist der Zauberwurfel oder Rubik-Wurfel mehr als eine

Spielerei. Mathematiker benutzen den Kubus, um ihre Formeln zu erharten.Mithilfe einer neuen Theorie und eines Hochleistungsrechners haben sie jetztbewiesen: 26 Zuge reichen, um den Wurfel aus jeder Stellung heraus zu losen.

(http://www.welt.de/wissenschaft/article922802/NeuerWeltrekordmitRubikswuerfel.html)

Die vorliegende Arbeit beschaftigt sich mit den algebraischen Grundlagendes Zauberwurfels. Sie bietet gleichzeitig eine Veranschaulichung elementarerGruppentheorie anhand dieses und einiger anderer Permutationspuzzles. Au-ßerdem erfahrt der Leser, wie man den Wurfel auf legale Art und Weise, d.h.ohne ihn zu zerlegen, losen kann.

2

Kapitel 2

Rubik’s Zauberwurfel - eineEinfuhrung

2.1 Der Zauberwurfel - Funktionalitat und Be-

schreibung

2.1.1 Beschreibung des Wurfels

Rubik’s Cube, auch Zauberwurfel genannt, ist ein Kunststoffwurfel, der aus3×3×3 = 27 Teilwurfeln, den Cubies besteht. Die Cubie-Seitenflachen an derOberflache des Wurfels sind so eingefarbt, dass jede der 6 Seiten des großenWurfels eine andere Farbe besitzt. Der Wurfel ist in insgesamt 9 Scheibengegliedert (in jeder Hauptachsenrichtung 3), die sich jeweils in ihrer Ebene umihren Mittelpunkt beliebig drehen lassen (s. Abb.2.1)

Abbildung 2.1: Mogliche Manipulationen des Zauberwurfels (Quelle: C. Bandelow,1981, S. 2)

3

2.1.2 Bezeichnung des Wurfels

Um eine sinnvolle Bezeichnung der Ecken- und Kantencubies des Wurfels fest-zulegen, ist es notwendig, dass dieser gerade auf dem Tisch liegt, sodass seineVorder- und Ruckseite sowie alle anderen Seiten eindeutig bestimmt sind. Die6 Flachen des Wurfels werden durch die Cubies im Zentrum, die sogenanntenFlachencubies, reprasentiert. Wir bezeichnen sie gemaß nachstehender Abbil-dung mit ihren kleinen lateinischen Anfangsbuchstaben (u = unteres Flachen-cubie, o = oberes Flachencubie, . . . ). Da sich ihre gegenseitige Lage nie andert,bestimmen sie die Farben der Wurfelseiten und die Position aller anderen Cu-bies im Ausgangszustand.

Abbildung 2.2: Bezeichnung der Flachen des Zauberwurfels (Quelle: C. Bandelow,1981, S. 4 )

Die Kanten des Wurfels (damit ist jeweils der mittlere der 3 Cubies anjeder Kante des großen Wurfels gemeint) werden mit den Buchstaben der sichdort treffenden 2 Flachen in beliebiger Reihenfolge bezeichnet, die Ecken (bzw.Eckcubies) mit den Buchstaben der sich dort treffenden 3 Flachen, wobei diesenach beliebiger Wahl der ersten Flache im Uhrzeigersinn gelistet werden sollen(s. Abbildung 2.3).

Abbildung 2.3: Bezeichnung der Ecken und Kanten des Zauberwurfels (Quelle:C. Bandelow, 1981, S. 5 )

4

2.1.3 Manipulationen des Wurfels

Eine mogliche R-Position ist ein aus dem Ausgangszustand (wohlgeordneterWurfel) durch Manipulationen des Wurfels erreichbares Farbmuster. Dabeigelten zwei Farbmuster als gleich, wenn sie durch Drehungen des Wurfels alsstarrer Korper ineinander ubergefuhrt werden konnen.

Die wichtigste Manipulation des Wurfels ist ein Randscheibenzug, die Dre-hung einer der sechs Randscheiben um 90 bzw. 180. Dabei bezeichnet mandie Drehung der betreffenden Scheibe um 90 im Uhrzeigersinn von außen be-trachtet mit dem jeweiligen lateinischen Großbuchstaben V , H, R, L, O, U .Die inverse Manipulation dazu, d.h. die 90-Drehung im Gegenuhrzeigersinn,bezeichnen wir mit V ′, H ′, R′, L′, O′, U ′ bzw. in Rechnungen mit Exponentenmit R−1, L−1, . . . Eine 180 Drehung im Uhrzeigersinn entspricht der Hinterein-anderausfuhrung von zwei 90-Drehungen und wird daher mit dem Exponenten2 beschrieben: V 2, H2, . . .

Diese elementare Manipulation wurde eigentlich zur Beschreibung des Wur-fels genugen, es empfiehlt sich allerdings, um die Bezeichnung der Manovermoglichst kurz zu halten, noch zwei weitere Zuge zuzulassen.

Bei einem Mittelscheibenzug wird eine der drei Mittelscheiben des Wurfelsum 90 bzw. 180 gedreht. Wir bezeichnen diesen Zug mitM und dem als Indexgesetzten Symbol des entsprechenden Randscheibenzuges, der Drehrichtungund -weite angibt, was bedeuten soll, dass statt der betreffenden Randscheibedie benachbarte Mittelscheibe gedreht wird, z.B. MV ,M

′V ,M

2V usw. Mit dieser

Bezeichnung hat naturlich jeder Mittelscheibenzug gleich zwei Namen (z.B.MR = M ′

L).

Ein Bewegungszug beschreibt schließlich die Drehung des ganzen Wurfelsum eine der drei Achsen, die die Mittelpunkte gegenuberliegender Wurfel-flachen verbinden. Wir bezeichnen ihn mit dem Buchstaben B und dem alsIndex gesetzten Symbol des entsprechenden Randscheibenzuges, wenn stattder Randscheibe der ganze Wurfel gedreht werden soll, z.B. BV , B

′V , B

2V Auch

hier gibt es fur jeden Zug zwei gleichwertige Namen (z.B. BR = B′L).

Ein Manover ist nach C. Bandelow (1981) eine endliche Folge von Zugen,in der weder zwei Scheibenzuge mit derselben Scheibe noch zwei Bewegungszugemit derselben Drehachse unmittelbar aufeinanderfolgen. Wir schreiben so eineFolge von Zugen dann in der Reihenfolge, in der sie ausgefuhrt werden sol-len, von links nach rechts nebeneinander. RO bedeutet somit, dass erst R unddann O ausgefuhrt wird. Dieselbe Konvention gilt in Folge auch fur die Ver-knupfung von Permutationen. Auch hier werden aufeinanderfolgende Zyklenvon links nach rechts angeschrieben. Wollen wir einmal von dieser Regel abwei-chen und, wie es ansonsten bei Funktionen ublich ist, von links multiplizieren,so verwenden wir fur die entsprechende Verknupfung

”“.

Am Ende eines Manovers wird im Folgenden oftmals seine Lange, d.h.die Anzahl seiner Scheibenzuge, in Klammer angegeben, um die Effizienz des

5

Manovers zu bestimmen. Gute Manover sind schließlich jene, die mit moglichstwenig Zugen gewunschte Operationen herbeifuhren und so zu einer kurzenund schnellen Losungsstrategie beitragen. Bewegungszuge werden hierbei nichtmitgezahlt, da sie die R-Position nicht verandern, z.B. ((MRO)4BRB

′O)3(24).

Ein Manover wird ruckgangig gemacht, indem man das zu ihm inverseManover anwendet. Man erhalt das inverse Manover m′ eines Manovers m,indem man m von hinten nach vorn liest und dabei die einzelnen Zuge umkehrt.(C. Bandelow, 1981, S. 8)

Beispiel: (R2M ′UR

2MU)′ = M ′UR

2MUR2

2.2 Grundbegriffe der Gruppentheorie

Notation Im folgenden wird die zu einer Abbildung x inverse Abbildung wiebei den Wurfelmanovern entweder mit x′ oder mit x−1 betitelt.

2.2.1 Gruppen

In diesem Abschnitt folgen wir im Wesentlichen A. Beutelspacher (2001, Ka-pitel 9).

Definition einer Gruppe

Eine Gruppe besteht aus einer nichtleeren Menge G zusammen mit einer Ver-knupfung · (die je zwei Elementen aus G wieder ein Element aus G zuordnet),sodass folgende Axiome erfullt sind:

1. Assoziativitat: Die Verknupfung · ist assoziativ:

(g · h) · k = g · (h · k) fur alle g, h, k ∈ G

2. Existenz eines neutralen Elements: Es gibt ein Element aus G, daswir e nennen, fur das gilt:

e · g = g fur alle g ∈ G

3. Existenz inverser Elemente: Fur jedes g ∈ G gibt es ein Element ausG, das wir g−1 nennen, fur das gilt:

g−1 · g = e, wobei e das neutrale Element ist.

Man sagt, dass G bezuglich der Verknupfung · eine Gruppe ist undschreibt (G, ·).Wenn zusatzlich folgendes Axiom gilt, nennt man eine Gruppe G kom-mutativ oder abelsch:

6

4. Fur je zwei Elemente g, h ∈ G gilt

g · h = h · g.

In einer Gruppe gibt es also nur eine Verknupfung, die oben mit · bezeich-net wurde. Will man diese Verknupfung additiv schreiben (d.h. + statt ·), sobezeichnet man ublicherweise das neutrale Element mit 0 und das zu g inverseElement mit −g.

Man kann zeigen, dass sowohl das neutrale Element als auch die inversenElemente eindeutig sind und dass g · e = g ∀g ∈ G und g · g−1 = e ∀g ∈ G.

Die Untergruppe

Eine Teilmenge U einer Gruppe (G, ·) heißt eine Untergruppe von G, falls (U, ·)ebenfalls eine Gruppe ist.

Untergruppenkriterium Sei U eine nichtleere Teilmenge von G. (U, ·) istgenau dann eine Untergruppe von (G, ·), falls folgende Kriterien erfullt sind:

• Wenn g ∈ U ist, so ist auch g−1 ∈ U

• Wenn g, h ∈ U sind, so ist auch gh ∈ U.

Beweis: Aufgrund der Assoziativitat auf G ist die Verknupfung · auch aufU assoziativ. U 6= ∅ - daher gibt es ein Element g ∈ U . Nach der 2. bzw. 3.Voraussetzung liegen auch g−1 bzw. g · g−1 = e in U . Daher liegt das neutraleElement von G in U und wirkt auch in U als neutrales Element. q.e.d.

Die Anzahl der Elemente einer endlichen Gruppe G heißt die Ordnung |G|von G.

Die symmetrische Gruppe

Die Menge aller Permutationen einer Menge X bildet bezuglich der Hinterein-anderausfuhrung von Abbildungen die symmetrische Gruppe auf X.

Ist X = 1, 2, . . . , n, so wird die symmetrische Gruppe auf X auch Sn

genannt. Die Anzahl aller Elemente der Sn entspricht der Anzahl der Moglich-keiten n Objekte wieder genau n Objekten im Bildbereich zuzuordnen. Dahergilt: |Sn| = n!.

2.2.2 Permutationen

Zyklische Permutationen

Eine Permutation π einer Menge X heißt Zyklus oder zyklische Permutation,falls ein i ∈ X und eine naturliche Zahl k existiert, sodass gilt:

7

1. πk(i) = i

2. die Elemente i, π(i), π2(i), . . . , πk−1(i) sind paarweise verschieden.

3. jedes Element, das verschieden von i, π(i), π2(i), . . . , πk−1(i), πk(i)(= i)ist, wird von π fest gelassen.

Die kleinste naturliche Zahl k mit dieser Eigenschaft wird Lange des Zyklusπ genannt. Ein Zyklus der Lange k heißt auch k-Zyklus. Man schreibt dannπ = (i, π(i), π2(i), . . . , πk−1(i)).

Proposition

Jede Permutation π lasst sich als Produkt disjunkter Zyklen (das sind Zyklen,die paarweise keine Elemente gemeinsam haben) darstellen.

Beweisidee: Man wahlt ein beliebiges Element i und schreibt es als Beginn desersten Zyklus an. Dann setzt man diesen Zyklus mit π(i), π2(i), . . . fort, bisman das erste Mal eine naturliche Zahl k findet, fur die πk(i) = i gilt. Dererste Zyklus (i, π(i), π2(i), . . . , πk−1(i)). ist somit beendet. Danach wahlt manein im ersten Zyklus noch nicht enthaltenes Element j und konstruiert damitden zweiten Zyklus etc. Man fahrt so lange fort, bis alle Elemente erfasst sind.

Bemerkungen

• Bei der Zyklendarstellung werden die Zyklen der Lange 1 ublicherweisenicht angeschrieben.

• Disjunkte Zyklen sind kommutativ.

Definition

Eine Permutation, die nur zwei Elemente vertauscht, heißt Transposition.

Proposition

Jede Permutation lasst sich als Produkt von Transpositionen darstellen.

Beweis: Jeder Zyklus der Lange k lasst sich folgendermaßen als Produktvon (k − 1) Transpositionen schreiben:

(x1, x2, x3, . . . , xk) = (xk−1, xk)(xk−2, xk−1) . . . (x2, x3)(x1, x2)

q.e.d.

8

Kapitel 3

Mathematische Grundlagen

3.1 Wissenswertes zum Thema Permutationen

In den Grundzugen dieses Abschnitts folgen wir wiederum A. Beutelspacher(2001, S. 178 ff.).

3.1.1 Definition

Eine Nachbartransposition ist eine Transposition, die zwei aufeinanderfolgendeElemente vertauscht.

3.1.2 Proposition

Jede Transposition kann als Produkt einer ungeraden Anzahl von Nachbar-transpositionen geschrieben werden.

Beweis: O.B.d.A. sei i < j. Dann gilt fur jede Transposition (i, j):

(i, j) = (j − 1, j)(j − 2, j − 1) . . . (i+ 1, i+ 2)(i, i+ 1)(i+ 1, i+ 2) . . . (j − 1, j)

Da zu beiden Seiten der Nachbartransposition (i, i + 1) dieselbe Anzahlvon Nachbartranspositionen steht, muss es sich bei der Darstellung insgesamtum eine ungerade Anzahl von Nachbartranspositionen handeln. Die genaueAnzahl betragt 2(j − i− 1) + 1.

3.1.3 Fehlstande von Permutationen

Fur eine beliebige Permutation π ∈ Sn nennt man ein Paar (i, j) von Elemen-ten der Menge X = 1, 2, . . . , n mit i < j aber π(i) > π(j) einen Fehlstandoder eine Inversion von π. Ein Fehlstand von π ist also ein Zahlenpaar, dessenOrdnung durch π verandert wird.

9

Im folgenden bezeichnet f die Anzahl der Fehlstande einer Permutation.

3.1.4 Korollar

Jede Nachbartransposition hat genau einen Fehlstand. Daher hat jede Trans-position eine ungerade Anzahl von Fehlstanden.

3.1.5 Definition

Eine Permutation π heißt gerade (ungerade), wenn die Anzahl f(π) ihrer Fehl-stande gerade (ungerade) ist. (−1)f(π) bezeichnet das Vorzeichen (Signum) derPermutation π.

Das Signum (sgn) einer Permutation π auf einer Menge X = 1, 2, . . . , nlasst sich auch folgendermaßen definieren:

sgn(π) =∏

1≤i<j≤n

π(i)− π(j)

i− j

Fur die Hintereinanderausfuhrung zweier Permutationen π und τ gilt dem-nach

sgn(π τ) =∏

1≤i<j≤n

π τ(i)− π τ(j)i− j

=∏

1≤i<j≤n

τ(i)− τ(j)

i− j

∏1≤i<j≤n

π τ(i)− π τ(j)τ(i)− τ(j)

=

= sgn(π) · sgn(τ)

Damit ist das Produkt zweier ungerader oder zweier gerader Permutatio-nen gerade und das Produkt einer geraden mit einer ungeraden Permutationungerade.

3.1.6 Satz

Sei π eine Permutation. Dann sind die folgenden Aussagen aquivalent:(a) π ist eine gerade Permutation.(b) Jede Darstellung von π als ein Produkt von Nachbartranspositionen

besteht aus einer geraden Anzahl von Nachbartranspositionen.(c) Es gibt eine Darstellung von π als Produkt einer geraden Anzahl von

Nachbartranspositionen.

10

Beweis:(a) ⇒ (b) : π sei eine gerade Permutation. Angenommen es gabe eine Dar-

stellung von π als Produkt einer ungeraden Anzahl von Nachbartranspositio-nen. Dann hatte π nach Korollar 3.1.4 eine ungerade Anzahl von Fehlstandenund ware somit eine ungerade Permutation. Widerspruch.

(b) ⇒ (c) : Trivial(c) ⇒ (a) : Jede Nachbartransposition hat genau einen Fehlstand. Damit

ist die Anzahl der Fehlstande von π gerade, wenn π sich als Produkt einergeraden Anzahl von Nachbartranspositionen schreiben lasst. Daher ist π einegerade Permutation.

q.e.d.

3.1.7 Korollar

Eine beliebige Permutation π ∈ Sn ist genau dann gerade, wenn sie das Pro-dukt einer geraden Anzahl von Transpositionen ist.

Beweis: Folgt aus vorhergehendem Satz und der Tatsache, dass jede Trans-position als Produkt einer ungeraden Anzahl von Nachbartranspositionen dar-gestellt werden kann.

Analog erhalt man

3.1.8 Satz

Sei π ∈ Sn eine beliebige Permutation. Dann sind folgende Aussagen gleich-wertig:

1. π ist eine ungerade Permutation.

2. π ist Produkt einer ungeraden Anzahl von Nachbartranspositionen.

3. π ist Produkt einer ungeraden Anzahl von Transpositionen.

Des weiteren folgt

3.1.9 Satz

π ∈ Sn ist genau dann gerade, wenn π−1 gerade ist.

Beweis: Es bezeichne I die identische Abbildung. Dann gilt I = π · π−1

und I ist gerade. Daher mussen π und π−1 entweder beide gerade oder beideungerade sein.

11

3.1.10 Definition

Die Menge aller geraden Permutationen aus der Sn heißt alternierende Gruppeund wird mit An bezeichnet.

3.1.11 Satz

Sei n eine naturliche Zahl. Dann gilt:(a) Das Produkt je zweier Permutationen aus An liegt wieder in An. Mit

anderen Worten: An ist bezuglich der Hintereinanderausfuhrung von Permu-tationen abgeschlossen.

(b) Fur jede Permutation π ∈ Sn\An gilt

Sn = An ∪ πAn,

wobei πAn := πα|α ∈ An ist.(c) Ist n ≥ 2, so gilt fur die Machtigkeit von An

|An| = n!2.

Genau die Halfte aller Permutationen ist also gerade.

Beweis:(a) Das Produkt gerader Permutationen ist gerade.(b) Trivialerweise gilt An ∪ πAn ⊆ Sn. Daher ist nur zu zeigen, dass eine

beliebige ungerade Permutation ψ ∈ Sn in πAn liegt. Mit π ist auch π−1 eineungerade Permutation. Daher ist π−1ψ eine gerade Permutation und liegt somitin An. Es gibt somit ein α ∈ An mit

π−1ψ = α

Daraus folgt

ψ = πα ∈ πAn.

(c) Da α → πα bijektiv ist, haben An und πAn gleich viele Elemente.Die beiden Mengen sind disjunkt, da An aus den geraden und πAn aus denungeraden Permutationen besteht. Da nach (b) Sn = An ∪ πAn und |Sn| = n!,folgt die Behauptung.

12

3.2 Konstruktionen aus der elementaren

Algebra

Die Inhalte dieses Abschnitts beziehen sich auf C. Bandelow (1981, S. 37 ff.).

3.2.1 Definition des Zentrums einer Gruppe

Ist A eine Gruppe, so heißt Z(A) := a ∈ A|ab = ba fur alle b ∈ A dasZentrum von A.

3.2.2 Proposition

Z(A) ist stets eine Untergruppe von A.

Beweis: Seien a, b ∈ Z(A). Dann gilt fur c ∈ A ac = ca und bc = cb. Darausfolgt abc = acb = cab und damit ab ∈ Z(A). Weiters gilt a′c = (ac′)′ = (c′a)′ =ca′ ⇒ a′ ∈ Z(A). Damit ist Z(A) eine Gruppe.

Folgender Satz zeigt, dass Sn in einer extremen Weise nicht abelsch ist:

3.2.3 Uber das Zentrum der symmetrischen Gruppe

Fur n ≥ 3 enthalt Z(Sn) lediglich das neutrale Element I.

Beweis: Ist f ∈ Sn und f 6= I, so gibt es ein a ∈ 1, . . . , n mit f(a) =:b 6= a. Wegen n ≥ 3 gibt es ein von a und b verschiedenes c ∈ 1, . . . , n.Es folgt (a, c)(f(a)) = (a, c)(b) = b und f((a, c)(a)) = f(c) 6= f(a) = b, alsof (a, c) 6= (a, c) f .

Bemerkung: Da sich jede Permutation als Produkt von Transpositionendarstellen lasst, erzeugt die Menge aller Transpositionen die gesamte symme-trische Gruppe Sn. Da (i, j) = (1, i)(1, j)(1, i) wird diese sogar von der Mengeder Transpositionen der Gestalt (1, i) erzeugt.

13

3.2.4 3-Zyklen erzeugen die alternierende Gruppe

Fur n ≥ 3 ist jedes Element der An das Produkt von 3-Zyklen.

Beweis: Jedes Element der An ist das Produkt einer geraden Anzahl vonTranspositionen der Gestalt (1, i). Fur je zwei solche Transpositionen gilt

(1, i)(1, j) = (1, i, j)

fur i 6= j. Die Identitat ist die dritte Potenz jedes 3-Zyklus.

3.2.5 Der Gruppenhomomorphismus

Seien G und H Gruppen. Eine Abbildung π : G→ H heißt Homomorphismus,falls ∀a, b ∈ G : π(ab) = π(a) · π(b).

Ist π bijektiv, so heißt π ein Isomorphismus und G undH heißen zueinanderisomorph, symbolisch A ∼= B.

Beispiel: Sei A eine Gruppe und a ∈ A beliebig. Die Abbildung π : A →A, π(b) := aba′(b ∈ A) ist ein Isomorphismus.

Beweis: Sie ist ein Homomorphismus, da

∀b, c ∈ A : π(bc) = abca′ = aba′ · aca′ = π(b) · π(c).

Sie ist bijektiv, da zu jedem c ∈ A genau ein b ∈ A mit c = π(b) = aba′

existiert, namlich b = a′ca.

3.2.6 Normalteiler einer Gruppe

Eine Untergruppe B einer Gruppe A heißt Normalteiler von A, wenn fur a ∈ Aund b ∈ B stets aba′ ∈ B gilt. Mit anderen Worten: die Menge aBa′ =aba′|b ∈ B ist gleich B.

3.2.7 Direktes und semidirektes Produkt mehrererGruppen

Seien A1, . . . , An Gruppen und B := A1×· · ·×An. Mit der komponentenweisenVerknupfung (a1, . . . , an) · (a1, . . . , an) = (a1a1, . . . , anan) heißt B das direkteProdukt der Gruppen A1, . . . , An. Falls A1 = A2 = · · · = An = A, schreibtman kurz B = An.

Beispiel: Sei B = A1 × A2 das direkte Produkt der Gruppen A1 und A2

und seien e1, e2 bzw. e die neutralen Elemente von A1, A2 bzw. B. Setzt man

14

A∗1 := (a1, e2)|a1 ∈ A1 und A∗

2 := (e1, a2)|a2 ∈ A2, dann ist A∗i eine zu Ai

isomorphe Untergruppe von B (i = 1, 2).Wie sofort ersichtlich ist, gilt sogar:

1. A∗i ist Normalteiler von B (i = 1, 2).

2. B = A∗1A

∗2 := a1a2|a1 ∈ A∗

1, a2 ∈ A∗2

3. A∗1 ∩ A∗

2 = e.

Gelten die drei eben genannten Punkte fur zwei Untergruppen A∗1 und A∗

2

einer Gruppe B, so heißt B ebenfalls (indem man A∗i mit Ai identifiziert) das

direkte Produkt von A∗1 und A∗

2 und schreibt B = A∗1 × A∗

2. Gilt statt 1. dieBedingung 1.′ A∗

1 ist eine Untergruppe von B und A∗2 ist ein Normalteiler von

B, so nennt man B das semidirekte Produkt von A∗1 mit A∗

2.

3.3 Notationsvereinbarungen fur den Zauber-

wurfel

Die Wirkung einzelner Manover besteht in der Anderung der Lage gewisserCubies, wobei ein Eckencubie stets wieder in ein Eckencubizil einzieht, einKantencubie in ein Kantencubizil und ein Flachencubie in ein Flachencubizil.

3.3.1 Notation fur Operationen

Eine mogliche Operation ist eine durch ein Manover bewirkbare Anderung derLage der Cubies.

Die hier verwendete Notation fur Operationen ist an C. Bandelow (1981)angelehnt und bringt nicht nur zum Ausdruck, welches Cubie in welches Cubizileinzieht, sondern auch, wie es sich dort einrichtet. (vr, hl, . . .) soll bedeuten,dass sich das Kantencubie aus vr so in hl niederlasst, dass seine bisherigev-Seite in h und seine bisherige r-Seite in l liegt. Allgemeiner treffen wir zurNotation eines beliebigen n-Zyklus, d.h. eines Wohnungsringtausches von nCubies, folgende Vereinbarungen:

• Nach der offnenden runden Klammer ist der Name eines beliebigen amRingtausch beteiligten Cubizils zu schreiben.

• Es folgen, durch Kommata voneinander getrennt, die Namen aller an-deren am Ringtausch beteiligten Cubizile in der durch den Ringtauschfestgelegten Reihenfolge, wobei der erste Buchstabe jeweils diejenige Sei-te des Wurfels bezeichnet, die die

”erste Seite“ des neu einziehenden

Cubies aufnimmt, d.h. die Cubieseite, die schon im alten Cubizil in derdort zuerst genannten Seite lag.

15

• Automatisch gilt dann entsprechendes im Falle von Kanten-Zyklen auchfur die zweiten Buchstaben der Cubizil-Namen und im Falle von Ecken-Zyklen fur die zweiten und dritten Buchstaben, wobei hier die bereitsfestgelegte Uhrzeigerkonvention wesentlich ist.

Beispiel: O → (ov, ol, oh, or)(ovl, olh, ohr, orv)

In oben beschriebenem Zyklus zieht das letzte Cubie in das an erster Stelleder Klammer stehende Cubizil um. Allerdings kann es sich dort, je nachdem, obes sich um ein Kanten- oder Eckencubie handelt, auf 2 bis 3 Weisen platzieren.Es kann seine Orientierung beibehalten oder nach links bzw. rechts verdrehen.

Um dies zu beschreiben, wird wieder C. Bandelows Notation verwendet:Man denke sich das Cubie aus dem in der Zyklusklammer an letzter Stelle

stehenden Cubizil im ersten Cubizil zunachst so platziert, als ware obenste-hende Konvention - wie es bei einer Zyklenschreibweise naheliegt - auch furdie Beziehung zwischen dem letzten und dem ersten Zykluselement gultig. Istes dann, um der gegebenen Operation zu entsprechen, noch zu verdrehen, soschreiben wir im Falle eines nach links zu drehenden Eckencubies das Vorzei-chen - , im Falle eines nach rechts zu drehenden Eckencubies das Vorzeichen+ und im Falle eines umzudrehenden Kantencubies das Vorzeichen + vor dasbetroffene erste Cubizil, d.h. unmittelbar nach der offnenden Klammer.

Beispiel:HLOL′O′H ′(6) → (−ovl, orv)(+olh, ohr)(ov, ho, ol) Dieses Mano-ver bewirkt u.a. die Operation (−ovl, orv), bei der das Eckencubie orv nachlinks verdreht in das Cubizil ovl wandert.

16

Kapitel 4

Eigenschaften des Zauberwurfels

4.1 Positionen, Operationen und Manover

4.1.1 Beschreibung der R-Positionen

Im folgenden werden vorerst ausschließlich Randscheibenzuge betrachtet. Die6 Flachencubies verlassen ihre Platze nicht und eine R-Position wird uberdie Lage der 8 Kanten- und 12 Eckencubies definiert (deren Cubizile mansich jeweils durchnummeriert vorstellen kann). Hierbei wird der Platz (nichtdie Orientierung) der Eckencubies durch eine Permutation ρ der S8 sowie dieVerteilung der Kantencubies durch eine Permutation σ der S12 beschrieben.

Da sich auch die Orientierung der Cubies in einem Manover andern kann,muss diese ebenfalls erfasst werden. Dazu markieren wir nach einem von C.Bandelow (1981) erdachten Prinzip an jeder der 8 Ecken bzw. jeder der 12 Kan-ten des Wurfels eine der drei bzw. zwei dort zusammentreffenden Wurfelseitenmit einem Bogen bzw. einem Strich (wie in Abb. 4.1 dargestellt). Die Markie-rungsstriche seien nicht auf den Cubies, sondern auf einer fiktiven Wurfelhulleangebracht, d.h. sie zeichnen jeweils eine der drei bzw. zwei außeren Cubizil-seiten aus. Außerdem nummerieren wir die drei farbigen Seiten eines jedenEckencubies im Uhrzeigersinn mit 0, 1 und 2 und die beiden farbigen Seiteneines jeden Kantencubies mit 0 und 1, wobei im Ausgangszustand des Wurfelsdie Nullen jeweils unter den Markierungsbogen bzw. -strichen liegen mogen.Fur eine beliebige R-Position kann die Orientierung der Ecken- bzw. Kan-tencubies nun durch ein 8-tupel x = (x1, . . . , x8) ∈ X := 0, 1, 28 und ein12-tupel y = (y1, . . . , y12) ∈ Y := 0, 112 charakterisiert werden, wobei xi bzw.yj angibt, welche Seite des i-ten Eckencubies bzw. j-ten Kantencubies im Cu-bizil ρ(i) bzw. σ(j) unter dem Markierungsbogen bzw. -strich liegt. Wir nennendas Eckencubie Nr. i richtig orientiert, nach links verdreht bzw. nach rechtsverdreht, wenn xi = 0, 1 bzw. 2 ist, und das Kantencubie Nr. j richtig bzw.falsch orientiert, wenn yj = 0 bzw. 1 ist.

17

Abbildung 4.1: Markierungen, die die Orientierung der Cubies festlegen (Quelle:C. Bandelow, 1981, S. 44)

4.1.2 Mathematische Definition einer R-Position

Wir definieren eine R-Position als ein 4-tupel (ρ, σ, x, y) mit ρ ∈ S8, σ ∈S12, x = (x1, . . . , x8) ∈ 0, 1, 28 und y = (y1, . . . , y12) ∈ 0, 112. P ∗ sei dieMenge aller R-Positionen. (C. Bandelow, 1981, S. 45)

4.1.3 Mathematische Definition einer R-Operation

R-Operationen sind bestimmte bijektive Abbildungen von P ∗ in P ∗. Einemogliche R-Operation ist eine R-Operation, die durch ein R-Manover bewirktwerden kann.

Die Menge G der moglichen R-Operationen und die Menge G∗ aller R-Operationen sind Untergruppen der symmetrischen Gruppe uber P ∗. Wir nen-nen G die Rubiksche Gruppe (C. Bandelow, 1981, S. 45).

Erklarung: Die symmetrische Gruppe uber P ∗ ist die Menge aller bijekti-ven Abbildungen aller R-Positionen in sich selbst. Ein Element dieser Gruppeordnet somit jeder R-Position eine andere R-Position zu. Ein Element ausG∗ ordnet ebenfalls jeder R-Position eine andere R-Position zu mit der Ein-

18

schrankung, dass mit jeder R-Position das gleiche passiert: Die R-Operation(+orv)(ov, oh) ordnet z.B. jeder R-Position eine neue R-Position zu, indem siedas obere rechte vordere Eckencubie nach rechts dreht und die Kantencubiesaus ov und oh in einer bestimmten Weise vertauscht.

4.1.4 Die große Manovergruppe

Sei M die Menge aller Manover. Sie wird als große Manovergruppe bezeichnet.

4.1.5 Proposition

M ist eine Gruppe.

Beweis: Das neutrale Element bildet IM , das”leere Manover“, das kei-

nen einzigen Zug enthalt. Zu jedem m ∈ M gibt es, wie bereits erwahnt,auch ein inverses Manover m′. Die Verknupfung auf M ist die Hintereinander-ausfuhrung zweier Manover, wobei man diese nebeneinander schreibt und alleunmittelbar aufeinanderfolgenden Scheibenzuge mit derselben Scheibe bzw.Bewegungszuge mit derselben Drehachse zusammenfasst bzw. kurzt.

Beispiele: R ·R2 = R′, LV R2 ·R2V ′H = LH

4.1.6 Die kleine Manovergruppe

Die kleine Manovergruppe M ist eine Untergruppe von M und besteht ausallen R-Manovern, d.h. aus allen m ∈M , in denen weder Mittelscheiben- nochBewegungszuge, also ausschließlich Randscheibenzuge vorkommen. Somit istM die von V,H,R, L,O und U (mit R4 = L4 = V 4 = H4 = O4 = U4 = I)erzeugte Gruppe (C. Bandelow, 1981, S. 40).

4.2 Operationen von Gruppen

4.2.1 Die Operation einer Gruppe auf einer Menge

Sei G eine Gruppe und Ω eine Menge. Unter einer Operation von G auf Ωversteht man eine Funktion µ : G× Ω → Ω sodass ∀ω ∈ Ω, ∀g, h ∈ G gilt

µ(h, µ(g, ω)) = µ(hg, ω)

und ∀ω ∈ Ω

µ(1, ω) = ω,

19

wobei 1 das neutrale Element der Gruppe bezeichnet.Man schreibt oft ωg statt µ(g, ω) und erhalt damit fur die Axiome die etwas

einfachere Notation:

(ωg)h = ωhg sowie ω1 = ω

∀ω ∈ Ω und ∀g, h ∈ G.Fur eine Gruppe von Permutationen G auf einer Menge Ω existiert eine

sogenannte naturliche Operation µ auf Ω, die folgendermaßen definiert ist:

µ(g, ω) := g(ω)

Die Axiome fur diese naturliche Operation lauten

h(g(ω)) = hg(ω), 1(ω) = ω.

(Neumann, P.; Stoy, G.; Thompson, E., 1994, S. 30)

D.Joyner (2002, S. 88) liefert eine etwas einfachere Formulierung fur die Ope-ration einer Gruppe:

Sei X eine Menge und G eine Gruppe. Wir nennen X eine G-Menge undsagen, dass G auf X operiert, wenn die folgenden Bedingungen gelten:

1. Jedes g ∈ G erzeugt eine Funktion

φg : X → X,

2. der Identitat I der Gruppe G ist die Identitatsfunktion aufX zugeordnet,

3. wenn g, h zu G gehoren, dann gilt fur die Komposition

φhg : X → X, dass φhg(x) = φh(φg(x)).

4.2.2 Transitive G-Mengen

Man sagt, dass Ω eine transitive G-Menge ist, oder dass G transitiv auf Ωoperiert, falls Ω 6= ∅ und ∀α, β ∈ Ω ∃g ∈ G : αg = β.

Eine G-Teilmenge einer G-Menge Ω ist eine Teilmenge Ω′ von Ω, fur diegilt: ω ∈ Ω′ ⇒ ωg ∈ Ω′ ∀g ∈ G. Eine transitive G-Teilmenge heißt Bahn(Neumann, P.; Stoy, G.; Thompson, E., 1994, S. 50).

20

4.2.3 Darstellung einer G-Menge durch ihre Bahnen

JedeG-Menge kann eindeutig als disjunkte Vereinigung von Bahnen dargestelltwerden.

Beweis: Sei Ω eine G-Menge. Darauf wird folgende Aquivalenzrelation de-finiert:

α ≡ β(modG) ⇔ ∃g ∈ G : αg = β.

Diese Relation ist eine Aquivalenzrelation:α ≡ α, da α1 = α;(α ≡ β) ⇒ (β ≡ α), denn aus αg = β folgt βg−1

= α;((α ≡ β) und (β ≡ γ)) ⇒ (α ≡ γ), denn wenn αg = β und βh = γ, dann

gilt αhg = γ.Fur eine entsprechende Indexmenge I sei (Ωi)i∈I die Familie der Aquiva-

lenzklassen. Es gilt daher

Ω =⋃i∈I

Ωi; Ωi ∩ Ωj = ∅, falls i 6= j; Ωi 6= ∅ ∀i ∈ I

Nun ist jede Aquivalenzklasse Ωi eine transitive G-Teilmenge von Ω, dennfur ω ∈ Ωi und g ∈ G gilt ωg ≡ ω(modG). Daraus folgt ωg ∈ Ωi; des weiterenfolgt aus α, β ∈ Ωi, dass α ≡ β(modG). ⇒ ∃g : αg = β.

Um die Eindeutigkeit zu beweisen, sei Ω =⋃j∈J

Σj, wobei Σjj∈J eine Fa-

milie paarweise disjunkter, nichtleerer, transitiver G-Teilmengen ist. Aufgrundder Definition der Transitivitat gilt, dass, wenn α, β in ein und derselben G-Teilmenge Σj liegen, es ein g ∈ G mit αg = β gibt. Daher ist α ≡ β(modG).

Umgekehrt, falls α ≡ β(modG) und α ∈ Σj, dann gilt aufgrund der Tat-sache, dass β = αg und Σj ein G-Teilraum ist, dass auch β in Σj liegen muss.Daraus folgt: α ≡ β(modG) ⇔ α, β in derselben Teilmenge Σj fur irgend-ein j ∈ J liegen. Das bedeutet, die Teilmengen Σj sind genau die ≡-klassenund die Familie Σjj∈J ist nichts anderes als Ωii∈I (Neumann, P.; Stoy, G.;Thompson, E., 1994, S. 51).

21

4.3 Beschreibung der Manovergruppen

4.3.1 Die kleine Manovergruppe

Definition Bezeichne nun Γ die Menge aller Cubies, die durch die kleineManovergruppe bewegt werden, d.h. alle Ecken- und Kantencubies. Die Teil-menge der Eckencubies bezeichnen wir mit Γc, die Teilmenge der Kantencubiesmit Γe.

Proposition

Die kleine Manovergruppe M operiert auf Γ, da jeder Randscheibenzug einePermutation der Cubies aus Γ darstellt. Es handelt sich um die naturlicheOperation von M auf Γ.

M operiert intransitiv auf Γ. Sie hat zwei Bahnen, die Menge Γc der 8Eckencubies und die Menge Γe der 12 Kantencubies (Neumann, P.; Stoy, G.;Thompson, E., 1994, S. 243).

Beweis: Trivial. Kanten- und Eckencubies konnen naturlich nicht vertauschtwerden.

Die Abbildung π : M → G, die jedem R-Manover die von ihm bewirk-te mogliche R-Operation zuordnet, ist ein Homomorphismus von der kleinenManovergruppe auf die Rubiksche Gruppe: π(mamb) = π(ma) ·π(mb), in Wor-ten, das Produkt von zwei R-Manovern bewirkt die Komposition der von denbeiden R-Manovern bewirkten moglichen R-Operationen. Zwei R-Manover ma

und mb heißen aquivalent, symbolisch ma∼= mb, wenn sie dieselbe R-Operation

bewirken: π(ma) = π(mb) (C. Bandelow, 1981, S. 45). Wir bezeichnen die Men-ge der Aquivalenzklassen von M mit M/ ≈= mi|i ∈ I.

Mit der Abbildung M × P ∗ → P ∗, (m, p) → m(p) := (π(m))(p) operiertdie kleine Manovergruppe auf der Menge der R-Positionen. Es gilt:

1. IM(p) = p ∀p ∈ P ∗ und

2. (mamb)(p) = ma(mb(p)) ∀p ∈ P ∗; ma,mb ∈M .

Diese Operation entspricht der naturlichen Operation von M auf P ∗.

Genauso wie in der kleinen Manovergruppe kann man auch in der Mengeder R-Positionen eine Aquivalenzrelation definieren:

Fur pa, pb ∈ P ∗ gelte pa∼= pb ⇔ ∃m ∈ M : pa = m(pb). Auch hier stellen

die Aquivalenzklassen Bahnen dar.

22

Definition einer moglichen R-Position

Eine R-Position p ∈ P ∗ heißt moglich, wenn sie in derselben Bahn wie derAusgangszustand IP = (1, 1, 0, 0) liegt, wenn also ein m ∈ M mit p = m(IP )existiert. (Hier steht 1 fur IS8undIS12, 0 fur das 8- bzw. 12-tupel (0, . . . , 0).) Psei die Menge aller moglichen R-Positionen (C. Bandelow, 1981, S. 46).

4.3.2 Die große Manovergruppe

Erinnerung Sie beinhaltet nicht nur Randscheibenzuge, sondern auch Mittel-scheiben- und Bewegungszuge.

Um hier alle moglichen Manipulationen des Wurfels zu erfassen, muss manin den Begriff der Position die

”Lage des Wurfels auf dem Tisch“ mit einbe-

ziehen. Diese beschreiben wir durch ein Element τ ∈ S6, eine Permutation der6 Flachencubies.

Definition einer Position

Eine Position ist ein Quintupel (ρ, σ, τ, x, y) mit ρ ∈ S8, σ ∈ S12, τ ∈ S6, x ∈0, 1, 28 und y ∈ 0, 112. P ∗ sei die Menge aller Positionen (C. Bandelow,1981, S. 46).

Proposition

Von den 720 (=6!) Permutationen der 6 Flachencubies treten nur 24 bei mogli-chen Positionen auf.

Beweis: Die Lage des Wurfels wird durch die Wahl einer der 6 Seiten als obereSeite und einer der dazu 4 senkrechten Seiten als vordere Seite festgelegt. Diesergibt 6 · 4 = 24 Moglichkeiten.

(Diese 24 Lagen entsprechen den Elementen der Drehgruppe D des Wurfels.)

Alle weiteren Begriffe fur die große Manovergruppe werden analog zur kleinenManovergruppe definiert.

23

4.3.3 Beschreibung der moglichen Positionen und Ope-rationen (nach C. Bandelow, 1981, S. 39 ff.)

Bemerkung Nach Satz 3.2.4 wird die alternierende Gruppe An fur n ≥ 3 vonden 3-Zyklen der Gestalt (1, i, j) erzeugt. Da (1, i, j) = (1, 2, j)(1, 2, i)(1, 2, j)2

genugen sogar die 3-Zyklen der Gestalt (1, 2, i).

Hauptsatz zum Zauberwurfel

Eine R-Position (ρ, σ, x, y) ist genau dann moglich, wenn die folgenden dreiBedingungen erfullt sind:

(a) sgn(ρ) = sgn(σ),(b) x1 + x2 + . . .+ x8 ≡ 0 mod 3,(c) y1 + y2 + . . .+ y12 ≡ 0 mod 2.

Beweis: (1) Wir zeigen, dass die drei Bedingungen fur jede mogliche R-Position gelten, also notwendig sind:

Erstens gelten sie fur den Ausgangszustand IP mit ρ = IS8 , σ = IS12 (unddamit sgn(ρ) = sgn(σ) = 1) sowie x1 = x2 = . . . = x8 = y1 = y2 = . . . = y12 =0. Zweitens bleiben die drei Bedingungen bei jedem der 6 RandscheibenzugeO, U , R, L, V und H erhalten, denn:

Jedes dieser Manover bewirkt gleichzeitig einen Ecken-4-Zyklus und einenKanten-4-Zyklus und damit jeweils eine ungerade Permutation der Ecken- undKantencubies.

Die Komponenten von x andern sich beiO oder U uberhaupt nicht, wahrendsich bei R, L, V und H jeweils zwei Komponenten um 1 mod 3 erhohen undzwei Komponenten um 1 mod 3 erniedrigen. (s. Abbildung 4.1)

Des weiteren andern sich bei jedem der 6 Zuge genau vier Komponentenvon y um 1.

(2) z.z.: Die drei Bedingungen sind hinreichend. Dazu zeigen wir, dass jedeR-Position p = (ρ, σ, x, y), die die drei Bedingungen erfullt, durch ein geeigne-tes Manover m in den Ausgangszustand uberfuhrt werden kann, d.h. zu jedemsolchen p ∃m ∈M mit m(p) = IP :

O.B.d.A. sei sgn(ρ) = sgn(σ) = 1 (Gilt sgn(ρ) = sgn(σ) = −1, so giltfur pa := (ρa, σa, xa, ya) := O(p) die Gleichung sgn(ρ) = sgn(σ) = 1, und ausma ∈M mit ma(pa) = IP folgt (ma O)(p) = ma(O(p)) = IP ).

Gelingt es uns nun jeweils ein Manover fur die Ecken-3-Zyklen (X1, X2, Xi)(i = 3, . . . , 6) zu finden, so haben wir gezeigt, dass jede gerade Permutationder Ecken (und nach Voraussetzung enthalt unsere betrachtete R-Position einesolche gerade Permutation ρ ∈ S8) mit Hilfe dieser Manover in den Ausgangs-zustand IS8 ubergefuhrt werden kann, da nach obiger Bemerkung die sechs3-Zyklen (X1, X2, X3), (X1, X2, X4), . . . , (X1, X2, X8) die Gruppe aller geradenPermutationen von X1, . . . , X8 erzeugen.

24

Ein Manover m, das den 3-Zyklus (X1, X2, X3) fur die Ecken X1 = ovl,X2 = orv, X3 = ohr bewirkt und die ubrigen Ecken (hier mit X4, . . . , X8 be-zeichnet) und alle Kanten festhalt, ist m = RH ′RV 2R′HRV 2R2(9) (s. nach-folgende Abbildung 4.2).

Abbildung 4.2: (Quelle: C. Bandelow, 1981, S. 23 )

Nun gibt es aber zu jedem i ∈ 4, . . . , 8 ein hochstens zweizugiges Manoverki ∈ M , das das Eckencubie aus Xi mit irgendeiner Orientierung nach X3

bringt, ohne die Cubies in X1 und X2 zu verandern. Das Manover kimk′i be-

wirkt dann genau den Zyklus (X1, X2, Xi). Daher gibt es ein ManovermE ∈M ,das alle acht Eckencubies in ihr Heimatcubizil bringt.

Analog gibt es einen Kanten-3-Zyklus, von dem ausgehend man ein ManovermK finden kann, das alle 12 Kantencubies auf ihren Platz bringt. Ein Beispielfur einen solchen Zyklus ist das Manover m = R2M ′

UR2MU(4) → (vr, hl, rh).

In der neuen Position mK(mE(p)) (= mE(mK(p))) sind bereits alle Ecken-und Kantencubies im richtigen Cubizil. Da bei allen Randscheibenzugen unddamit bei allen Manovern der kleinen Manovergruppe die Bedingungen (b)und (c) erhalten bleiben, gelten diese nun auch fur die neue Position. D.h. umden Wurfel in den geordneten Zustand zuruckzufuhren ist eine gerade Anzahlvon Kantencubies umzuorientieren, und die Anzahl der nach rechts zu drehen-den Eckencubies ist gleich der Anzahl der nach links zu drehenden Eckencubiesmod 3. Wir losen dieses Problem unter Verwendung zweier Manover, die un-seren Anspruchen Folge leisten. Das eine, LV R′V ′L′O2RORO′R2O2R(13) →(+ov)(+or), andert die Orientierung zweier Kantencubies und erhalt damitBedingung (b), das andere, R(O2RV ′U2V R′)2R′(13) → (+orv)(−ovl) drehtzwei Ecken in entgegengesetzte Richtungen, wie es Bedingung (c) erfordert.

Diese Manover wendet man auf den von C. Bandelow (s. Abbildung 4.3)vorgeschlagenen Wegen um den Wurfel, die jeweils zwei benachbarte Ecken-bzw. Kantencubies verbinden und jedes Ecken- bzw. Kantencubie genau einmalerreichen, an und erreicht so stets die richtige Orientierung aller Cubies. q.e.d.

25

Abbildung 4.3: Wege um den Wurfel (Quelle: C. Bandelow, 1981, S. 48 )

Die Anzahl der Farbmuster

Die Anzahl der moglichen R-Positionen ist

|P | = |G| = 112|P ∗| = 1

12· 8! · 12! · 38 · 212 = 43252003274489856000

Beweis: Fur die 8 Eckencubies gibt es 8!, fur die 12 Kantencubies 12! An-ordnungen. Jedes Eckencubie kann des weiteren 3 Orientierungen und jedesKantencubie 2 Orientierungen haben. Daher gilt fur die Anzahl aller Positio-nen

|P ∗| = 8! · 12! · 38 · 212.

Da fur mogliche Positionen nur gerade Permutationen in Frage kommen,wird diese Zahl auf die Halfte reduziert. Wegen x1 + x2 + . . . + x8 = 0 mod3 kann die Orientierung von 7 Eckencubies beliebig gewahlt werden und be-stimmt dann die Orientierung des 8. Eckencubies - die Zahl der Positionenwird weiter auf ein Drittel verringert. Fur die Kantencubies gilt analog: wegeny1 +y2 + . . .+y12 = 0 mod 2 kann die Orientierung von 11 Kantencubies belie-big gewahlt werden und bestimmt dann die Orientierung des 12. Kantencubies,was die Zahl der moglichen Positionen nochmals auf die Halfte reduziert. Ins-gesamt finden wir also eine Reduktion auf 1

2· 1

3· 1

2= 1

12. q.e.d.

26

Kapitel 5

Ausflug in die Manoverkunde -Konjugation undKommutatoren

5.1 Konjugationen

5.1.1 Definition

Sei G eine Gruppe und b ∈ G ein festes Element. Unter der Konjugation unterb versteht man die Abbildung ϕ : G→ G: ϕ(x) = bxb−1

Wie bereits gezeigt ist ϕ ein Isomorphismus. Die Umkehrabbildung ist dieKonjugation unter b−1 (denn

ϕ(ϕ−1(y)) = b(ϕ−1(y))b−1 = bb−1ybb−1 = y).

Fur eine abelsche Gruppe ist jede Konjugation die identische Abbildung:bab−1 = abb−1 = a.

Das Element bab−1 heißt das unter b zu a konjugierte Element. Zwei Ele-mente a, a∗ einer GruppeG heißen konjugiert, wenn es ein b ∈ Gmit a∗ = bab−1

gibt. Mit dieser Bezeichnung gilt

ba = a∗b.

Man kann damit die Konjugation unter b als Anderung von a auffassen,die eintritt, wenn man b von einer Seite auf die andere verschiebt (M. Artin,1998, S. 53 ff.).

5.1.2 Konjugationen als Manover

Konjugationen sind ein hilfreiches Instrument beim Losen des Zauberwurfels.Als Wurfelspezialist kennt man in der Regel einige Manover auswendig, die

27

sehr spezielle Dinge tun, z.B. ein Manover, das zwei spezielle Kantencubiesumorientiert ohne etwas anderes am Wurfel zu andern. Sei m → (+ov)(+ol)ein solches Manover. Hat man nun bei seinem Wurfel die Situation vorliegen,zwei andere Kantencubies umorientieren zu mussen, benotigt man z.B. dieOperation (+uv)(+uh), so wird man den Wurfel einfach umdrehen und zweiRandscheibenzuge durchfuhren, um schließlich die Cubies von den Cubizilenuv und uh nach ov und ol zu bringen. Danach wird man das Manover manwenden und anschließlich die vorbereitenden Randscheibenzuge sowie dieUmdrehung des Wurfels wieder ruckgangig machen.

Mathematisch gesehen geschieht folgendes: Bezeichnen wir das gesamteManover, das wir anwenden mussen um die zu drehenden Kantencubies andie fur m vorgesehenen Platze zu schaffen (also Wurfel umdrehen und diezwei Randscheibenzuge), mit p, so bewirkt p−1 die dazu inverse Operation, diedie Cubies, die durch m nicht tangiert wurden, wieder in ihre Heimatcubizilezurucktragt. Das gesamte Manover zur Umorientierung der beiden Kantencu-bies ware dann pmp−1, somit das unter p zu m konjugierte Manover.

Das Prinzip der Konjugation wurde auch im Beweis des Hauptsatzes 4.3.3verwendet, in dem man das Manover kimk

′i zur Erstellung des Zyklus

(X1, X2, Xi) nutzte.

5.2 Kommutatoren

5.2.1 Definition

Sind x, y Elemente einer Gruppe, so heißt das Element xyx−1y−1, symbolisch[x, y] ihr Kommutator.

Der Kommutator ist genau dann gleich 1, wenn die Elemente x und ykommutieren. (xyx−1y−1 = x(yx−1)y−1 = x(x−1y)y−1 = (xx−1)(yy−1) = ee =e)

Die meisten Manover der kleinen Manovergruppe kommutieren nicht, man-che jedoch schon, z.B. U und O, da sie auf ganz unterschiedliche Cubies wirken.Außerdem kommutiert naturlich jedes Manover mit sich selbst.

Wenn zwei Permutationen einer Gruppe nicht kommutieren, so ist ihr Kom-mutator, mit Vorsicht gesprochen, eine Art Gradmesser, wie stark die

”Nicht-

Kommutativitat“ unter ihnen ist. Wenn zwei Permutationen”fast“ kommu-

tieren, ist ihr Kommutator relativ einfach; wenn sie von der Kommutativitatdagegen weit entfernt sind, ist er eher komplex.

Beispiel: Sei

a = (1, 2, 3, 4, 5, 6)(7, 8, 9)(10, 11, 12, 13, 14)

undb = (7, 9)(15, 16, 17, 18, 19, 20).

28

Obwohl beide Permutationen eine Menge an Elementen verschieben, ist ihrKommutator

”nur“ [a, b] = (7, 9, 8). Das kommt daher, dass beide Permuta-

tionen zwar viele Objekte bewegen, jedoch nur wenige davon in gemeinsamenZyklen zu finden sind, in diesem Fall gerade 7,8 und 9. Die Permutation abeinhaltet zwar den Zyklus (1, 2, 3, 4, 5, 6), diese Objekte werden aber von bnicht weiter verschoben, sodass die inverse Operation a−1 im Kommutator dieAktion von a auf den 6 Elementen wieder ruckgangig macht.

Man kann jedoch nicht sagen, dass zwei Permutationen fast kommutativsind, nur weil sie wenige Objekte gemeinsam bewegen. Im nachfolgenden Bei-spiel wird nur das Objekt 6 von zwei Permutationen bewegt, aber deren Pro-dukt bringt alle Elemente in einen großen Zyklus zusammen:

(1, 2, 3, 4, 5, 6)(6, 7, 8, 9, 10) = (1, 2, 3, 4, 5, 7, 8, 9, 10, 6)

.Dagegen konnen zwei Permutationen auch dann kommutativ sein, wenn sie

beide alle Objekte gemeinsam bewegen, z.B.

[(1, 2)(3, 4)] [(1, 3)(2, 4)] = (1, 4)(2, 3) = [(1, 3)(2, 4)] [(1, 2)(3, 4)]

.

5.2.2 Kommutatoren als Manover

Ein Beispiel: Erstellung des Manovers m→ (+ov)(+ol).Dazu suchen wir eine Serie von Zugen, die die oberste der 3 Schichten des

Wurfels vollig unangetastet lasst, außer dass ein einziges Kantencubie umori-entiert wird:

Wir mochten beispielsweise den ov-cubie umorientieren, aber die restlichenCubies an der oberen Seite des Wurfels fest lassen. Dazu bringen wir die oberenrechten und linken Cubies mit RL′ aus dem Weg. Dieses Manover bringt jene6 Cubies an die Ruckseite des Wurfels. V 2 bewegt dann den Kantencubie, denwir umorientieren mochten, in das vu-cubizil, wobei die Seite des Cubies, diezuvor an der Oberseite des Wurfels lag, jetzt nach unten zeigt.

Wir mochten nun die Unterseite des Wurfels verdrehen, aber dieses Manoverwurde auch auf einige Cubies, die ursprunglich an der Oberseite lagen, wirken,also mussen wir diese mit LR′ erst zuruck an die Oberseite bringen (die durcheine Drehung der Unterseite nicht tangiert werden wurde).

Die Oberseite des Wurfels ist nun wieder korrekt, bis auf den falschenCubie in der ov-Position. Der richtige Cubie ist im uv-Cubizil. Um ihn um-zuorientieren, bevor wir ihn wieder in sein Heimatcubizil schicken, verwendenwir folgenden Trick: Wir verdrehen die Unterseite mit U ′ und verschieben soden Cubie nach lu. Dann bringen wir die 6 linken und rechten Cubies derOberseite mit RL′ aus dem Weg, damit der nun folgende V -Randscheibenzug

29

sie nicht tangiert, der allerdings unseren nun endlich umorientierten Kanten-cubie wieder in sein Heimatcubizil ov bewegt. LR′ verschiebt schließlich die 6Kantencubies von der Hinterseite zuruck zu ihrem angestammten Platz an derOberseite des Wurfels.

Das gesamte Manover lautet damit m = RL′V 2LR′U ′RL′V LR′.Wir erhalten damit einen Wurfel mit geordneter Oberschicht (bis auf den

umorientierten ov-Cubie), dessen restliche 2 Lagen aber vermutlich ziemlichzerstort sind. Wie gelangt man nun zu dem gewunschten Ergebnis (+ov)(+ol)?Nun, man wendetm an, um einen Cubie der Oberseite umzuorientieren, schiebtihn dann auf einen anderen Platz (mit O′), um ihn zu schutzen, bevor man m′

anwendet, mit dem man einen anderen Kantencubie der Oberseite umorientiertund den Schaden am Rest des Wurfels wieder behebt. Letztendlich bringt manmit O alle Cubies der Oberseite wieder an ihre ursprunglichen Platze. Ergebnis:Die Cubies in ov und ol haben ihre Orientierung geandert, und ansonsten istnichts passiert.

Die Gesamtabfolge an Manovern lautete damit mO′m′O (bzw. ausgeschrie-ben: RL′V 2LR′U ′RL′V LR′O′RL′V ′LR′URL′V 2LR′O) - wie man sieht han-delt es sich also um einen Kommutator! (Tom Davis, 2006, S. 27)

5.2.3 Satz

Seien X und Y die Randscheibenzuge zweier benachbarter Seiten des Wurfels.Der Kommutator X ′Y ′XY bewirkt einen 3-Zyklus auf Γe, der 3 Kantencubieszyklisch vertauscht und die restlichen 9 Kantencubies festhalt. Des weiterenbewirkt er eine Doppeltransposition auf Γc, indem er zwei Paare von Ecken-cubies vertauscht und die restlichen 4 Cubies nicht bewegt.

Daraus folgt, dass (X ′Y ′XY )2 als ein 3-Zyklus auf Γe operiert, wahrenddie Platze der Eckencubies sich nicht andern (die Orientierungen allerdingsschon!!). (X ′Y ′XY )3 bewirkt dann wieder eine Doppeltransposition auf Γc,wahrend die Kantencubies nicht bewegt werden (Neumann, P.; Stoy, G.;Thompson, E., 1994, S. 244).

5.2.4 Beispiel: Andere Manover fur 3-Zyklen

Die Strategie, ein Manover fur einen 3-Eckenzyklus zu finden, lautet folgender-maßen: Man sucht sich eine Abfolge von Zugen, die zwei benachbarte Eckencu-bies an der Oberseite des Wurfels vertauscht, wahrend der Rest der Oberseiteintakt bleibt. Dann verdreht man die Oberseite um 90 und macht das zu-vor verwendete Manover ruckgangig. Dadurch wird einer der zuvor getausch-ten Eckencubies neuerlich mit einem anderen vertauscht, aber der Rest desWurfels wird wieder in seinen Ausgangszustand gebracht. Das Endresultatist ein 3-Eckenzyklus, da die Permutationsstruktur folgendermaßen aussieht:(1, 2)(2, 3) = (1, 3, 2).

30

Ein Manover, das zwei Eckencubies der Oberseite vertauscht und den Restdavon fest lasst ist LR′URU ′L′. Die gesamte Permutation, die den 3-Eckenzyklusverursacht, lautet somit LR′URU ′L′OLUR′U ′RL′O′.

Man erhalt einen 3-Zyklus auch als Produkt zweier Permutationen mittelsfolgender Uberlegung:

(ADC) = (ABCD)(ACBD) = (ABCD)(AD)(DCBA)(AD)

.Das Permutationsprodukt bewirkt die zyklische Vertauschung von 4 Cu-

bies, die Inversion zweier dieser Cubies und die abschließende Invertierung des4-Zyklus und der Transposition. Um das dazu notige Manover zu beschreiben,verwenden wir der Einfachheit halber auch Mittelscheibenzuge.

ML verursacht (ov, vu, uh, ho). O2 vertauscht danach ov und oh, und M ′L

produziert den Zyklus (ov, ho, uh, vu). Ein weiterer Zug O2 bringt alles anderean seine ursprungliche Position zuruck. Das Produkt ergibt

(ov, vu, uh, ho)(ov, oh)(ov, ho, uh, vu)(ov, oh)

= (ov, vu, uh, ho)(ov, hu, uv, ho) = (ov, oh, uh)

und das gesamte dazu notige Manover lautet nun MLO2M ′

LO2. Dies ist ein

Kommutator, da (O2)′ = O2 (Tom Davis, 2006, S. 29).

5.2.5 Satz

Sei G die Rubiksche Gruppe. Die Kommutatorgruppe K(G) besteht aus allenendlichen Produkten von Kommutatoren und ist in diesem Fall die

”halbe“

Gruppe:

K(G) = (ρ, σ, x, y) ∈ G| sgn(ρ) = sgn(σ) = 1

Beweis: Ist g = [g1, g2] = g1g2g′1g

′2 = (ρ, σ, x, y) ein Kommutator mit

g1 = (ρ1, . . .) und g2 = (ρ2, . . .), so gilt ρ = ρ1ρ2ρ′1ρ

′2, also sgn(ρ) = 1 (da

sgn(ρ1) = sgn(ρ′1)). Die Bedingung sgn(ρ) = sgn(σ) = 1 gilt damit fur alleKommutatoren, also auch fur alle Produkte von Kommutatoren, d.h. fur alleg ∈ K(G).

Umgekehrt ist jedes g = (ρ, σ, x, y) ∈ G mit sgn(ρ) = sgn(σ) = 1 dasProdukt von Kommutatoren, da es fur die zum Losen des Wurfels benotigtenElementaroperationen Manover gibt, die die Gestalt eines Kommutators derkleinen Manovergruppe haben:

Verdrehung zweier Kantencubies:

V OU ′L2O2U2R ·O ·R′U2O2L2UO′V ′ ·O′ → (+ov)(+or)

31

Umorientierung zweier Eckencubies:

R′URV UV ′ ·O′ · V U ′V ′R′U ′R ·O(14) → (+orv)(−ovl)

Ecken-3-Zyklus:

R ·HL′H ′ ·R′ ·HLH ′(8) → (ovl, orv, hro)

Kanten-3-Zyklus:

OLUR · V ·R′U ′L′O′ · V ′(10) → (ov, ro, rv)

.Konjugierte von Kommutatoren sind wieder Kommutatoren, denn

m ·mambm′am

′b ·m′ = (mmam

′)(mmbm′)(mmam

′)′(mmbm′)′.

Als Bildelement unter dem Homomorphismus π (der jedem R-Manoverdie von ihm bewirkte mogliche R-Operation zuordnet) ist schließlich die voneinem Produkt von Kommutatoren in M bewirkte Operation ein Produkt vonKommutatoren in G. q.e.d. (C. Bandelow, 1981, S. 54)

32

Kapitel 6

Weitere Begriffe und Resultateaus der Gruppentheorie

6.1 Homomorphismen, Nebenklassen, Faktor-

gruppen

Wir folgen in 6.1.1 bis 6.1.10 im Wesentlichen A. Beutelspacher (2001, Kapitel9).

6.1.1 Kern und Bild

Sei f : G → H ein Homomorphismus der Gruppe G in die Gruppe H und edas neutrale Element von H. Der Kern von f ist definiert als

Kern(f)=g ∈ G|f(g) = e.

Das Bild von f besteht aus allen Bildern der Elemente von G:

Bild(f)=h ∈ H| es gibt g ∈ G mit f(g) = h = f(g)|g ∈ G.

6.1.2 Satz

Sei f : G → H ein Homomorphismus von Gruppen. Dann ist Kern(f) einNormalteiler von G.

Beweis: (1) Kern(f) ist eine Untergruppe von G, da die drei Bedingun-gen des Untergruppenkriterium erfullt sind: (a) f(eG) = eH , denn fur a ∈ Gbeliebig gilt f(a) = f(eG · a) = f(eG) · f(a) ⇒ f(eG) = eH .

(b) Wenn g ∈ Kern(f) ⇒ g−1 ∈ Kern(f), da aus f(g) = e und e = f(e) =f(g · g−1) = f(g) · f(g−1) = e · f(g−1) = f(g−1) folgt f(g−1) = e und damitg−1 ∈ Kern(f).

33

(c) Wenn g, h ∈ Kern(f), so gilt f(g) = e und f(h) = e und f(gh) =f(g) · f(h) = e · e = e⇒ gh ∈ Kern(f).

Des weiteren gilt ∀g ∈ G dass f(g−1) = (f(g))−1, denn e = f(e) = f(g ·g−1) = f(g) · f(g−1) ⇒ (f(g))−1 = f(g−1).

Sei nun h ∈ Kern(f), also f(h) = e, und g ∈ G beliebig. Dann ist

f(g−1hg) = f(g−1)f(h)f(g) = f(g−1)ef(g) = f(g−1)f(g) = f(g)−1f(g) = e.

Damit gilt g−1hg ∈ Kern(f) und dieser ist tatsachlich ein Normalteiler vonG.

6.1.3 Definition einer Nebenklasse

Ist U eine Untergruppe von G und g ∈ G, so nennt man die Menge

gU = gu|u ∈ U

eine Nebenklasse von G nach U .

Bemerkung

Um die Notation moglichst einfach zu halten, wollen wir in Zukunft die kleineManovergruppe M mit M/ ≈ identifizieren. Das heißt, zwei Manover sind ge-nau dann verschieden, wenn sie verschiedene Operationen bewirken. Da dieMenge der moglichen Operationen isomorph zur Menge der moglichen R-Positionen ist (man denke sich jede Operation auf den geordneten Zustandangewandt), ist von nun an fur uns auch M isomorph zur Rubikschen GruppeG und kann daher mit ihr identifiziert werden.

Beispiel

Sei M die Rubiksche Gruppe und H = 1, U, U2, U3 die Untergruppe vonZugen der unteren Randscheibe. Sei g ∈ M ein Manover. Die Menge gH =g, gU, gU2, gU3 ist die Menge der Zuge, die denselben Effekt wie g haben,außer dass eventuell die untere Randscheibe zusatzlich am Ende bewegt wurde.Sie wird eine linke Nebenklasse von H genannt.

Fur die rechte Nebenklasse von H(= Hg = g, Ug, U2g, U3g) gilt dieanaloge Definition (D. Joyner, 2002, S. 92).

34

6.1.4 Satz uber Nebenklassen

Sei U eine Untergruppe der Gruppe G. Es gilt(a) gU = hU ⇔ h−1g ∈ U .(b) Je zwei verschiedene Nebenklassen von U sind disjunkt.(c) Die Abbildung f : U → gU mit f(u) = gu ist eine Bijektion.Beweis: (a) Es gilt

gU = hU ⇒ g = ge ∈ hU ⇒ g = hu fur einu ∈ U ⇒ h−1g = u ∈ U(⇔ gh−1 = (h−1g)−1 ∈ U).

Umgekehrt folgt aus u := h−1g ∈ U dass g = hu ∈ hU , also gU ⊆ hU . Esfolgt auch , dass h = gu−1 ∈ gU , also hU ⊆ gU , und somit gU = hU .

(b) Sei x ∈ gU ∩ hU . Dann ∃u1, u2 ∈ U : gu1 = x = hu2. ⇒ h−1g =u2u

−11 ∈ U . Daher gilt nach (a) gU = hU .(c) Trivial.

6.1.5 Definition

Sei G eine endliche Gruppe und U eine Untergruppe von G. Wir nennen dieAnzahl der Nebenklassen von G nach U den Index von U in G, symbolisch[G : U ].

6.1.6 Satz von Lagrange

Sei G eine endliche Gruppe und U eine Untergruppe von G. Dann gilt

|G| = |U | · [G : U ].

Beweis: Je zwei Nebenklassen sind disjunkt. Da jedes Gruppenelement zueiner Nebenklasse gehort, ist die Menge der Nebenklassen eine Partition vonG. Da es eine bijektive Abbildung von U nach gU (g ∈ G) gibt, haben jezwei Nebenklassen die gleiche Machtigkeit, namlich |U | (da U = eU selbst eineNebenklasse ist!). Damit folgt:

|G| = Anzahl der Nebenklassen · Anzahl der Elemente proNebenklasse=[G : U ] · |U |. q.e.d.

Bemerkung: Aus dem Satz folgt, dass die Ordnung einer jeden Untergruppedie Gruppenordnung teilen muss.

6.1.7 Definition

Sei N ein Normalteiler von G. Dann heißt G/N = gN |g ∈ G die Faktor-gruppe von G nach N .

35

6.1.8 Satz uber die Faktorgruppe

Sei N ein Normalteiler der Gruppe G. Dann ist G/N eine Gruppe mit derVerknupfung (gN) · (hN) := ghN .

Beweis: Die Verknupfung ist wohldefiniert, denn: Seien g1, g2, h1, h2 ∈ Gmit g1N = g2N und h1N = h2N . Zu zeigen ist, dass g1h1N = g2h2N .

Wegen g1N = g2N ist g−11 g2 = n1 ∈ N . Ebenso ist n2 = h−1

1 h2 ∈ N . Darausfolgt:

g1h1 = g2n−11 h2n

−12 = g2h2n3n

−12 mit n3 ∈ N .

Dies gilt, da N ein Normalteiler ist und damit ∀g ∈ G, ∀n ∈ N : ng = gni

mit einem gewissen ni aus N . So unterscheiden sich g1h1 und g2h2 nur umn3n

−12 ∈ N . Damit ist g1h1N = g2h2N und die Multiplikation ist auf G/N

wohldefiniert.Die restlichen Gruppeneigenschaften ergeben sich trivialerweise.q.e.d.

6.1.9 Korollar

Sei f : G→ H ein Homomorphismus von Gruppen. Dann ist G/Kern(f) eineGruppe.

6.1.10 Homomorphiesatz fur Gruppen

Sei f : G → H ein Homomorphismus der Gruppe G in die Gruppe H. Danngilt

G/Kern(f) ∼= Bild(f).

Beweis: Sei N := Kern(f). Wir definieren die Abbildung ϕ : G/N →Bild(f) so naheliegend, wie nur moglich, als

ϕ(gN) := f(g).

ϕ ist wohldefiniert: zz. gN = hN ⇔ f(g) = f(h):gN = hN ⇔ gh−1 ∈ N(= Kern(f))⇔ f(gh−1) = e ⇔ e = f(gh−1) =

f(g)f(h−1) = f(g)f(h)−1 ⇔ f(g) = f(h)ϕ ist ein Homomorphismus: Seien gN und hN zwei beliebige Nebenklassen.

Dann gilt:ϕ(gN · hN) = ϕ(ghN) = f(gh) = f(g) · f(h) = ϕ(gN) · ϕ(hN).ϕ ist surjektiv: folgt aus der Definitionϕ ist injektiv: Seien gN und hN Nebenklassen. Dann folgt:ϕ(gN) = ϕ(hN) ⇔ f(g) = f(h) ⇔ f(gh−1) = f(g)f(h)−1 = e ⇔ gh−1 ∈

Kern(f)(= N) ⇔ gN = hN .q.e.d.

36

6.1.11 Der G-Morphismus

Seien Ω und Ω′ zwei G-Mengen. Unter einem G-Morphismus versteht man eineAbbildung θ : Ω → Ω′ fur die gilt θ(ωg) = (θ(ω))g ∀ω ∈ Ω,∀g ∈ G (Neumann,P.; Stoy, G.; Thompson, E., 1994, S. 74).

6.1.12 Die Kongruenz

Die Aquivalenzrelation ρ auf derG-Menge Ω heißtG-invariant (oder invariant),falls

α ≡ β (mod ρ) ⇒ αg ≡ βg (mod ρ) fur jedes g ∈ G.

Eine invariante Aquivalenzrelation heißt Kongruenz auf Ω.Als disjunkte Vereinigung der Aquivalenzklassen Γi ist ρ eine Partition von

Ω. Die Kongruenzbedingung besagt, dass, wenn α, β in derselben Aquivalenz-klasse Γi sind, fur jedes g ∈ G αg und βg in derselben Aquivalenzklasse Γj

sind. Das bedeutet Γgi = Γj. Folglich permutieren die Elemente von G die

Aquivalenzklassen untereinander. Die Menge Γi|i ∈ I von Kongruenzklas-sen heißt Quotientenraum (oder Faktorraum) Ω/ρ. Schreibt man ρ(ω) fur dieAquivalenzklasse, die ω enthalt, dann ist die Operation von G auf Ω/ρ durchdie Regel ρ(ω)g = ρ(ωg) gegeben. Das zeigt, dass die Abbildung ω → ρ(ω) einG-Morphismus von Ω nach Ω/ρ ist (Neumann, P.; Stoy, G.; Thompson, E.,1994, S. 74).

6.1.13 Definition

Sei Ω eine transitive G-Menge, ρ eine Kongruenz auf Ω. Da die Kongruenz-klassen untereinander transitiv durch die Operation der Elemente von G per-mutiert werden, mussen sie alle dieselbe Große haben. Man spricht von einernicht-trivialen Kongruenz, falls die Klassen mehr als ein Element haben (d.h.falls ρ nicht die Identitat ist), und von einer ordentlichen Kongruenz, falls esmehr als eine Klasse gibt (d.h. falls ρ 6= Ω2).

Die G-Menge Ω heißt primitiv (oder man sagt, dass G primitiv auf Ω ope-riert), wenn sie transitiv und nicht-trivial ist und es keine nicht-triviale ordent-liche Kongruenz auf Ω gibt (Neumann, P.; Stoy, G.; Thompson, E., 1994, S.79).

37

6.2 Zyklische Gruppen

6.2.1 Definition

Das Erzeugnis der Elemente g1, g2, . . . einer Gruppe G, symbolisch 〈g1, g2, . . .〉ist der Durchschnitt aller Untergruppen von G, die g1, g2, . . . enthalten:

〈g1, g2, . . .〉 =⋂U |U Untergruppe, die g1, g2, . . . enthalt.

〈g1, g2, . . .〉 besteht aus allen Produkten der Elemente g1, g2, . . . und ihrerInversen.

Die von einem Element g ∈ G erzeugte Untergruppe 〈g〉 von G besteht ausallen Potenzen von g:

〈g〉 = gz|z ∈ Z.

〈g〉 heißt die von g erzeugte zyklische Untergruppe von G. Eine Gruppeheißt zyklisch, wenn sie von einem Element erzeugt ist.

Eine additiv geschriebene Gruppe (G,+) ist zyklisch, wenn es ein Elementg ∈ G gibt, derart, dass G gleich der Menge der (ganzzahligen) Vielfachen vong ist:

G = 〈g〉 = zg|z ∈ Z.

Beispiel: (Zn,+) ist eine zyklische Gruppe der Ordnung n. Sie wird vondem Element 1 erzeugt.

Die Ordnung eines Elements g ∈ G ist die Ordnung der von g erzeugtenUntergruppe von G (Beutelspacher, 2001, S. 235 ff.).

6.2.2 Satz

Sei g ein Element einer Gruppe G. Dann ist die Ordnung von g unendlich,oder die Ordnung ist die kleinste positive ganze Zahl k mit gk = e.

Beweis: Sei die Ordnung von 〈g〉 endlich und m die Anzahl der Elementevon 〈g〉. Weiters sei k die kleinste positive ganze Zahl mit gk = e. zz.: k = m

(1) Wir zeigen: k ≤ m. Das folgt daraus, dass die Elemente

e = g0, g1, g2, . . . , gk−1

verschieden sind (ware gi = gj mit 0 ≤ i < j < k ⇒ gj−i = gj(gi)−1 = e mitj − i < k, Widerspruch).

Also hat 〈g〉 mindestens k verschiedene Elemente ⇒ k ≤ m.(2) Wir zeigen: m ≤ k. Das folgt daraus, dass G′ := g0, g1, g2, . . . , gk−1

eine Untergruppe bildet:Zur Uberprufung wenden wir das Untergruppenkriterium an.

38

• G′ 6= ∅.

• Das Inverse eines Elements gi ∈ G′ ist gk−i, denn gigk−i = gk = e. Aus0 < k − i < k folgt gk−i ∈ G′.

• Seien gi, gj ∈ G′. Zu zeigen: gigj = gi+j ∈ G′. Dies ist klar, wenn i+j < k.Wenn i+ j ≥ k ⇒ i+ j = k+ i′ mit 0 ≤ i′ < k ⇒ gi+j = gk+i′ = gkgi′ =egi′ = gi′ ∈ G′.

G′ ist also eine Untergruppe von G, die g enthalt. Damit enthalt G′ auch〈g〉, und die Anzahlm der Elemente von 〈g〉 ist hochsten so groß wie die Anzahlk der Elemente von G′. q.e.d. (Beutelspacher, 2001, S. 236 ff.)

6.2.3 Korollar

Wenn G eine endliche zyklische Gruppe der Ordnung m ist, dann gilt

G = g0, g1, g2, . . . , gm−1 = e, g, g2, . . . , gm−1

fur jedes g ∈ G, das G erzeugt. (Beutelspacher, 2001, S. 237)

6.2.4 Satz uber die Untergruppen einer zyklischenGruppe

Sei G eine zyklische Gruppe der Ordnung n. Ist k ein Teiler von n, so hat Geine Untergruppe der Ordnung k.

Beweis: Sei G = 〈g〉. Da k|n⇒ ∃m ∈ N mit km = n.Wir zeigen: h := gm hat Ordnung k. Aus hk = (gm)k = gmk = gn = e folgt,

dass die Ordnung von h hochstens k ist. Ware die Ordnung k′ von h kleinerals k, so ware aber auch gmk′ = (gm)k′ = hk′ = e mit mk′ < mk = n. Damithatte g eine Ordnung < n, Widerspruch.

Daher hat die Untergruppe 〈h〉 von G Ordnung k. q.e.d. (Beutelspacher,2001, S. 237 ff.)

6.2.5 Satz

Jede zyklische Gruppe ist isomorph zu Z oder zu Zn.Beweis: Sei G = 〈g〉 eine zyklische Gruppe.1. Fall: 〈g〉 ist unendlich. Dann sind die Elemente gz fur z ∈ Z alle verschie-

den und durchlaufen ganz G. ⇒ f : G→ Z, f(gz) := z ist ein Isomorphismusvon G in (Z,+).

2. Fall: 〈g〉 ist endlich. Sei n die Ordnung von 〈g〉. Die Abbildung f : G→Zn, f(gi) := i ist ein Isomorphismus. q.e.d. (Beutelspacher, 2001, S. 238)

39

6.2.6 Definition des Kranzproduktes

Seien G und H endliche Permutationsgruppen auf den Mengen Γ und ∆.Das Kranzprodukt G wr H ist die Gruppe von Permutationen t der Menge

Γ×∆ der Form:t : (γ, δ) → (gδ(γ), h(δ)), wobei gδ ∈ G und h ∈ H. t wird daher durch ein

Element h ∈ H und eine Funktion ∆ → G bestimmt (Neumann, P.; Stoy, G.;Thompson, E., 1994, S. 96).

Eine genauere Erklarung bietet die Definition von J.A.Eidswick (1986, S.159):

Seien G und H Permutationsgruppen, die auf Γ = 1, . . . , n und ∆ =1, . . . , r operieren. Das Kranzprodukt H wr G ist eine Untergruppe der sym-metrischen Gruppe Sym(Γ×∆), die durch Permutationen der folgenden zweiArten erzeugt wird:

π(g) : (i, j) → (g(i), j)

fur g ∈ G und

δ(h1, . . . , hn) : (i, j) → (i, hi(j))

fur h1, . . . , hn ∈ H.Diese Definition kann man folgendermaßen visualisieren: Angenommen n

Stoße von Spielkarten besetzen die Positionen 1, . . . , n und angenommen jederStoß enthalt r Karten, die die Level 1, . . . , r besetzen. Dann permutiert π(g) dieKartenstoße der Permutation g entsprechend, wahrend es die Reihenfolge derSpielkarten innerhalb eines Stoßes beibehalt, und δ(h1, . . . , hn) durchmischt dieeinzelnen Kartenstoße in Positionen 1, . . . , n den zustandigen Permutationenh1, . . . , hn entsprechend, wahrend es die Positionen der Stoße festhalt.

Wir verwenden in weiterer Folge die Notation der 2. Definition (H wr G).D. Joyner (2002) weist darauf hin, dass Kranzprodukte Verallgemeinerungenvon semidirekten Produkten sind. Man konnte das Kranzprodukt (H wr G)auch als das semidirekte Produkt (symbolisch o) (GoHr) anschreiben.

In unseren Anwendungen wird H zyklisch und damit isomorph zu Zr furein r > 0 sein. Die auf dieser Gruppe definierte Verknupfung ist dann additiv.

40

Kapitel 7

Die Rubiksche Gruppe

7.1 Ein Zugang uber die kleine Manovergruppe

M

Die Inhalte dieses Abschnitts wurden in Anlehnung an P. Neumann, G. Stoyund E. Thompson (1994, S. 243 ff.) zusammengestellt.

7.1.1 Definition

Die Gruppe aller Permutationen von Γ, die die Ecken- und Kantencubies je-weils untereinander permutieren, ist das direkte Produkt der symmetrischenGruppe uber Γc und uber Γe. Wir konnen sie daher, um die Notation einfachzu halten, mit S8 × S12 identifizieren. Sei MP die Untergruppe von Permu-tationen von Γ, die von Elementen der kleinen Manovergruppe M induziertwerden. Dann gilt MP ⊆ S8 × S12.

Wie wir bereits wissen beinhaltet M nur Permutationen ρ ∈ S8, σ ∈ S12 :sgn(ρ) = sgn(σ). Daraus folgt: MP = (S8 × S12) ∩ A20. Das direkte Produktbesagt, dass man jede Permutation der Ecken mit jeder Permutation der Kan-ten kombinieren kann, und der Durchschnitt mit allen geraden Permutationender insgesamt 20 Ecken- und Kantencubies stellt sicher, dass die gesamte ausρ und σ bestehtende Permutation gerade ist, d.h. dass sgn(ρ) = sgn(σ). (Hierwird S8 × S12 als Teilmenge der S20 aufgefasst. Es ist die Teilmenge aller Per-mutationen der 20 Cubies, die Ecken- bzw. Kantencubies separat voneinanderpermutieren.)

Die Ordnung von MP betragt 12· 8! · 12!.

Erklarung: Eine Permutation aus MP ist genau dann gerade, wenn ρ undσ entweder beide gerade oder beide ungerade sind. Die Anzahl der Permuta-tionen, bei denen ρ und σ gerade sind, betragt |A8| · |A12| = 1

2· 8! · 1

2· 12!.

Die Anzahl der Permutationen, bei denen ρ und σ ungerade sind, betragt|S8\A8|·|S12\A12| = 1

2·8!· 1

2·12!. Daraus folgt |MP | = 1

2·8!· 1

2·12!+ 1

2·8!· 1

2·12! =

41

12· 8! · 12!.

Bemerkung

Der Kern der Operation von M auf Γ ist die Gruppe N , bestehend aus allenManovern, die jeden Cubie in seinem Heimatcubizil belassen und nur eventuellseine Orientierung andern.

7.1.2 Proposition

N ist Normalteiler von M und MP∼= M/N .

Erklarung: Fur jedes m ∈ M , n ∈ N gilt mnm−1 ∈ N , denn, wenn ich einbeliebiges Manover m mit Permutationen ρ ∈ S8 und σ ∈ S12 anwende unddanach ein Manover n, das die Ecken- und Kantencubies nicht weiter unterein-ander permutiert, so macht das inverse Manover m−1 die ersten Permutationenwieder ruckgangig und ubrig bleiben nur etwaige Verdrehungen der Ecken undKanten, also ein Manover aus N . Damit (und als Kern von M ohnehin!) ist NNormalteiler von M .

Das Bild der Operation von M auf Γ besteht aus allen moglichen Permu-tationen von Γ und entspricht damit der Gruppe MP . Nach dem Homomor-phiesatz gilt daher MP

∼= M/N .

7.1.3 Definition

Wir betrachten nun, als neue Referenzmenge Ω die sichtbaren Seitenflachenaller Cubies, bis auf die zentralen Cubies, die fur uns einen Bezugsrahmendarstellen. Dabei bezeichnen wir mit Ωc die sichtbaren Flachen aller Ecken-cubies und mit Ωe die sichtbaren Flachen aller Kantencubies. Da jeder der 12Kantencubies je 2 sichtbare Seitenflachen und jeder der 8 Eckencubies je 3sichtbare Seitenflachen hat, gilt |Ωc|=|Ωe|=24.

Ahnlich wie bei Γe und Γc konnen auch die Elemente von Ωe und Ωc nuruntereinander vertauscht werden. Daher gilt:

7.1.4 Folgerung

Die Gruppe M hat zwei Bahnen in Ω, namlich Ωe und Ωc.

42

7.1.5 Proposition

Die Operationen von M auf Ωe und Ωc sind transitiv, aber nicht primitiv.Erklarung:

• transitiv: Fur zwei beliebige Eckenseiten a, b gibt es ein Manover aus M ,das (unter anderem) a dorthin bringt, wo zuvor b war, d.h. a wird durchM auf b abgebildet.

• nicht primitiv: Die M -Menge Ωc ist zwar transitiv und nicht-trivial, aberes gibt sehr wohl eine nicht-triviale ordentliche Kongruenz auf Ωc. Wirbetrachten dazu die Aquivalenzrelation, deren Aquivalenzklassen jeweilsaus den Seitenflachen eines bestimmten Cubies bestehen. Diese Aquiva-lenzrelation ist eine Kongruenz, denn die 3 Seitenflachen eines Eckencu-bies werden offensichtlich nur als 3er-Pack cubieweise vertauscht. Mochteman eine Seitenflache eines Eckencubies mit der eines anderen Eckencu-bies tauschen, so muss man notgedrungen auch die anderen beiden Sei-tenflachen des ersten Cubies mit denen des zweiten Eckencubies vertau-schen. Ein Manover bewirkt stets das gleiche, egal ob man sich vorstellt,dass es auf der Menge der Seitenflachen der Cubies oder auf der Mengeder Cubies selbst operiert, nur ist der Kern der Operation von M jeweilsein anderer. Das heißt, es spielt keine Rolle, ob man sich erst uberlegt,zu welchem Cubie die Seitenflache gehort und dann das Manover m an-wendet oder ob man erst das Manover durchfuhrt und dann nachsieht,auf welchem Cubie die Seitenflache sitzt - wenn die Flache wandert, mussder Cubie schließlich mitwandern! Daher sind zwei zueinander aquivalen-te Seitenflachen nach Anwendung eines beliebigen Manovers noch immerzueinander aquivalent, was der Kongruenzbedingung entspricht. Außer-dem entspricht dies der Tatsache, dass die Abbildung f : Ω → Γ, die jederSeitenflache den Cubie zuordnet, dem sie angehort, ein M -Morphismusist. Dieser M -Morphismus f besteht aus zwei M -Morphismen transitiverM -Mengen, fc : Ωc → Γc, fe : Ωe → Γe.

Fur die Kantenseiten gilt die analoge Erklarung.

7.1.6 Die”illegale“ Wurfelgruppe

Sei Q die Gruppe aller (moglichen und unmoglichen) Manover, die man durch-fuhren kann, wenn man den Zauberwurfel einfach in seine Bestandteile zerlegtund irgendwie wieder zusammensetzt(wobei zwei Manover als ident angesehenwerden, wenn sie dieselbe Operation bewirken).

Offensichtlich gilt M ⊂ Q und die Anzahl der Elemente von Q entsprichtder Anzahl aller R-Positionen. (Analog zur kleinen Manovergruppe identifizie-ren wir hier Q mit Q/ ≈!)

43

7.1.7 Lemma

|Q| = 8! · 38 · 12! · 212. Q ist das direkte Produkt Qc ×Qe, wobei |Qc| = 8! · 38

und |Qe| = 12! · 212.

Erklarung: Klarerweise operiert Qc auf Γc als die volle symmetrische Grup-pe S8 und der Kern dieser Operation ist das 8-fache direkte Produkt vonZ3 = 0, 1, 2 (da jedes Eckencubie 3 mogliche Orientierungen hat). Wir nen-nen diesen Kern Kc. Er ist eine abelsche Gruppe, da offensichtlich Manover,die nur Umorientierungen der Eckencubies bewirken, vertauschbar sind. JedesElement dieser Gruppe, das nicht die Identitatsabbildung ist, hat Ordnung 3,da jedes dieser Manover jeden Cubie nach 3-maliger Verdrehung wieder in dieAusgangsposition ubergefuhrt hat.

Genauso operiert Qe auf Γe als die volle symmetrische Gruppe S12, undder Kern Ke dieser Operation ist eine abelsche Gruppe, in der jedes ElementOrdnung 2 hat. Er entspricht einem 12-fachen direkten Produkt von Z2 =0, 1 (da jedes Kantencubie 2 mogliche Orientierungen hat).

Qc und Qe sind Kranzprodukte. Das kann man sich z.B. fur Qc folgender-maßen vorstellen: erst werden die Eckencubies untereinander permutiert, unddann wirken 8 unterschiedliche Abbildungen auf die 8 Cubies, die jedem eineZiffer von 0 bis 2, je nach seiner Verdrehung, zuordnen.

7.1.8 Korollar

Die Struktur von Q sieht damit folgendermaßen aus:

Q ∼= (Z3wrS8)× (Z2wrS12).

7.1.9 Lemma

Auch die Gruppe N bestehend aus allen moglichen R-Manovern, die Cubiesnicht vertauschen, sondern nur umorientieren, kann man als direktes Produktderjenigen Manover Nc, die auf die Seitenflachen der Eckencubies und derjeni-gen Manover Ne, die auf die Seitenflachen der Kantencubies wirken, anschrei-ben. Es gilt somit

N = Nc ×Ne

Erklarung: Wie wir bereits gesehen haben, gibt es Manover, die nur dieVerdrehung zweier Kanten, und Manover, die nur die Umorientierung zweierEcken bewirken. Da man zum Losen des Wurfels aus der Gruppe N nur diesebeiden Arten von Manovern benotigt, erzeugen sie die gesamte Gruppe N(jedes mogliche Manover aus N kann auch mit einer Kombination dieser beidenArten zusammmengestellt werden).

44

Naturlich ist Nc eine Untergruppe von Kc und Ne eine Untergruppe vonKe.

Wie wir bereits gesehen haben, gilt folgendes

7.1.10 Korollar

Die Gruppe Nc besteht aus denjenigen Elementen von Kc, fur die gilt, dass dieSumme der von ihnen bewirkten Umorientierungen der 8 Eckencubies gleichNull mod 3 ist.

Daraus folgt: Nc hat Index 3 in Kc und |Nc| = 37.

Erklarung: In der MengeKc kann man jeden Eckencubie beliebig verdrehen,in der Gruppe Nc gilt fur die von den Manovern erzeugten Positionen dieBedingung x1 + . . . + x8 = 0 mod 3. Sind die Verdrehungen von x1, . . . , x7

schon gewahlt, so ist der Wert fur x8 vorgegeben. Es gibt also 3 Nebenklassenvon Nc in Kc. Die eine ist Nc selbst, und die beiden anderen bestehen aus Nc

verknupft mit einer”in Nc nicht moglichen Verdrehung des letzten Cubies“

(wobei naturlich zu Beginn frei gewahlt werden kann, welches das letzte Cubieist).

Da |Nc| = |Kc| /[Kc : Nc] ⇒ |Nc| = 37.

Analog gilt

7.1.11 Korollar

Die Gruppe Ne besteht aus denjenigen Elementen von Ke, fur die gilt, dassdie Summe der von ihnen bewirkten Umorientierungen der 12 Kantencubiesgleich Null mod 2 ist.

Daraus folgt: Ne hat Index 2 in Ke und |Ne| = 211.

7.1.12 Korollar

Es gilt somit |N | = 37 · 211

Erinnern wir uns an die Gruppe MP aller Permutationen von Γ, die in Menthalten sind. Wir wissen bereits, dass |MP | = 1

2·8!·12! und dass MP

∼= M/N .Die Anzahl der Elemente von M/N (mit anderen Worten der Index von N

in M) multipliziert mit der Anzahl der Elemente von N ergibt die Anzahl derElemente von M . Daher gilt

45

7.1.13 Korollar

|M | = 12· 8! · 37 · 12! · 211.

Wie erwartet ist die Anzahl an moglichen R-Manovern, die unterschiedli-che Operationen bewirken, gleich der Anzahl aller moglichen R-Positionen desZauberwurfels.

Versteht man M als Untergruppe von Q, so sieht man (wenn man dieOrdnungen beider Gruppen vergleicht), dass [Q : M ] = 12.

Das heißt: Wenn man den Wurfel zerlegt und zufallig wieder zusammen-setzt, so ist die Chance, ihn aus dieser Position auf

”erlaubtem“ Wege losen

zu konnen, gleich 1:12.

7.2 Die Struktur der Rubikschen Gruppe

7.2.1 Rechengesetze und Untergruppen

Zwischen den Aquivalenzklassen in M und der Rubikschen Gruppe G be-steht,wie bereits erwahnt, der Isomorphismus, der jeder Klasse von R-Manoverndie von ihnen bewirkte Operation zuordnet.

Genauso besteht zwischenG und der Menge P aller moglichen R-Positionendie naturliche Bijektion G 3 g → g(IP ) ∈ P . Daher kann man jedes Gruppen-element g mit der Position g(IP ) = (ρ, σ, x, y) ∈ P identifizieren.

Dabei befindet sich das Eckencubie Nr. i im Cubizil ρ(i) und besitzt dieOrientierungskoordinate xi = x(i) (i = 1, . . . , 8). Nach Anwenden eines wei-teren Gruppenelements g∗ = (ρ∗, σ∗, x∗, y∗) ∈ G gelangt das Eckencubie Nr.i in das Cubizil ρ∗(ρ(i)) und bekommt die Orientierungskoordinate x(i) +x∗(ρ(i)) mod 3. Analoges gilt fur die Kantencubies.

Definieren wir die Addition in X = 0, 1, 28 und Y = 0, 112 komponen-tenweise mod 3 bzw. 2, so erhalten wir fur das Produkt zweier Elemente derRubikschen Gruppe G:

(ρ, σ, x, y)(ρ∗, σ∗, x∗, y∗) = (ρρ∗, σσ∗, x+ ρx∗, y + σy∗),

wobei wir hier x und y wie Permutationen behandeln und dementsprechendvon links nach rechts multiplizieren, sofern sie nicht, wie oben, auf ein konkretesCubie angewandt werden.

Weiters definieren wir folgende zwei Teilmengen von G:

G1 := g = (ρ, σ, x, y) ∈ G|x = 0, y = 0,G2 := g = (ρ, σ, x, y) ∈ G|ρ = 1, σ = 1,

46

wobei 0 fur das 8- bzw. 12-tupel (0,. . . ., 0) und 1 fur IS8 bzw. IS12 steht.G1 ist also die Menge der moglichen R-Operationen, die die Orientierung

der Cubies erhalten, und damit isomorph zu MP , wahrend G2 als die Mengealler moglichen R-Operationen, die alle Cubies an ihrem Platz lassen, isomorphzu N ist.

Daher gilt folgender Satz

7.2.2 Satz

(a) G1 ist eine Untergruppe, G2 ein Normalteiler von G.(b) G1

∼= (ρ, σ) ∈ S8 × S12| sgn(ρ) = sgn(σ), G2∼= Z7

3 × Z112 .

(c) G ist das semidirekte Produkt von G1 mit G2.Beweis: (a) Die Untergruppen-Eigenschaft von G1 und G2 ist trivial.G2 ist Normalteiler: Fur g = (ρ, σ, x, y) ∈ G ist g′ = (ρ′, σ′, ρ′(−x), σ′(−y)).

Daher gilt fur beliebiges g∗ = (1, 1, x∗, y∗) ∈ G2:

gg∗g′ = (ρ, σ, x, y)(1, 1, x∗, y∗)(ρ′, σ′, ρ′(−x), σ′(−y)) =

= (ρ, σ, x+ ρx∗, y + σy∗)(ρ′, σ′, ρ′(−x), σ′(−y)) =

= (ρρ′, σσ′, x+ ρx∗ + ρρ′(−x), y + σy∗ + σσ′(−y)) =

= (1, 1, ρx∗, σy∗) ∈ G2

.(b)Der erste Teil ist trivial.Sei nun (1, 1, (x1, . . . , x8), (y1, . . . , y12)) ∈ G2. Die Abbildung f : G2 → Z7

3×Z11

2 , f((1, 1, (x1, . . . , x8), (y1, . . . , y12)) = ((x1, . . . , x7), (y1, . . . , y11)) ∈ Z73×Z11

2

ist ein Isomorphismus.(c) Wegen (a) bleibt nur noch zu zeigen: G1 ∩ G2 = IG und G1G2 = G.

Letzteres gilt wegen (ρ, σ, x, y) = (ρ, σ, 0, 0)(1, 1, ρ′x, σ′y). q.e.d. (C. Bandelow,1981, S. 52)

Bemerkung

Genauso wie MP∼= M/N ist, gilt wegen oben erwahnter Isomorphismen, dass

G1∼= G/G2.Der Grad an Nicht-Kommutativitat von G ist relativ hoch, wie folgender

Satz bezeugt:

7.2.3 Satz

Das Zentrum Z(G) der Rubikschen Gruppe besteht lediglich aus IG und demvom Manover ((MRO)4BOLV )3(24) alle zwolf Kantencubies umorientierenden

47

Superflip (wobei BOLV eine 120 Drehung um die Eckenachse olv − uhr be-deuten soll, die die Seite o nach l, die Seite l nach v und die Seite v nach obringt).

Beweis: Sei g = (ρ, σ, x, y) ∈ Z(G). Aus Satz 3.2.3 folgt, dass das Zentrumder symmetrischen Gruppe Sn fur n ≥ 3 trivial ist. Da jedes ρ∗ ∈ S8 als ersteund jedes σ∗ ∈ S12 als zweite Koordinate eines Elementes von G vorkommt,folgt ρ = 1 und σ = 1, d.h. g ∈ G2.

Die Bedingung gg∗ = g∗g ∀g∗ ∈ G liefert weiters x + x∗ = x∗ + ρ∗x, alsox = ρ∗x ∀ρ∗ ∈ S8 und y + y∗ = y∗ + σ∗y, also y = σ∗y ∀σ∗ ∈ S12, d.h. xund y werden durch beliebige Permutationen auf sich selbst abgebildet. DieVerdrehungen aller Ecken- bzw- Kantencubies muss somit gleich sein, d.h. xund y sind konstant. Die Bedingung

∑8i=1 xi = 0(mod3) schließt x = 1 und

x = 2 aus. Daher besteht Z(G) nur aus den zwei Elementen IG = (1, 1, 0, 0)und (1, 1, 0, 1) (Superflip), wobei in letzterem y = 1 bedeutet, dass yi = 1,i = 1, . . . , 12. q.e.d. (C. Bandelow, 1981, S. 53)

7.2.4 Der Stabilisator

Sei G eine Gruppe, die auf einer Menge X operiert, φ die entsprechende Ope-ration. Fur jedes x ∈ X heißt die Untergruppe

stabG(x) = Gx = g ∈ G|φ(g, x) = x

der Stabilisator von x in G (D. Joyner, 2002, S. 91).

Bemerkung

stabM(rov) = 〈L,U,H〉.

7.2.5 Weitere Eigenschaften moglicher Positionen

Vorbemerkungen

1. Zwischen den R-Operationen g ∈ G∗ und den R-Positionen p ∈ P ∗ be-steht naturlicherweise die Bijektion G∗ 3 g ↔ p = g(IP ) ∈ P ∗. Dasheißt, g ist genau dann moglich, wenn p = g(IP ) moglich ist.

2. Die r-te Potenz eines Ecken-r-Zyklus mit Vorzeichen + bzw. - bewirkt ei-ne Rechts- bzw. Linksdrehung aller r am Zyklus beteiligten Eckencubies.Die r-te Potenz eines Kanten-r-Zyklus mit Vorzeichen orientiert alle amZyklus beteiligten Kantencubies um.

Eckenzyklen mit Vorzeichen +, - oder mit keinem Vorzeichen haben un-terschiedliche r-te Potenzen (namlich alle Cubies nach rechts oder links

48

gedreht bzw. die identische Abbildung). Da jedoch zwei verschiedene Zy-klendarstellungen desselben r-Zyklus dieselbe r-te Potenz haben, mussdas Vorzeichen eines Zyklus unabhangig von dessen Darstellung sein.Dieselbe Feststellung gilt fur Kantenzyklen.

Wir konnen daher von orientierungstreuen Ecken- bzw. Kantenzyklen,von rechtsdrehenden und von linksdrehenden Eckenzyklen sowie von um-orientierenden Kantenzyklen sprechen.

Satz

Eine R-Operation ist genau dann moglich, wenn die folgenden 3 Bedingungenerfullt sind:

1. Die Gesamtanzahl der Zyklen gerader Lange (Ecken- und Kantenzy-klen)ist gerade.

2. Die Anzahl der rechtsdrehenden Eckenzyklen ist gleich der Anzahl derlinksdrehenden Eckenzyklen mod 3.

3. Die Anzahl der umorientierenden Kantenzyklen ist gerade.

Beweis: (1) Wir wissen bereits, dass eine R-Position genau dann moglich ist,wenn die in der 20-elementigen Menge aller Ecken- und Kantencubies bewirktePermutation gerade ist. Ein Zyklus gerader Lange ist ungerade. Um insgesamteine gerade Permutation zu erhalten, muss daher die Gesamtanzahl solcherZyklen gerade sein.

(2) Diese Bedingung gilt, da ein rechts- bzw. linksdrehender bzw. orientie-rungstreuer Eckenzyklus die Summe der Orientierungskoordinaten xi der amZyklus beteiligten Cubies um -1 bzw. um +1 bzw. um 0 mod 3 andert.

(3) Es gilt die analoge Feststellung: Ein umorientierender Kantenzyklusandert die Summe der Orientierungskoordinaten yj der am Zyklus beteiligtenCubies um 1 mod 2 (C. Bandelow, 1981, S. 51).

Korollar

Jede Position, die aus einer moglichen Position durch Vertauschen zweierEckencubies (beliebige Orientierung), durch Vertauschen zweier Kantencubies(beliebige Orientierung), durch Verdrehen eines einzelnen Eckencubies oderdurch Umorientieren eines einzelnen Kantencubies entsteht, ist unmoglich (C.Bandelow, 1981, S. 51).

49

7.3 Bemerkungen zur Transitivitat im

Rubik Cube

7.3.1 Definition

Sei G eine Gruppe, die auf einer Menge X operiert. Man nennt diese Operationφ von G auf X k-tupel-transitiv, wenn es fur jedes Paar geordneter k-Tupel(x1, x2, . . . , xk), (y1, y2, . . . ., yk) von Elementen aus X ein g ∈ G gibt, sodassyi = φ(g, xi) = xg

i fur jedes 1 ≤ i ≤ k (D. Joyner, 2002, S. 139).

Lemma Sei X eine G-Menge. Wenn k ≥ 2, dann ist X genau dann k-transitiv, wenn fur jedes x ∈ X die Menge X − x, auf der der StabilisatorGx von x operiert, (k − 1)-transitiv ist.

Beweis: Angenommen, X ist k-transitiv. Seien (x1, . . . , xk−1) und (y1, . . . ,yk−1) (k − 1)-Tupel unterschiedlicher Elemente von X − x. Dann gibt esfolglich ein g ∈ G mit g(x) = x (sodass g ∈ Gx) und g(xi) = yi ∀i ≥ 1.

Seien umgekehrt (x1, . . . , xk) und (y1, . . . , yk) zwei k-Tupel unterschiedli-cher Elemente von X. Nach Voraussetzung gibt es ein g ∈ Gxk

mit g(x1, . . . ,xk−1, xk) = (y1, . . . , yk−1, xk) und es gibt ein h ∈ Gy1 mit

h(y1, y2, . . . , yk−1, xk) = (y1, y2, . . . , yk−1, yk).

Daher bildet hg ∈ G das Tupel (x1, . . . , xk) auf (y1, . . . , yk) ab (J. J. Rotman,1995, S. 250).

Satz Fur jedes n operiert die Symmetrische Gruppe Sn n-transitiv auf1, 2, . . . , n, und fur jedes n ≥ 3 operiert die Alternierende Gruppe An (n−2)-transitiv auf X = 1, 2, . . . , n.

Beweis: Die erste Aussage ist offensichtlich, da die Sn jede Permutationvon X enthalt. Die zweite Aussage beweisen wir durch Induktion fur n ≥ 3.Fur n = 3 operiert A3 = 〈(1, 2, 3)〉 transitiv auf X = 1, 2, 3. Fur n > 3ist fur jedes i mit 1 ≤ i ≤ n der Stabilisator (An)i von i isomorph zu An−1.Laut Induktionsvoraussetzung operiert er (n−3)-transitiv auf X−i. Damitoperiert An nach Lemma 7.3.1 (n− 2)-transitiv auf X (J. J. Rotman, 1995, S.251 ff.).

50

7.3.2 Satz

Sei k > 5 und G eine Gruppe, die k-transitiv auf einer endlichen Menge Xoperiert. Dann ist G isomorph zu Sm oder zu An fur ein m ≥ k oder einn ≥ k + 2.

Beweis: Dieser Satz kann mit Hilfe der Klassifikation der endlichen einfa-chen Gruppen bewiesen werden, vergleiche die Ubersichtsarbeit von P. Came-ron (1981).

Aus obigem Satz und aus der Tatsache, dass beim Zauberwurfel insgesamt nurgerade Permutationen der Cubies moglich sind, folgt

7.3.3 Korollar

1. Angenommen c1, . . . , c6 sind beliebige 6 verschiedene Eckencubies undc′1, . . . , c

′6 irgendwelche anderen 6 verschiedenen Eckencubies. Dann gibt

es ein Element der kleinen Manovergruppe M , das alle Kantencubies fixlasst und ci nach c′i schickt (∀i = 1, . . . , 6). M operiert damit 6-transitivauf der Menge der Eckencubies ohne die Kantencubies zu bewegen.

2. Angenommen c1, . . . , c8 sind 8 verschiedene Eckencubies des Zauberwurfels.Seien c′1, . . . , c

′8 8 weitere verschiedene Eckencubies. Dann gibt es ein Ele-

ment der kleinen Manovergruppe M , das ci nach c′i schickt ∀i = 1, . . . , 8(und dabei eventuell auch Kantencubies bewegt).

M operiert damit 8-transitiv auf der Menge der Eckencubies (wobei hierbei den Manovern auch Kantencubies bewegt werden durfen).

3. Ebenso operiert M 10-transitiv auf der Menge der Kantencubies ohnedie Eckencubies dabei zu bewegen, und

4. M operiert 12-transitiv auf der Menge der Kantencubies, wobei nun beiden Manovern auch Eckencubies bewegt werden durfen. (D. Joyner, 2002,S. 139)

51

Kapitel 8

Die Untergruppen desZauberwurfels

8.1 Zyklische Gruppen

8.1.1 Einfache Beispiele:

〈V 〉 enthalt die vier Elemente V, V 2, V ′, I. 〈V 2〉 enthalt die zwei Elemente V 2, I.

Die Ordnung der Elemente der Rubikschen Gruppe kann aus der Zyklendar-stellung abgelesen werden: Sie ist das kleinste gemeinsame Vielfache der mit 3(drehende Eckenzyklen) bzw. 2 (umorientierende Kantenzyklen) bzw. 1 (orien-tierungstreue Zyklen) multiplizierten Zyklenlangen. Es treten laut C. Bandelow(1981, S. 56) genau 73 verschiedene Ordnungen auf, und die maximale Ord-nung ist 2 · 2 · 3 · 3 · 5 · 7 = 1260.

Als Beispiel fur eine R-Operation dieser Ordnung dient das von J.B.Butler(in C. Bandelow, 1981, S. 56) angegebene Manover

RO2U ′HU ′(5) →

(−ovl, lho, rvo)(+ohr, vul, uvr, rhu, luh)

(+ov, lh, ur, vr, ol, or, ho)(+ul, rh)(uv, uh).

Da die Ordnung von G endlich ist, erzeugt jedes Element aus G eine (end-liche) zyklische Untergruppe von G. Das heißt, wenn man auf den geordnetenWurfel ein beliebiges Manover (und damit eine beliebige Operation) anwendet,so gelangt man, nach fortwahrender Anwendung ein und desselben Manoversirgendwann wieder in den geordneten Anfangszustand zuruck. Dies kann aller-dings einige Zeit dauern, da selbst das einfache Manover V R (und ebenso XY ,wenn X, Y zwei aneinander

”anstoßende“ Randscheibenzuge sind) die relativ

große Ordnung 105 hat.

52

8.1.2 Bemerkungen

• Konjugation andert die Ordnung eines Elements nicht, d.h. wenn P dieOrdnung n hat und Q ein beliebiges anderes Manover ist, dann hatQPQ−1 ebenfalls die Ordnung n (denn (QPQ−1)m = QPmQ−1 ∀m ≥ 0).

• Die Ordnung jeder Untergruppe von G (und damit auch die Ordnungjeder zyklischen Gruppe 〈ma〉 muss nach dem Satz von Lagrange dieOrdnung von G (= 227 · 314 · 53 · 72 · 11) teilen.

Daher wird man z.B. niemals Manover finden, deren Ordnung durch 13teilbar ist (Tom Davis, 2006, S. 34).

8.2 Bahnen, Stabilisatoren und der Satz von

Sylow

Wir folgen in diesem Abschnitt M. Artin (1998, S. 198 ff.).

8.2.1 Definition

Man kann (wie wir bereits wissen) eine Menge X, auf der eine Gruppe Goperiert, in Bahnen zerlegen.

Ist x ein Element von X, dann ist die Bahn Bx von x in X

Bx = y ∈ X|y = g(x) fur ein geeignetes g ∈ G.

Bemerkung

Wie wir bereits gesehen haben (Satz 4.2.3) sind die Bahnen einer Gruppen-operation die Aquivalenzklassen der Aquivalenzrelation

x ≡ y ⇔ y = g(x) fur ein g ∈ G.

Daher gilt: X ist die Vereinigung disjunkter Bahnen B1, . . . , Bk und |X| =|B1|+ |B2|+ . . .+ |Bk|.

Die Anzahl der Elemente der Bahn eines Elementes x ∈ X heißt Lange derBahn.

8.2.2 Satz

Seien X eine G-Menge und x ∈ X mit Stabilisator H und Bahn Bx. Dann gibtes eine bijektive Abbildung ϕ : G/H → Bx, ϕ(aH) = a(x).

Fur jedes g ∈ G gilt: ϕ(gH) = g(ϕ(H)). Damit ist ϕ mit den Operationenvon G vertraglich.

53

Beweis: Zu zeigen ist, dass die Zuordnung gH → g(x) eine Abbildungdefiniert. Seien a, b ∈ G mit aH = bH. Zu zeigen: a(x) = b(x).

Es gilt genau dann aH = bH, wenn b = ah fur ein geeignetes h ∈ H. Ausb = ah folgt dann, wie gewunscht, b(x) = ah(x) = a(x), weil h das Element xfestlasst.

ϕ ist surjektiv: Die Bahn von x besteht aus den Elementen g(x) und ϕschickt gH nach g(x). Also gibt es fur jedes Element der Bahn von x ein ent-sprechendes Element aus dem Raum der Nebenklassen G/H, das auf ersteresabgebildet wird.

ϕ ist injektiv: Aus a(x) = b(x) folgt x = a−1(b(x)), und da H der Stabili-sator von x ist, gilt a−1b = h ∈ H. Also ist b = ah und daher aH = bH.

q.e.d.

8.2.3 Bahnformel

Sei X eine G-Menge und Gx der Stabilisator von x. Fur jedes x ∈ X gilt:

|G| = |Gx| |Bx|, oder (Ordnung von G)=(Ordnung des Stabilisators)(Langeder Bahn).

Aus obigem Satz folgt, dass |Bx| = |G/Gx|. Die Bahnformel folgt nun ausdem Satz von Lagrange.

Die Anzahl der Elemente von G besteht damit aus allen Elementen, diex auf sich selbst abbilden kombiniert mit allen Elementen, die x auf andereElemente aus X abbilden.

Definition

Die Gruppe G operiere auf X und U sei eine Teilmenge von X. Der Stabilisatorvon U ist die Menge der Gruppenelemente g mit g(U) = U .

8.2.4 Satz

Sei H eine Gruppe, die auf einer Menge X operiere, und sei U eine Teilmengevon X. Die Gruppe H stabilisiert U genau dann, wenn U eine Vereinigungvon H-Bahnen ist.

Beweis: Die H-Bahn eines Elementes u ∈ U besteht aus den Elementen derForm h(u). DamitH die Menge U stabilisiert, muss U somit aus denH-Bahnenseiner Elemente bestehen.

54

8.2.5 Satz

Sei U eine endliche Teilmenge einer Gruppe G. Die Ordnung des Stabilisa-tors Stab(U) bezuglich der Operation der Linksmultiplikation ist ein Teiler derAnzahl der Elemente von U .

Beweis: Sei H der Stabilisator von U . Nach obigem Satz ist U eine Vereini-gung von H-Bahnen. Diese sind die Rechtsnebenklassen Hu. Daher ist U eineVereinigung von Rechtsnebenklassen, und die Anzahl der Elemente von U istein Vielfaches von |H|.

8.2.6 Erster Satz von Sylow

Sei G eine Gruppe der Ordnung n und p eine Primzahl, die n teilt. Mit pe

bezeichnen wir die großte Potenz von p, die als Faktor in n vorkommt, sodassgilt:

n = pem

fur eine naturliche Zahl m, die nicht durch p teilbar ist.Dann hat die Gruppe G eine Untergruppe der Ordnung pe.

Beweis: SeiX die Menge aller Teilmengen vonG, die pe Elemente enthalten.Eine dieser Teilmengen ist die gesuchte Untergruppe. Wir werden jedoch zei-gen, dass eine dieser Teilmengen einen Stabilisator der Ordnung pe hat, und daein Stabilisator stets eine Gruppe bildet, ist dieser die gesuchte Untergruppe.

Dazu benotigen wir folgendes

Lemma Die Anzahl der Teilmengen der Ordnung pe in einer Menge mitn = pem Elementen (wobei m nicht durch p teilbar ist) wird durch den Bino-mialkoeffizienten

N =

(npe

)= n(n−1)...(n−k)...(n−pe+1)

pe(pe−1)...(pe−k)...1

angegeben. Diese Zahl N ist nicht durch p teilbar.

Beweis: Der erste Teil ist klar. Zu zeigen bleibt, dass N nicht durch p teilbarist: Ware N durch p teilbar, so musste p im Zahler ofter enthalten sein als imNenner. Dies ist aber nicht der Fall. Zahler und Nenner enthalten offensichtlichgleich viele Faktoren. Teilt p einen Faktor (n− k) des Zahlers, so teilt p auchden entsprechenden Faktor (pe − k) des Nenners, und zwar gleich oft, denn: pteilt n - daher teilt p (n − k) genau dann, wenn p k teilt. Sei k also von derForm k = pil, wobei l nicht durch p teilbar ist. Da k < pe ist, gilt i < e. Also

55

sind (n − k) und (pe − k) beide durch pi teilbar, aber nicht durch pi+1. Einmoglicher gemeinsamer Faktor pi kurzt sich daher aus dem gesamten Bruchstets hinaus, und N ist damit nicht durch p teilbar. q.e.d.

Wir zerlegen nun X in Bahnen fur die Operation der Linksmultiplikationund erhalten damit fur die Anzahl N der Elemente von X:

N = |X| =∑

BahnenB |B|.

Da p die Zahl N nicht teilt, gibt es eine Bahn, deren Lange nicht durch pteilbar ist. Sei dies die Bahn der Teilmenge U . Da U ∈ X gilt |U | = pe. Nachobigem Satz ist damit |Stab(U)| eine Potenz von p.

Die Bahnformel liefert:

|Stab(U)| · |BU | = |G| = pem.

Da |BU | nicht durch p teilbar ist, folgt |Stab(U)| = pe. Dieser Stabilisatorist die gesuchte Untergruppe.

q.e.d.

8.2.7 Korollar

Teilt eine Primzahl p die Ordnung einer endlichen Gruppe G, so enthalt G einElement der Ordnung p.

Beweis: Sei H eine Untergruppe der Ordnung pe und x 6= 1 ein Elementvon H. Dann ist nach dem Satz von Lagrange die Ordnung von x ein Teilervon pe, also gleich pr fur ein r mit 0 ≤ r ≤ e. 〈x〉 ist zyklisch mit Ordnung pr,und da p|pr ∃y ∈ 〈x〉 (⊆ H) mit | 〈y〉 | = p.

8.3 Untergruppen des Zauberwurfels

8.3.1 Ordnungen in der Rubikschen Gruppe

Da die Ordnung der Rubischen Gruppe 227 · 314 · 53 · 72 · 11 betragt, wissenwir, dass es nach Korollar 8.2.7 eine zyklische Untergruppe der Ordnung 11geben muss. Tom Davis (2006, S. 35) konnte mit seinem Computerprogramm

”Rubik“ ein Manover dieser Ordnung ausmachen, namlichR′O′V HO′V ′UHOUH ′O′RRU ′LLO′LLU ′LLO′RR.

8.3.2 Gruppengeneratoren

Offensichtlich ist die durch die Manover V,H, L,R,O, U erzeugte Gruppe diegesamte kleine ManovergruppeM . WegenRL′V 2H2RL′·O·LR′H2V 2LR′(13) ∼=U (D.J.Benson u.a. in C. Bandelow, 1981, S. 54) wird M bereits von denManovern R, L, V , H und O erzeugt und die Rubiksche Gruppe G ebenfallsbereits von den 5 durch R, L, V , H und O bewirkten Operationen erzeugt.

56

Proposition

Die kleine Manovergruppe M wird nicht von nur 4 elementaren Randschei-benzugen erzeugt.

Beweis: Stehen die Scheiben, auf die man verzichten mochte, aufeinandersenkrecht, so ist der Kantencubie, den sie begrenzen, unbeweglich. Liegen sieeinander gegenuber, wie z.B. R und L, so konnen keine Kantencubies umori-entiert werden. Man kann sich z.B. uberlegen, dass das linke Farbplattchen desKantencubies lv nie auf die vordere oder hintere Wurfelseite gelangen kann.

Jedes R-Manover, das Kantencubies umorientiert, enthalt mindestens drei90-Randscheibenzuge, und zwar fur jedes der drei Paare gegenuberliegenderRandscheiben einen 90-Zug mit einer der beiden Scheiben. (C. Bandelow,1981, S. 54 ff.)

Proposition

Die symmetrische Gruppe Sn wird von zwei Elementen erzeugt.Beweis: Wir wissen, dass die Transpositionen der Form (1,i) (i=2, . . . , n)

Sn erzeugen. Da fur 2 ≤ i ≤ n gilt (1, i) = (2, . . . , n)n+1−i(1, 2)(2, . . . , n)i−2,erzeugen bereits die beiden Zyklen (1, 2) und (2, . . . , n) die ganze Gruppe (C.Bandelow, 1981, S. 55).

Bemerkung

Fur die Rubiksche Gruppe G gibt es ebenfalls ein 2-elementiges Erzeugenden-system:

• OHLOL′O′H ′(7) → (−ovl, ohr)(+olh)(+oh, or)(+ol)

• R2V LU ′R′(5) →

(orv, hur, lvu, luh, lho, lov, vru)(ov, ru, rv, ro, vu, uh, hr, lu, lh, lo, lv).

Das bedeutet, dass diese beiden Manover genugen mussten, um den Wurfelzu losen! (C. Bandelow, 1981, S. 55)

8.3.3 Symmetriegruppen

Eine Symmetrieabbildung eines Objekts K ist ein Isomorphismus des Raum-es bzw. der Ebene, der K in sich uberfuhrt. Es handelt sich hierbei um alldiejenigen Permutationen der Punktmenge, die alle geometrisch relevanten Ei-genschaften erhalten, wie z.B. den Abstand. In der reellen Ebene sind dasSpiegelungen, Drehungen, Verschiebungen und Gleitspiegelungen. Die Menge

57

der Symmetrieabbildungen einer Menge K von Punkten wird mit Sym(K) be-zeichnet. Sie bildet bezuglich der Hintereinanderausfuhrung von Abbildungeneine Gruppe.

Sei R ein regelmaßiges n-Eck (n > 2). Dann wird Sym(R) von einer Rota-tion um 2π/n um den Mittelpunkt des n-Ecks und einer Spiegelung an einerbeliebigen Symmetrieebene, die R in zwei Halften teilt, erzeugt (Beutelspacher,2001, S. 231 bzw. D. Joyner, 2002, S. 68).

8.3.4 Die”Two Squares“ Gruppe

Es handelt sich um die Gruppe H = 〈R2, O2〉, die das hilfreiche Manover

(R2O2)3(6) → (rv, rh)(ov, oh)

zum Vertauschen zweier Paare von Kantencubies beinhaltet (D. Joyner, 2002,S. 81).

Wir wollen nun in Anlehnung an T. Davis (2006, S. 35 ff.) folgende Notationeinfuhren: φ = O2 und ρ = R2. Klarerweise gilt φ2 = ρ2 = 1 und man findetleicht heraus, dass die Elemente (φρ) und (ρφ) Ordnung 6 haben, d.h. (φρ)6 =(ρφ)6 = 1.

Als mogliche Gruppenmitglieder kommen nur die folgenden 18 Moglichkei-ten in Betracht:

1 (ρφ) (ρφ)2 (ρφ)3 (ρφ)4 (ρφ)5

φ φ(ρφ) φ(ρφ)2 φ(ρφ)3 φ(ρφ)4 φ(ρφ)5

ρ (ρφ)ρ (ρφ)2ρ (ρφ)3ρ (ρφ)4ρ (ρφ)5ρDie ρs und φs mussen alternieren, da man sie sonst zur Identitat kurzen

kann. Ebenso kann (ρφ) mit keiner hoheren Potenz als 5 vorkommen. Multipli-ziert man irgendein Element obiger Tabelle mit ρ oder φ von links oder rechts,entsteht daraus durch Kurzen ein anderes Element der Tabelle.

Das heißt, die Große der erzeugten Untergruppe ist hochstens 18.Die Liste besitzt allerdings 6 Duplikate, sodass die tatsachliche Ordnung

der Untergruppe 12 ist:

1. φ(ρφ)2 = (ρφ)3ρ, da beide Elemente Inverse von (ρφ)3ρ sind und dasInverse eines Gruppenelements eindeutig bestimmt ist.

Beweis:

(ρφ)3ρ · φ(ρφ)2 = (ρφ)6 = 1 sowie

(ρφ)3ρ · (ρφ)3ρ = ρφρφρφρρφρφρφρ =

ρφρφρφφρφρφρ = ρφρφρρφρφρ = . . . = ρρ = 1.

2. (ρφ)5ρ = φ, da beide Elemente Inverse von φ sind, denn:

φ · φ = φ2 = 1 und

(ρφ)5ρ · φ = (ρφ)6 = 1

58

3. φ(ρφ)5 = ρ, da beide Elemente Inverse von ρ sind (Beweis analog).

4. φ(ρφ)3 = (ρφ)2ρ, da beide Elemente Inverse von φ(ρφ)3 sind:

(ρφ)2ρ · φ(ρφ)3 = (ρφ)6 = 1

und

φ(ρφ)3 · φ(ρφ)3 = φ(ρφ)(ρφ)(ρφ)φ(ρφ)(ρφ)(ρφ)

= φ(ρφ)(ρφ)ρ(ρφ)(ρφ)(ρφ)

= φ(ρφ)(ρφ)φ(ρφ)(ρφ) = . . . = 1

5. φ(ρφ) = (ρφ)4ρ, da beide Elemente Inverse von φ(ρφ) sind:

φ(ρφ) · φ(ρφ) = φρρφ = . . . = 1

und(ρφ)4ρ · φ(ρφ) = (ρφ)6 = 1

6. φ(ρφ)4 = (ρφ)ρ (Beweis analog)

Folgende 12 Elemente genugen somit, um die Gruppe zu erzeugen:

1 (ρφ) (ρφ)2 (ρφ)3 (ρφ)4 (ρφ)5

φ φ(ρφ) φ(ρφ)2 φ(ρφ)3 φ(ρφ)4 φ(ρφ)5

Um mehr uber die Gruppe herauszufinden, nummerieren wir die Ecken desZauberwurfels entsprechend nachfolgender Abbildung 8.1.

59

Abbildung 8.1: Nummerierung der Ecken des Zauberwurfels (Quelle: D.Joyner,2002, S. 82)

Das Manover R2 verursacht dann die Permutation (1, 4)(2, 3), wahrend O2

die Transpositionen (4, 5)(3, 6) bewirkt.Bezeichnen wir nun, wie unten dargestellt (Abb. 8.2) die Ecken eines Sechs-

ecks, dann ist die Permutation (1, 4)(2, 3) einfach die Spiegelung an der Sym-metriegeraden, die 5 und 6 enthalt.

Abbildung 8.2: (Quelle: D.Joyner, 2002, S. 82)

Ebenso ist (4, 5)(3, 6) die Spiegelung an der Symmetriegeraden, die 1 und2 enthalt. Diese beiden Reflexionen erzeugen die Symmetriegruppe des Sechs-ecks. Somit ist die

”Two Squares“ Gruppe isomorph zur Symmetriegruppe des

Sechsecks.

60

8.4 Cayley-Graphen

8.4.1 Allgemeine Definitionen

Ein Graph ist ein Paar abzahlbarer Mengen (V,E), wobei

• V eine abzahlbare Menge alleinstehender Elemente ist, die Ecken (Ver-tices) genannt werden und

• E eine Teilmenge aller ungeordneten Paare v1, v2|v1, v2 ∈ V, v1 6=v2 ist. Die Elemente von E werden Kanten genannt.

Den Graphen zeichnet man, indem man die Ecken, die zur selben Kantegehoren, verbindet.

Ein gerichteter Graph ist ein Paar abzahlbarer Mengen (V,E), wobei

• V eine abzahlbare Menge von Ecken ist und

• E eine Teilmenge aller geordneten Paare (v1, v2)|v1, v2 ∈ V, v1 6= v2,genannt Kanten ist.

Einen gerichteten Graphen zeichnet man, indem man die Ecken, die zurselben Kante (v1, v2) gehoren, mit einem Pfeil verbindet, der bei v1 beginntund nach v2 hin zeigt.

Wenn e = v1, v2 zu E gehort, sagt man, dass e eine Kante von v1 zuv2 (oder von v2 zu v1)ist und dass v2 und v1 Nachbarn oder im Graphenbenachbart sind.

Sind v und w Ecken, dann ist ein Pfad von v nach w eine endliche Folgevon Kanten, die bei v beginnen und bei w enden:

e0 = v, v1, e1 = v1, v2, . . . . ., en = vn, w

Gibt es einen Pfad von v nach w, so sagt man, dass v mit w verbunden ist.Ein Graph (V,E) heißt verbunden, falls jedes Paar von Ecken verbunden

ist.Die Anzahl von Kanten, die aus einer Ecke v herausfuhren, heißt Grad

(oder Wertigkeit) von v, symbolisch grad(v).Sind v und w Ecken, die in dem Graphen (V,E) miteinander verbunden

sind, so definiert man die Distanz zwischen v und w (d(v, w)) alsd(v, w) = min #Kanten in einem Pfad von v nach w, wenn v, w ∈ V

verbunden sind.Wenn v und w nicht verbunden sind, setzt man d(v, w) = ∞.Der Durchmesser eines Graphen (diam((V,E))) ist die großtmogliche Di-

stanz:

diam((V,E))=maxv,w∈V d(v, w).

(D. Joyner, 2002, S. 115 ff.)

61

8.4.2 Definitionen zu Cayley-Graphen

Sei G = 〈g1, g2, . . . , gn〉 eine Permutationsgruppe. Der Cayley Graph von Gmit Bezug auf X = g1, g2, . . . , gn ist der Graph (V,E), dessen Ecken V dieElemente von G sind und dessen Kanten durch folgende Bedingung bestimmtsind:

Wenn x und y zu V = G gehoren, dann gibt es genau dann eine Kante vonx nach y, wenn y = x · gi oder x = y · gi fur ein i ∈ 1, 2, . . . , n.

Der gerichtete Cayley Graph von G mit Bezug auf X = g1, g2, . . . , gnist der gerichtete Graph (V,E), dessen Ecken V die Elemente von G sind unddessen Kanten durch folgende Bedingung bestimmt sind:

Wenn x und y zu V = G gehoren, dann gibt es genau dann eine Kante vonx nach y, wenn y = x · gi fur ein i ∈ 1, 2, . . . , n.

Lemma

Der Cayley-Graph einer Permutationsgruppe ist verbunden.Beweis: Seien x, y ∈ G = 〈g1, g2, . . . , gn〉. Dann gilt y = x(x−1·y). Da x−1·y ∈ G∃a1, . . . , ak ∈ g1, g2, . . . , gn, g

−11 , g−1

2 , . . . , g−1n , sodass x−1 · y = ak · . . . · a1.

Damit gilt y = x ·ak · . . . ·a1, und e0 = x, x ·ak bildet eine Kante, da entwederak = gi oder ak = g−1

i fur irgendein i ∈ 1, 2, . . . , n (und die Bedingung, dassx und y eine Kante bilden, lautet y = x · gi oder y = x · g−1

i ).Mit Induktion folgt dann, dass auch e1 = x · ak, x · ak · ak−1, . . . , ek−1 =

x · ak · . . . · a2, y Kanten sind, die insgesamt einen Pfad bilden, der x und yverbindet.

q.e.d. (D. Joyner, 2002, S. 117 ff.)

8.4.3 Lemma

Sei ΓG = (V,E) der Cayley-Graph zur PermutationsgruppeG = 〈g1, g2, . . . , gn〉(wobei o.B.d.A. gi 6= gj fur i 6= j gelten soll), und sei

N =∣∣g1, g2, . . . , gn, g

−11 , g−1

2 , . . . , g−1n

∣∣ .Dann gilt ∀v ∈ V : grad(v)=N .

Beweis: Angenommen nicht. Dann gibt es ein v ∈ V = G mit(i) grad(v) < N oder(ii) grad(v) > N .Aus der Definition eines Cayley-Graphen ergibt sich, dass fur jedes h ∈

g1, g2, . . . , gn, g−11 , g−1

2 , . . . , g−1n die Menge v, v · h eine Kante von ΓG ist.

• Falls r = grad(v) > N , dann gibt es unterschiedliche Elemente v1, . . . , vr ∈V mit v = vi · hi ∀1 ≤ i ≤ r, wobei h1, . . . , hr unterschiedliche Elementeaus g1, g2, . . . , gn, g

−11 , g−1

2 , . . . , g−1n sind (waren z.B. die his nicht alle

62

unterschiedlich, so wurde gelten v = vi · hi und v = vj · hi ⇒ vi = vj undes handelt sich bei v, vi und v, vj um dieselbe Kante.).

Es musste also r > N unterschiedliche Elemente aus einer Menge mit NElementen geben, was auf einen Widerspruch fuhrt.

• Falls r = grad(v) < N , gibt es unterschiedliche

hi, hj ∈ g1, g2, . . . , gn, g−11 , g−1

2 , . . . , g−1n ,

sodass v ·hi = v ·hj, denn: v ·hi und v ·hj sind beides Gruppenelemente,die per Definition des Cayley-Graphen mit v eine Kante bilden mussen.Wenn weniger als N Kanten vorhanden sein sollen, mussen z.B. obigeKanten zusammenfallen, was nur moglich ist, wenn zwei unterschiedlicheElemente v · hi und v · hj gleich sind. Widerspruch.

(D. Joyner, 2002, S. 117)

8.4.4 Cayley-Graphen des Rubik Cube

Bei gerichteten Cayley-Graphen wird ein Pfeil von einem Gruppenelement zumnachsten gezogen, wenn ein Element des Generators der Gruppe von jenemGruppenelement zum nachsten fuhrt.

Beispiel 1: Abbildung 8.3 zeigt den Cayley-Graphen der Gruppe 〈V 〉.

Abbildung 8.3: Cayley-Graph der Gruppe 〈V 〉 (Quelle: T. Davis, 2006, S. 37)

63

Beispiel 2: Der Cayley-Graph der oben untersuchten Gruppe 〈ρ, φ〉 ist schonetwas interessanter: Beginnend bei der Identitatsabbildung 1 kann jedes Ele-ment aus dem davor erhaltenen Element durch Multiplikation mit ρ oder φvon links oder rechts erhalten werden. Da ρ2 = φ2 = 1 wird durch solch eineMultiplikation offensichtlich manchmal ein ρ oder φ wieder eliminiert, aber imEndeffekt bekommt man auf diese Weise eine komplette Liste aller Gruppen-mitglieder.

Abbildung 8.4 zeigt den Cayley-Graphen dieser Gruppe. Elemente, die aus-einander durch die Multiplikation mit ρ erzeugt werden konnen, sind mit ein-fachen Pfeilen verbunden, wird stattdessen φ benotigt, so ist dies durch einenDoppellinienpfeil illustriert.

Abbildung 8.4: Cayley-Graph der Gruppe 〈ρ, φ〉 (Quelle: T. Davis, 2006, S. 37)

Beispiel 3: Sei M = 〈R,L,O, U, V,H〉 die kleine Manovergruppe (identifi-ziert mit der Rubikschen Gruppe!). Jede Position des Wurfels entspricht einemElement dieser Gruppe (namlich dem Manover, das vom Ausgangszustand zudieser Position fuhrt). In anderen Worten entspricht jede Position des Wurfelseiner Ecke des Cayley-Graphen. Nach obigem Lemma gilt fur jede Ecke v, dassgrad(v) = |R,L,O, U, V,H,R−1, L−1, . . . , H−1| = 12.

Eine Losung des Zauberwurfels ist damit einfach ein Pfad im Cayley-Graphen von der Ecke der derzeitigen Position des Wurfels ausgehend zu derEcke der Identitatsabbildung, die der geordneten Position entspricht.

Die Anzahl der Zuge des kurzest moglichen Losungsweges ist die Distanzzwischen der Ecke der derzeitigen Position und der der Ausgangsposition.

Der Durchmesser des Cayley-Graphen ist die Anzahl der 90-Zuge des best-moglichen Losungsweges von der am meisten

”ungeordneten“ Position ausge-

hend.

64

8.5 Die Mittelscheibengruppe

8.5.1 Mathematischer Einschub - Die Symmetriegruppedes Wurfels

Die Gruppe aller Symmetrieabbildungen eines Wurfels enthalt nach Beutel-spacher (2001, S. 232) folgende 24 Abbildungen:

• die Identitat

• drei Drehungen um 90 um eine Gerade, die zwei gegenuberliegende Fla-chenmitten verbindet,

• drei Drehungen um −90 um eine Gerade, die zwei gegenuberliegendeFlachenmitten verbindet,

• drei Drehungen um 180 um eine Gerade, die zwei gegenuberliegendeFlachenmitten verbindet,

• sechs Drehungen um 180 um eine Gerade, die zwei gegenuberliegendeKantenmitten verbindet,

• vier Drehungen um 120 um eine Raumdiagonale,

• vier Drehungen um 240 um eine Raumdiagonale.

Proposition Die Gruppe G der Symmetrieabbildungen eines Wurfels ist iso-morph zur S4.

Beweis: Bei einer Bewegung des Wurfels gehen die vier Raumdiagonalenwieder in die Raumdiagonalen uber. Jeder Bewegung ist somit eine Permu-tation der Raumdiagonalen, nach deren Nummerierung von 1 bis 4 also einElement der S4, zugeordnet. Die Abbildung ist somit injektiv und G isomorphzu einer Teilmenge der S4. Da aber |G| = |S4| = 4! = 24, gilt G ist isomorphzu S4. q.e.d. (C. Bandelow, 1981, S. 41)

Proposition Die Gruppe der Symmetrieabbildungen eines Wurfels wird be-reits von den Drehungen um 90 um eine Gerade, die zwei gegenuberliegendeFlachenmitten verbindet, erzeugt.

Beweis: Wir nummerieren die Raumdiagonale, die das Eckencubie orv mitdem Eckencubie uhl verbindet mit 1, die Raumdiagonale, die das Eckencu-bie hro mit dem Eckencubie ulv verbindet mit 2, die Raumdiagonale, diedas Eckencubie hol mit dem Eckencubie uvr verbindet mit 3 und die Raum-diagonale, die das Eckencubie ovl mit dem Eckencubie urh verbindet mit

65

4. Es genugt zu zeigen, dass es Bewegungszuge gibt, die die Permutationen(1, 2), (1, 3), (1, 4) der vier Raumdiagonalen bewirken, da diese Permutationenbereits die ganze S4 erzeugen. Diese sind

BOBRBO → (1, 2),

BOBO → (1, 3),

BOBVBO → (1, 4).

8.5.2 Beschreibung der Mittelscheibengruppe

Diese Gruppe H = 〈MR,MV ,MO〉 wird aus den drei Mittelscheibenzugen er-zeugt. Wir beschreiben sie im folgenden in Anlehnung an D. Joyner (2002, S.150 ff.). Sei dazu E die Menge der Kantencubies und C die Menge der Cubiesim Zentrum jeder Wurfelseite und X = E ∪ C. Dann operiert H auf X. DieEckencubies werden von H nicht bewegt.

Es gilt:

• Die Operation von H auf X ist nicht transitiv, da z.B. ein Kantencubienicht zu einem Cubizil im Zentrum hinbewegt werden kann.

• Die Operation von H auf C ist transitiv, da jedes Cubie im Zentrum zujedem beliebigen Zentrumscubizil durch ein Element aus H hinbewegtwerden kann.

• Die Operation von H auf E ist nicht transitiv, da sich jedes Kantencubienur in seiner

”Scheibe“ bewegen kann. Das ov-Kantencubie kann z.B.

nicht durch einen Mittelscheibenzug ins or-Cubizil gebracht werden.

Bahnen von H bezuglich E

Wir nennen zwei Kantencubies aquivalent, wenn eines mit einem Mittelschei-benzug ins Cubizil des anderen geschickt werden kann. Es gibt drei disjunkteAquivalenzklassen, die jeweils die Cubies einer Mittelscheibe enthalten.

Die Bahnen von H bezuglich E sind daher

• Die Kantencubies der Scheibe MR, genannt ERL,

• die Kantencubies der Scheibe MV , genannt EV H und

• die Kantencubies der Scheibe MO, genannt EOU .

E ist die disjunkte Vereinigung der Bahnen, die die Operation von H aufE definiert: E = ERL ∪ EV H ∪ EOU .

66

Jedes Element aus H bestimmt ein Element in SX , der Gruppe aller Per-mutationen der Elemente aus X. Es gibt daher einen Homomorphismus f :H → SX , was einfach bedeutet, dass H auf der H-Menge X operiert.

Jeder Mittelscheibenzug M ∈ MR,MV ,MO ist als Element der SX vonder folgenden Form:

M=(4-Zyklus in SE)(4-Zyklus in SC)

Proposition

Der Homomorphismus f ist eine Einbettung, also injektiv.

Beweis: Mittelscheibenzuge konnen Kantencubies nur innerhalb der Schei-be, zu der sie gehoren, rotieren. Die Elemente aus H konnen Kantencubies nurpermutieren, nicht umorientieren. Daher sind sie durch die Elemente der SX

eindeutig bestimmt. q.e.d.H operiert auf der Bahn ERL, es gibt daher einen Homomorphismus

rRL : H → SERL

und genauso Homomorphismen rOU : H → SEOUund rV H : H → SEV H

.H operiert auf jedem der Sets E und C, also gibt es Homomorphismenr = rRL×rOU ×rV H : H → SERL

×SEOU×SEV H

⊂ SE, s : H → SC , welcheman zum injektiven Homomorphismus r× s : H → SERL

× SEOU× SEV H

× SC

zusammensetzen kann.Um H zu bestimmen, bestimmen wir das Bild von H in SERL

× SEOU×

SEV H× SC . Offenbar gilt:

• Das Bild von H in SERList 〈MR〉 ∼= Z4,

• das Bild von H in SEV Hist 〈MV 〉 ∼= Z4 und

• das Bild von H in SEOUist 〈MO〉 ∼= Z4.

Nun bestimmen wir das Bild von H in SC . Interessiert man sich nur furdie Bewegungen der Cubies im Zentrum, so konnen die Mittelscheibenzugeeigentlich auch durch die entsprechenden Rotationen des gesamten Wurfels(um eine Symmetrieachse) ersetzt werden. Daher ist das Bild von H in SC

dasselbe wie das Bild der Gruppe der Symmetrietransformationen des Wurfels,die, wie bereits festgestellt, isomorph zu S4 ist.

Verknupft man obige Erkenntnisse, so sieht man, dass das Bild von H inSERL

×SEOU×SEV H

×SC isomorph zu einer Untergruppe von Z34×S4 ist. Wir

konnen daher die Elemente vonH als 4-Tupel (h1, h2, h3, h4) mit h1, h2, h3 ∈ Z4

und h4 ∈ S4 angeben.

67

Nachdem jedes der die Gruppe H erzeugenden Manover MR,MO und MV

die Bedingung sgn(r(h)) = sgn(s(h)) ∀h ∈ H erfullt (auf die Kantencubiesund auf die Cubies im Zentrum wird jeweils ein 4-Zyklus angewandt), kanndas Bild von H nicht die ganze Gruppe Z3

4 × S4 sein.

Proposition

Das Bild von H in Z34 × S4 ist isomorph zum Kern der Abbildung

t : Z34 × S4 → ±1

(h1, h2, h3, h4) → sgn(h1) · sgn(h2) · sgn(h3) · sgn(h4),

wobei jedes sgn das Signum der Permutation als Element der SX darstellt.

Bemerkung

|ker(t)| = (43 · 4!)/2 = 768

Erklarung: Der Kern von t besteht aus allen h ∈ H, die auf 1 (das neutraleElement in ±1) abgebildet werden. Damit nun sgn(h1) · sgn(h2) · sgn(h3) ·sgn(h4) = 1 gilt, kann man h1, h2 und h3 beliebig wahlen - man hat 43 Moglich-keiten, dies zu tun. Fur die Permutation h4 steht dann fest, ob sie gerade oderungerade sein muss. In jedem Fall hat man fur die Wahl von h4 4!/2 Moglich-keiten, da es in der S4 genauso viele gerade wie ungerade Permutationen gibt.

Beweis der Proposition:Wir haben bereits gezeigt, dass H zu einer Untergruppe von Z3

4 × S4 iso-morph ist. Die Mittelscheibenzuge bilden jeder fur sich eine gerade Permuta-tion der Cubies, die sie bewegen und gehoren daher zum Kern von t (dennsgn(h) =

∏4i=1 sgn(hi) und fur jeden Mittelscheibenzug gilt sgn(h4) = −1 und

∃! i ∈ 1, 2, 3 : sgn(hi) = −1). Also ist H isomorph zu einer Untergruppevon ker(t) ⊂ Z3

4 × S4 (da die Kombination mehrerer Mittelscheibenzuge alsProdukt gerader Permutationen wieder gerade ist).

Zu zeigen bleibt, dass jedes Element des Kerns von t zu H gehort. Dazubetrachten wir den Projektionshomomorphismus

p : H → S4,

den man erhalt, wenn man oben konstruierten Homomorphismus r × s :H → Z3

4×S4 mit dem Projektionshomomorphismus Z34×S4 → S4 kombiniert.

p ist surjektiv, da das Bild von H in SC isomorph zu S4 ist.Bezeichnen wir die Identitatsabbildung in der S4 mit 1, so ist der Kern

von p Kern(p) = h ∈ H|s(h) = 1. Die Menge h ∈ H|s(h) = 1, rRL(h) +

68

rOU(h) + rV H(h) ≡ 0 (mod2) liegt daher im Kern von p. Unter rRL(h) ver-stehen wir hier bereits das zugeordnete Element der Z4, d.h. die Anzahl der90-Drehungen von MR mod 4. rRL(h) beschreibt die Potenz des 4-Kanten-Zyklus der MittelscheibeMR. Da ein 4-Zyklus aus drei Transpositionen bestehtund damit eine ungerade Permutation ist, beschreiben die ungeraden Ziffernder Z4, die den Permutationen rRL(h), rOU(h) und rV H(h) zugeordnet werden,genau die ungeraden Permutationen aus dieser Menge.

Da der Kern von p eine Untergruppe von H ist, gilt

sgn(s(h)) = sgn(r(h)) = sgn(rRL(h)) · sgn(rOU(h)) · sgn(rV H(h)).

Das Signum von r(h) ist genau dann gleich 1, wenn die PermutationenrRL(h),rOU(h) und rV H(h) entweder alle gerade sind oder genau zwei davon ungeradesind. Daher ist die Bedingung sgn(rRL(h)) ·sgn(rOU(h)) ·sgn(rV H(h)) = 1 identmit der Bedingung rRL(h) + rOU(h) + rV H(h) ≡ 0(mod2).

Daraus folgt

Kern(p) ⊂ h ∈ H|s(h) = 1, rRL(h) + rOU(h) + rV H(h) ≡ 0 (mod2)

und insgesamt

Kern(p) = h ∈ H|s(h) = 1, rRL(h) + rOU(h) + rV H(h) ≡ 0 (mod2)Wieviele Elemente hat nun der Kern von p?

Dazu betrachten wir die Bedingung rRL(h)+ rOU(h)+ rV H(h) ≡ 0 (mod2)mit rRL(h), rOU(h) und rV H(h) aus Z4. Zwei Elemente, z.B. rRL(h) und rOU(h)konnen beliebig gewahlt werden - man hat fur jede dieser Permutationen vierMoglichkeiten aus Z4. Die letzte Permutation, in unserem Fall rV H(h), mussdann, je nach Wahl der ersten beiden Permutationen, entweder gerade oderungerade sein - in jedem Fall hat man noch zwei Moglichkeiten, ein Elementaus Z4 so zuzuordnen, dass obige Bedingung erfullt ist.

Der Kern von p hat somit 4 · 4 · 2 = 32 Elemente.

Nach dem Homomorphiesatz gilt nun

H/Kern(p) ∼= Bild(p) = S4, wobei Bild(p) das Bild von p ist.

Daher ist |H| = |S4| · |Kern(p)| = 4! · 32 = 768.

Da H, wie bereits gezeigt, isomorph zu einer Untergruppe des Kerns vont : Z3

4 × S4 → ±1 ist und der Kern von t ebenfalls 768 Elemente enthalt, istH ident mit Kern(t). q.e.d.

69

8.6 Untergruppen der Ordnung 2

Aus Abschnitt 7.1 wissen wir: die Rubiksche Gruppe G ist isomorph zumsemidirekten Produkt (symbolisch n) von (ρ, σ) ∈ S8×S12| sgn(ρ) = sgn(σ)und Z7

3 × Z112 .

Anders ausgedruckt ist G isomorph zu den Elementen der Gruppe H =(Z7

3 o S8)× (Z112 o S12) mit sgn(ρ) = sgn(σ) (∀ρ ∈ S8, σ ∈ S12). Ein Element

(x, y, ρ, σ) der Rubikschen Gruppe hat genau dann die Ordnung 2, wenn dasElement (h1, h2) ∈ H mit h1 = (x, ρ) und h2 = (y, σ) Ordnung 2 hat.

Wir interessieren uns hier fur die Anzahl der Elemente aus G mit Ordnung2. Diese lassen sich nach D. Joyner (2002, S. 186 ff.) in 3 disjunkte Untergrup-pen unterteilen:

(a) Elemente, die nur Eckencubies bewegen,

(b) Elemente, die nur Kantencubies bewegen und

(c) Elemente, die sowohl Kanten-, als auch Eckencubies bewegen.

Wir beschaftigen uns vorerst mit der Teilmenge (a), die aus den geradenPermutationen der 8 Eckencubies der Ordnung 2 besteht. Nachdem die Permu-tation gerade sein und Ordnung 2 haben muss, werden entweder zwei oder vierPaare von Eckencubies vertauscht (Zyklen, die langer als 2 sind, haben einehohere Ordnung!). Eckencubies, die nicht bewegt werden, durfen auch nichtumorientiert werden, da dabei kein Manover der Ordnung 2 entstehen kann(denn 1 + 1 ≡ 2 6≡ 0 (mod3) und 2 + 2 ≡ 4 ≡ 1 6≡ 0 (mod3)). Fur jede Trans-position von Eckencubies gibt es offenbar drei Moglichkeiten die Eckencubieszu verdrehen, sodass insgesamt ein Manover der Ordnung 2 dabei entsteht(Wird das erste Eckencubie z.B. um 1 verdreht, so muss - damit nach zwei-maliger Anwendung der Transposition die ursprungliche Orientierung erreichtwird - das zweite Eckencubie um 2 verdreht werden, etc.).

Elemente der Ordnung 2 in Z73 o S8 sind jene (x, ρ) mit ρ2 = 1 (d.h. Per-

mutationen, die aus disjunkten Transpositionen bestehen), fur die außerdemgilt: x1 + . . .+ x8 ≡ 0 (mod3) und xi + xρ−1(i) = xi + xρ(i) ≡ 0 (mod3). Nichtalle solchen Elemente entsprechen Manovern bzw. moglichen Positionen desZauberwurfels.

Bestimmen wir nun die Anzahl der Elemente der Ordnung 2 in Z73 o S8:

Die Anzahl der Moglichkeiten aus 8 Elementen 4 Paare, die vertauscht

werden sollen, auszuwahlen, betragt 14!

(82

) (62

) (42

).

(Erklarung: Denken wir uns diese Paare der Einfachheit halber bereits als

Paare von Eckencubies. Fur das erste Paar hat man

(82

)Moglichkeiten, fur

das zweite Paar stehen nur noch 6 Eckencubies zur Auswahl zur Verfugung,

daher hat man

(62

)Moglichkeiten, etc. Nachdem es keine Rolle spielt, in

welcher Reihenfolge man die 4 Paare auswahlt, muss noch durch die Anzahl

70

aller moglichen unterschiedlichen Reihenfolgen, eben durch 4!, dividiert wer-den.)

Wie oben bemerkt gibt es pro Paar drei Orientierungsmoglichkeiten. DieAnzahl der Elemente der Ordnung 2 in Z7

3 oS8, bei denen vier Transpositionenvon Eckencubies und keine Bewegung der Kantencubies stattfindet ist somit

1

4!

(82

) (62

) (42

)34.

Ebenso bestimmt man die Anzahlen, bei denen drei, zwei bzw. eine Trans-position von Eckencubies und keine Bewegung der Kantencubies stattfindet.

Man erhalt fur die Gesamtanzahl der Elemente der Ordnung 2 in Z73 o S8:

1

4!

(82

) (62

) (42

)34 +

1

3!

(82

) (62

) (42

)33

+1

2!

(82

) (62

)32 +

(82

)3 = 21819.

Der zweite und letzte Term zahlt keine Elemente der Rubikschen Gruppe,da es sich hier nicht um eine gerade Anzahl von Transpositionen (und damitnicht um gerade Permutationen) handelt.

Die Anzahl der Elemente (x, ρ) der Ordnung 2 aus Z73 o S8, bei denen ρ

gerade ist, ist somit

14!

(82

) (62

) (42

)34 + 1

2!

(82

) (62

)32 = 10395. (1)

Die Anzahl der Elemente (x, ρ) der Ordnung 2 aus Z73 o S8, bei denen ρ

ungerade ist, betragt

13!

(82

) (62

) (42

)33 +

(82

)3 = 11424. (2)

Bei der Zahlung der Manover der Ordnung 2, die nur Kantencubies bewe-gen, gehen wir ahnlich vor:

Es konnen, damit eine gerade Permutation der Ordnung 2 entsteht, nur2, 4 oder 6 Paare von Kantencubies vertauscht werden. Pro Paar gibt es 2Moglichkeiten, die Cubies umzuorientieren. Die Kantencubies, die an ihremHeimatcubizil verbleiben, konnen - im Gegensatz zu den Eckencubies - jedochbeliebig orientiert werden, da es nur zwei Orientierungsmoglichkeiten gibt undsomit jede Verdrehung Ordnung 2 haben muss.

Die Anzahl aller Elemente der Ordnung 2 in (Z112 o S12) betragt

71

1

6!

(122

) (102

). . . .

(42

)26 +

1

5!

(122

) (102

). . . .

(42

)27

+1

4!

(122

). . . .

(62

)28 +

1

3!

(122

). . .

(82

)29

+1

2!

(122

) (102

)210 +

(122

)211 = 30706368.

Wiederum sind nicht alle Elemente in dieser Aufzahlung mogliche Positio-nen des Zauberwurfels.

Die Anzahl der Elemente (y, σ) der Ordnung 2 aus (Z112 o S12), bei denen

σ gerade ist, ist

1

6!

(122

) (102

). . .

(42

)26 +

1

4!

(122

). . .

(62

)28 +

1

2!

(122

) (102

)210 = 15491520.

(3)

Die Anzahl der Elemente (y, σ) der Ordnung 2 aus (Z112 o S12), bei denen

σ ungerade ist, betragt

1

5!

(122

) (102

). . .

(42

)27 +

1

3!

(122

). . .

(82

)29 +

(122

)211 = 15214848.

(4)

Da die Elemente (x, y, ρ, σ) der Rubikschen Gruppe G den Elementen derGruppeH = (Z7

3oS8)×(Z112 oS12) mit sgn(ρ) = sgn(σ) entsprechen, kann man

sie in folgende vier Untergruppen bestehend aus (h1, h2) ∈ H mit h1 = (x, ρ)und h2 = (y, σ) unterteilen (wobei wir uns wiederum nur fur die Elemente derOrdnung 2 interessieren):

(a) h1 6= 1, h2 = 1, h21 = 1, sgn(ρ) = 1,

(b) h1 = 1, h2 6= 1, h22 = 1, sgn(σ) = 1,

(c) h1 6= 1, h2 6= 1, h21 = h2

2 = 1, sgn(ρ) = sgn(σ) = 1,(d) h1 6= 1, h2 6= 1, h2

1 = h22 = 1, sgn(ρ) = sgn(σ) = −1,

Die Anzahl der Elemente in (a) wird in (1) gezahlt, die Anzahl der Ele-mente in (b) in (3). Fur (c) kann man alle geraden Permutationen der Ecken

72

und Kanten miteinander kombinieren, die jeweiligen Anzahlen aus (a) und(b) sind also zu multiplizieren, und im Fall (d) gilt das Analoge - hier wer-den die Anzahlen der ungeraden Permutationen aus (2) und (4) miteinandermultipliziert.

Summiert man alle Falle auf, erhalt man fur die Anzahl der Elemente derOrdnung 2 aus der Rubikschen Gruppe

10395 + 15491520 + 10395 · 15491520 + 11424 · 15214848 = (3.34..) · 1011.

8.7 Die Kommutatorgruppe

Diese Untergruppe K(G) der Rubikschen Gruppe besteht aus allen endlichenProdukten von Kommutatoren und hat, wie wir bereits in Satz 5.2.5 gesehenhaben, Index 2, umfasst also die halbe Rubiksche Gruppe.

D. Singmaster (1981, S. 27) liefert fur diese Tatsache eine anschaulicheelementare Erklarung, die als Erganzung zum Beweis des Satzes 5.2.5 kurzerwahnt werden soll:

In Satz 4.3.3 haben wir gezeigt, dass ein beliebiger Ecken-3-Zyklus (und ent-sprechende Konjugationen davon) genugt, um alle geraden Permutationen derEckencubies zu erzeugen. Dasselbe gilt fur die Kantencubies. Wir haben eben-so gezeigt, dass man, um alle Cubies richtig zu orientieren, nur ein Manoverbenotigt, das zwei Kantencubies in dieselbe Richtung verdreht und eines, daszwei Eckencubies in verschiedene Richtungen um je 120 verdreht.

Finden wir Produkte von Kommutatoren, die diese Manover bewirken, sowissen wir bereits, dass K(G) mindestens die halbe Gruppe ist: Da konjugierteKommutatoren wieder Kommutatoren sind, erzeugt K(G) damit alle geradenPermutationen der Eckencubies sowie alle geraden Permutationen der Kanten-cubies. Die Gruppe G enthalt außerdem noch alle Kombinationen ungeraderEcken- und Kantenpermutationen. Die Anzahl dieser ist aber genauso großwie die Anzahl aller Kombinationen gerader Ecken- und Kantenpermutatio-nen. Daher umfasst K(G) mindestens die halbe Rubiksche Gruppe.

Die gesuchten Manover sind:

• Zur richtigen Platzierung der Eckencubies:

[V,R]L′ [R, V ]L→ (rvo, vlo, ulv)

(D. Singmaster, 1981, S. 23)

• Zur richtigen Orientierung der Eckencubies:

[R′, V ] [O, V ′] [O′, R] (12) → (+orv)(−ovl)(ov, ro, vr)

73

(R. Ahrens in C. Bandelow, 1981, S. 117, m11)

Dieses Manover bewirkt zwar auch einen Kanten-3-Zyklus, was aber kei-ne Rolle spielt, wenn man erst die Eckencubies richtig orientiert und sichdann um die Kantencubies kummert.

• Zur richtigen Platzierung der Kantencubies:

[R,O′]UO′ [O′, R]OU ′ → (ov, vr, rh)

(C. Bandelow, 1981, S. 124, m532)

• Zur richtigen Orientierung der Kantencubies:

Erhebt man dieses Manover

[V,R′] [R,O′] [O, V ′] → (+vlo)(+vor)(+vru)(+vo)(+vr)

(M. Vaughan-Lee in D. Singmaster, 1981, S. 24)

zur dritten Potenz, so erhalten die Eckencubies wieder ihre ursprunglicheOrientierung, und es verbleibt (+vo)(+vr).

DassK(G) mit der Rubikschen Gruppe jedoch nicht ident ist, zeigt folgendeUberlegung (D. Singmaster, 1981, S. 27):

Wir definieren die”Bewegung“ einer Folge von Zugen als die Summe aller

Exponenten in dieser Folge, z.B. hat V 2RH−1L die Bewegung 2+1−1+1 = 3.Da alle elementaren Randscheibenzuge Ordnung 4 haben, betrachten wir dieBewegung eines Manovers mod4.

Klarerweise sind die Manover der Bewegung 0 oder 2 unter Multiplikationabgeschlossen und bilden damit eine Untergruppe. Es gibt Manover ungeraderBewegung, z.B. V . Zu jedem Manover M ungerader Bewegung ist auch M−1

von ungerader Bewegung, da −3 ≡ 1 (mod4) und −1 ≡ 3 (mod4).Ist P ein Manover ungerader Bewegung, dann ist PQ ein Manover un-

gerader Bewegung fur jedes Manover gerader Bewegung Q. Da aus Q 6= R⇒ PQ 6= PR und da jedes Manover ungerader Bewegung R als PQ ge-schrieben werden kann, wobei Q ein Manover gerader Bewegung ist, indemman Q = P−1R setzt, folgt, dass die Abbildung Q → PQ bijektiv von denManovern gerader Bewegung zu den Manovern ungerader Bewegung fuhrt.

Daher gibt es genauso viele Manover gerader wie ungerader Bewegung,und die Manover gerader Bewegung machen genau die Halfte der RubikschenGruppe aus.

Da jeder Kommutator Bewegung 0 hat, istK(G) in der Gruppe der Manovergerader Bewegung enthalten, und da erstere mindestens genauso groß wie letz-tere ist, sind die beiden ident.

74

Das bedeutet aber auch, dass die Gruppe der Manover der Bewegung 0ident ist mit der Gruppe der Manover der Bewegung 2. Diese Tatsache wirdersichtlich, sobald man ein Manover der Bewegung 2 findet, die der Identitatentspricht, z.B. (RO)105 = I. Jedes andere Manover der Bewegung 2 kannman schließlich mit der Identitat multiplizieren ohne es zu verandern, wodurchdennoch ein Manover der Bewegung 0 entsteht.

75

Kapitel 9

Die Losung des Wurfels

9.1 Wie und wie schnell man den Wurfel losen

kann und warum es uberhaupt so kompli-

ziert ist

9.1.1 Die Schwierigkeit beim Losen des Wurfels

Die Große der Zahl moglicher Positionen des Zauberwurfels (> 43 Trillionen!)ist nicht die Hauptursache fur die Schwierigkeit des Spiels. Es wird beispiels-weise niemand als Herausforderung ansehen, 21 Karten einer Kundenkarteialphabetisch zu ordnen, obwohl es fur diese 21 Karten 21! = 51, . . . ·1018 (> 51Trillionen) Reihenfolgen gibt.

Die Schwierigkeiten mit dem Zauberwurfel beruhen dagegen auf der kom-plizierten Verbundenheit von jeweils 8 bis 9 Cubies, die es erforderlich macht,die Losung auf Umwegen anzusteuern. Diese Umwege erscheinen beachtlich,wenn man bedenkt, dass vor dem letzten Zug notwendigerweise noch 8 Cubiesfalsch stehen mussen und unmittelbar vor dem vorletzten Zug sogar noch 12- 16 Cubies (12 nur im Falle von zwei 180 - Mittelscheibenzugen). Ist mannoch weiter vom geordneten Zustand des Wurfels entfernt, werden daher inder Regel mehr als die Halfte aller Cubies falsch stehen! (C. Bandelow, 1981,S. 49 ff.)

9.1.2 Eine einfache Strategie - Die Ecken-Kanten-Me-thode

Bei dieser Methode nach D. Joyner (2002, S. 234 ff.) wird der Wurfel in fol-genden 4 Schritten gelost:

1. Ordne die Eckencubies, sodass sie zu den Cubies im Zentrum passen,ohne Rucksicht auf ihre Orientierung.

76

2. Ordne die Kantencubies, sodass sie zu den Cubies im Zentrum passen,ohne Rucksicht auf ihre Orientierung.

3. Bringe die Orientierung der Eckencubies in Ordnung.

4. Nachdem auch die falsch orientierten Kantencubies richtig gedreht wor-den sind, ist der Wurfel gelost!

Ordnung der Eckencubies Dies gelingt mit Hilfe einer Methode, die wirin Anlehnung an D. Joyner (2002)

”fischen“ nennen wollen. Mathematisch

gesehen handelt es sich dabei um die Anwendung sorgsam ausgesuchter Kom-mutatoren.

Angenommen, wir wollen das (lvu)-Eckencubie in das (orv)-Cubizil brin-gen, ohne den Rest des Wurfels zu sehr durcheinander zu bringen. Der Zug R′

entspricht beim”fischen“ dem Auslegen des Koders, mit dem Zug U beißt der

Fisch an und mit R wird die Angel wieder eingeholt - der Fisch ist gefangen.U ′ bringt schließlich den

”Meeresboden“ wieder in Ordnung.

Mit der Methode des Fischens kann man entweder (a) alle Eckencubiesrichtig positionieren, (b) alle richtig positionieren, bis auf zwei, die vertauschtwerden mussen, oder (c) alle richtig positionieren, außer drei, die zyklisch per-mutiert werden mussen.

Um diesen ersten Schritt zu vollenden, brauchen wir daher eine Ecken-Transposition im Fall (b) und einen Ecken-3-Zyklus im Fall (c).

Im Fall (b) bietet sich folgendes Manover an:

OV [R,O]3 V ′ → (ohr, ovl)(ov, ol, oh, or).

Sind die Ecken, die man permutieren mochte, nicht in den Positionen (ohr)und (ovl), dann verwendet man folgenden Trick:

Man dreht den Wurfel so, dass einer der zu permutierenden Eckencubies inder (ohr)-Position ist und bringt den zweiten Eckencubie mit einem passendenRandscheibenzug (so kodert man ihn!) in das (ovl)-Cubizil. Dann fuhrt manobiges Manover aus und anschließend den zum

”Kodern“ inversen Randschei-

benzug (so holt man den Koder wieder ein).

Im Fall (c) verwendet man beispielsweise

[RUR′, O] → (hru, orh, olh).

Sind die entsprechenden Eckencubies nicht in den richtigen Positionen, somuss man wieder den

”Koder“-Trick verwenden.

77

Ordnung der Kantencubies Um diesen Schritt zu vollenden muss maneinfach den Kanten-3-Zyklus

M2RO

′M ′RO

2MRO′M2

R → (ov, ol, or)in Kombination mit dem bewahrten Koder-Trick (mathematisch gesehen

eine simple Konjugation) immer weiter anwenden, bis die Ordnung der Kan-tencubies vollstandig hergestellt ist.

Da 3-Zyklen die alternierende Gruppe erzeugen, funktioniert diese Vorge-hensweise jedenfalls fur gerade Permutationen der Kantencubies. Handelt essich bei der Position des Wurfels um eine ungerade Permutation der Eckenund Kanten, so wendet man einfach zusatzlich ein Manover an, das sowohlzwei Ecken als auch zwei Kanten vertauscht, z.B.

L′ORO′LO2R′ORO2R′(11) → (orv, ohr)(ov, or)

(M. B. Thistlethwaite in C. Bandelow, 1981, S. 129, m900),

RHR′OH ′OHO2RH ′R′O(12) → (orv, hol)(ov, or)

(M. B. Thistlethwaite in C. Bandelow, 1981, S. 129, m905) oder

OHLOL′O′H ′(7) → (−ovl, ohr)(+olh)(+oh, or)(+ol)

(C. Bandelow, 1981, S. 129, m991).

Orientierung der Eckencubies Hierfur genugt ein Manover, das zwei Ek-kencubies gegensinnig verdreht, in Kombination mit unserem Koder-Trick. Eingeeignetes Manover ist

(R′U2RH ′O2H)2 → (+ovr)(−hlu).

Orientierung der Kantencubies Es empfehlen sich folgende zwei Manover:

(MRO)3O(M ′RO)3O → (+ov)(+oh) sowie

(MRO)4 → (+oh)(+ol)(+uv)(+uh).

9.1.3 Die Anzahl der Zuge

Wieviele Zuge benotigt man im”schlimmsten Fall“ mindestens, um den Wurfel

zu losen? Wir wollen uns bei der Betrachtung dieser Frage darauf einigen, dasses sich bei einem Zug um einen Randscheibenzug um 90 im oder gegen denUhrzeigersinn handelt.

Anders formuliert mochten wir wissen, aus welcher Position man die mei-sten Zuge benotigt, um den Wurfel zu losen, wenn man die bestmogliche Stra-tegie verwendet und so mit einer minimalen Anzahl an Zugen auskommt. Die

78

großte auftretende Anzahl dieser Minimalzahl an Zugen wird”God’s num-

ber“ genannt. Diese Anzahl entspricht zugleich dem Durchmesser des Cayley-Graphen.

Eine ungefahre Untergrenze fur God’s number erhalt man mittels folgenderUberlegung (T. Davis, 2006, S. 31): Von einem geordneten Wurfel ausgehendgibt es hochstens 12 mogliche Positionen nach dem ersten Randscheibenzug (6Scheiben, im oder gegen den Uhrzeigersinn). Nach zwei Zugen gibt es hochstens12 ·11 Positionen, nicht 122, da einer der 12 Zuge den ersten ruckgangig macht(und damit zur Startposition zuruckfuhrt). Nach 3 Zugen gibt es hochstens12 · 112 und nach n Zugen schließlich hochstens 12 · 11n−1 mogliche Positio-nen. Nachdem man genauso viele Zuge benotigt, um aus einer bestimmtenPosition den Wurfel zu losen, wie man brauchen wurde, um aus der Startposi-tion zu der entsprechenden Position zu gelangen, muss n groß genug sein, dass1+12+12 ·11+12 ·112 + . . .+12 ·11n−1 = 1+12 ·(

∑n−1k=0 11k) = 1+12 · 11n−1

10>

4, 32 · 1019, wobei auf der linken Seite der Ungleichung 1 fur die Identitat, dengeordneten Wurfel, steht und die Zahl auf der rechten Seite der Ungleichungdie Gesamtanzahl moglicher Positionen ist. Lost man diese Gleichung fur n,erhalt man eine Untergrenze von 19. Etwas vorsichtigere Kalkulationen schlie-ßen unnotig komplizierte Zuge, wie z.B. V V V , aus. Dadurch hat man auf derlinken Seite ab dem zweiten Zug nicht immer 11 Mogichkeiten, sondern manch-mal weniger, wodurch sich aus der Gleichung fur n letztendlich eine großereZahl ergeben muss. Diese Vorsichtsmaßnahmen liefern fur die Untergrenze vonGod’s number den Wert 21.

Lange Zeit hatte man gedacht, dass God’s number 24 ist, da man (minde-stens) 24 Zuge benotigt, um die Position

”Superflip“, bei der alle Kantencubies

falsch orientiert sind, in den geordneten Zustand zuruckzufuhren.

Dann fand Mike Reid ein noch langeres Element der Rubikschen Gruppe,das zwar nur 21 Randscheibenzuge, aber 26

”echte“ 90-Randscheibenzuge

benotigt (D. Joyner, 2002, S. 81):

superflip4spot= O2U2LV 2O′UR2HO′U ′RLV 2ROU ′R′LOV ′H ′(26).

Mike Reid bewies auch, dass die Anzahl der Zuge dieses Manovers minimalist, um den Wurfel aus der dem Manover entsprechenden Position in den geord-neten Zustand uberzufuhren, was bedeutete, dass God’s number mindestens26 sein muss.

Im Fruhjahr 2007 gelang es D. Kunkle und G. Cooperman zu zeigen, dassGod’s number genau 26 betragt.

79

9.1.4 Wichtige Manover

Der Superflip

Der Superflip ist besonders wichtig, da er, wie bereits gezeigt, neben der Iden-titat das einzige Manover im Zentrum der Rubikschen Gruppe ist. Seine einzigeWirkung ist die Umorientierung aller Kantencubies.

Die kurzeste Variante des Superflips stammmt von Mike Reid (in D. Joyner,2002, S. 80):

R′O2HL′V O′HUV OU ′LU2V ′RH ′UV ′O′H ′OU ′(24)

Jerry Bryan zeigte in einem eMail vom 19.2.1995 an die”cube lover’s email

list“, dass es keine geringere Anzahl von 90-Randscheibenzugen gibt, die denSuperflip bewirken.(ftp-Archive der

”cube-lovers“-Liste auf ftp://ftp.ai.mit.edu/pub/cube-lovers/

in D. Joyner, 2002, S. 80)

Drehungen der Eckencubies

Isotwist fur die obere Scheibe:

R′URV UV ′(6) → (+orv)(+uvr)(+urh, uhl, ulv)(vr, ul, uv, ru, hu)

(C. Bandelow, 1981, S. 116 m0)

Abbildung 9.1: R′URV UV ′(6) (Quelle: C. Bandelow, 1981, S. 116)

Gegensinnige Verdrehung zweier Eckencubies:

R(O2RV ′U2V R′)2R′(13) → (+orv)(−ovl)

(C. Bandelow, 1981, S. 117 m5)

(O2L′V BLV )4(12) → (+orv)(−olh)

(E. Rubik in C. Bandelow, 1981, S. 117 m15)

80

Abbildung 9.2: R(O2RV ′U2V R′)2R′(13) (Quelle: C. Bandelow, 1981, S. 117 )

Abbildung 9.3: (O2L′V BLV )4(12) (Quelle: C. Bandelow, 1981, S. 117 )

Ecken-3-Zyklen

RHL′H ′R′HLH ′(8) → (ovl, orv, hro)

(C. Bandelow, 1981, S. 119 m101)

(R2UL2U ′)2(8) → (ovl, orv, urh)

(C. Bandelow, 1981, S. 120 m110)

Ecken-Transpositionen

Isoswap fur die obere Scheibe:

R′UV ′U2V U ′R(7) → (ovl, orv)(uvr, uhl)(uv, uh)(vl, rv)

(C. Bandelow, 1981, S. 121 m300)

Drehungen der Kantencubies

Isoflip fur die obere Scheibe:

RMUR2M2

UR(5) → (+or)(+vl)(hl, ru)(v, l, h, r),

wobei v, l, h, r die entsprechenden Flachencubies vorne, links, . . . bezeich-net.

(C. Bandelow, 1981, S. 122 m400)

(MRO)4(8) → (+ol)(+oh)(+hu)(+uv)

(C. Bandelow, 1981, S. 122 m431)

81

Abbildung 9.4: RHL′H ′R′HLH ′(8) (Quelle: C. Bandelow, 1981, S. 119)

Abbildung 9.5: (R2UL2U ′)2(8) (Quelle: C. Bandelow, 1981, S. 119)

Abbildung 9.6: R′UV ′U2V U ′R(7) (Quelle: C. Bandelow, 1981, S. 121)

Abbildung 9.7: RMUR2M2

UR(5) (Quelle: C. Bandelow, 1981, S. 122)

82

Kanten-3-Zyklen

R2M ′UR

2MU(4) → (vr, hl, hr)

(C. Bandelow, 1981, S. 123 m500)

Abbildung 9.8: R2M ′UR

2MU(4) (Quelle: C. Bandelow, 1981, S. 123)

ROR′M ′VRO

′R′MV (8) → (ov, ol, ro)

(C. Bandelow, 1981, S. 123 m511)

Abbildung 9.9: ROR′M ′VRO

′R′MV (8) (Quelle: C. Bandelow, 1981, S. 123)

Kanten-Transpositionen

(R2M2U)2(4) → (vr, hr)(vl, hl)

(C. Bandelow, 1981, S. 126 m600)

83

(R2O2)3(6) → (rv, rh)(ov, oh)

(C. Bandelow, 1981, S. 126 m620)

Abbildung 9.10: (R2O2)3(6) (Quelle: C. Bandelow, 1981, S. 126)

V O2V ′O′L′H ′O2HOL(10) → (+ov, oh)(+ol, or)

(C. Bandelow, 1981, S. 127 m710)

Abbildung 9.11: V O2V ′O′L′H ′O2HOL(10) (Quelle: C. Bandelow, 1981, S. 127)

Transpositionen von Ecken- und Kantencubies

L′ORO′LO2R′ORO2R′(11) → (orv, ohr)(ov, or)

(M. B. Thistlethwaite in C. Bandelow, 1981, S. 129, m900)

84

Kapitel 10

Andere mathematischeSpielzeuge

10.1 Der Superwurfel

10.1.1 Beschreibung des Superwurfels

Beim Superwurfel werden die normalerweise unsichtbaren Drehungen der Fla-chencubies sichtbar gemacht. Die einfachste Moglichkeit hierfur ist, auf jede dersechs Wurfelseiten einen Strich zu machen, der den Mittelpunkt des Flachen-cubiefarbplattchens mit dem Mittelpunkt eines Nachbarplattchens verbindet(s. Abbildung 10.1).

Abbildung 10.1: Der Zauberwurfel mit markierten Mitten (Quelle: C. Bandelow,1981, S. 92)

Beim Spiel”Superwurfel“ muss nun dieser markierte Wurfel, nachdem er

durcheinander gebracht wurde, so in den Ausgangszustand zuruck gefuhrt wer-den, dass auch die Strichhalften wieder richtig zusammenpassen. Die Dre-hungen der Flachencubies mussen in einem mathematischen Modell fur denSuperwurfel mit berucksichtigt werden. Wir unterscheiden hierfur wieder be-wegliche Cubies und Cubizile, die mit einer undurchsichtigen, unbeweglichenWurfelhulle verbunden sind. Nach Wahl einer beliebigen Nummerierung der 6

85

Flachencubies beschreiben wir ihre Lagen durch ein 6-tupel z = (z1, . . . , z6) ∈Z := 0, 1, 2, 36, wobei zk angibt, welche der 4 Seiten des k-ten Flachencubiesunter dem Markierungsstrich seines Cubizils liegt (k = 1, . . . , 6).

10.1.2 Definition

Eine R-Position des Superwurfels ist ein 5-tupel (ρ, σ, x, y, z), wobei (ρ, σ, x, y)eine R-Position des Wurfels und z ∈ Z = 0, 1, 2, 36 ist. Sie heißt moglich,wenn sie aus dem Ausgangszustand (1, 1, 0, 0, 0) des Superwurfels durch Rand-scheibendrehungen erreichbar ist (C. Bandelow, 1981, S. 94).

10.1.3 Satz

Eine R-Position des Superwurfels ist genau dann moglich, wenn die Bedingun-gen (a), (b) und (c) aus Satz 4.3.3 und die Bedingung

(d) (−1)z1+...+z6 = sgn(ρ)erfullt ist (C. Bandelow, 1981, S. 94).Beweis:(⇒) Ist (ρ, σ, x, y, z) eine mogliche R-Position des Superwurfels, so

ist (ρ, σ, x, y) eine mogliche R-Position des normalen Wurfels, woraus folgt,dass die Bedingungen (a), (b) und (c) aus Satz 4.3.3 erfullt sind. Gleichung (d)gilt fur jede mogliche R-Position, weil sie fur den Ausgangszustand (1,1,0,0,0)des Superwurfels erfullt ist (hier ist z1 = . . . = z6 = 0 und sgn(ρ) = sgn(IS8) =1) und bei jedem 90-Randscheibenzug erhalten bleibt (Jeder der Zuge V , H,R, L, O und U bewirkt einen Ecken-4-Zyklus und verandert so das Vorzeichenvon ρ). Außerdem bewirkt er durch die Drehung des entsprechenden Flachen-cubies, dass die Summe z1 + . . .+ z6 um 1 verandert wird.

(⇐) Zu zeigen bleibt: Wenn eine Position des Superwurfels, bei der sichEcken- und Kantencubies bereits im geordneten Zustand befinden, Bedingung(d) erfullt, ist sie moglich. Wir konnen voraussetzen, dass ρ gerade ist, dennist fur eine Position p ρ ungerade, so betrachten wir analog zu Satz 4.3.3einfach die Position pa = pO, deren Permutation der Ecken ρa gerade ist unddie ebenfalls Bedingung (d) erfullt (falls auch p die Bedingung (d) erfullt),da O die Koordinate des Flachencubies o um 1 verandert. Ist nun pa mittelsRandscheibenzugen erreichbar, so auch p = paO

′.Wir mussen daher zeigen, dass jede Position mit ρ gerade und damit z1 +

. . . + z6 ≡ 0 (mod2) fur die Flachencubies auflosbar ist. Das gelingt analogzu Satz 4.3.3 mit einem geeigneten Weg um den Wurfel und/oder mit Hilfefolgender Manover, wobei die Vorzeichen

”+“,

”−“ bzw.

”++“ die Drehung

eines Flachencubies um 90 im Uhrzeigersinn, um 90 gegen den Uhrzeigersinnbzw. um 180 im Uhrzeigersinn bezeichnen:

(OR)105(210) → (+o)(+r)

86

Abbildung 10.2: (OR)105(210)

(ORLO2R′L′)2(12) → (+ + o)

Abbildung 10.3: (ORLO2R′L′)2(12) (Quelle: C. Bandelow, 1981, S. 93)

M ′RM

′UMR ·O′ ·M ′

RMUMR ·O(8) → (+o)(−r)

Abbildung 10.4: M ′RM

′UMR · O′ ·M ′

RMUMR · O(8) (Quelle: C. Bandelow, 1981, S.93)

M ′RM

′UMR ·O2 ·M ′

RMUMR ·O2(8) → (+ + o)(+ + r)

M ′RM

2UMR ·O′ ·M ′

RM2UMR ·O(8) → (+o)(−u)

(M ′RM

2UMR ·O2)2(8) → (+ + o)(+ + u)

87

Abbildung 10.5: M ′RM

′UMR ·O2 ·M ′

RMUMR ·O2(8)(Quelle: C. Bandelow, 1981, S.93)

Abbildung 10.6: M ′RM

2UMR · O′ ·M ′

RM2UMR · O(8) (Quelle: C. Bandelow, 1981, S.

93 )

10.1.4 Satz

Bezeichnet |P | die Anzahl der moglichen R-Positionen des Zauberwurfels, sogilt:

Es gibt genau

211 · |P | = 88580102706155225088000 = 238314537211

(mehr als 88 Trilliarden) mogliche R-Positionen des Superwurfels.Beweis: Da fur jede mogliche R-Position (ρ, σ, x, y, z) des Superwurfels die

Gleichung (−1)z1+...+z6 = sgn(ρ) gilt, kann man z1, . . . , z5 beliebig wahlen und

Abbildung 10.7: (M ′RM

2UMR ·O2)2(8) (Quelle: C. Bandelow, 1981, S. 93 )

88

hat dafur 45 Moglichkeiten. z6 muss dann je nach Vorzeichen von ρ entwedergerade oder ungerade sein - man hat dafur in jedem Fall noch 2 Moglichkeiten.Daraus folgt: Die Anzahl der R-Positionen des Superwurfels betragt 45 ·2·|P | =211 · |P |. q.e.d. (C. Bandelow, 1981, S. 94)

Bemerkung Die minimale Anzahl von Generatoren fur die dem Superwurfelentsprechende Supergruppe ist gleich der Anzahl der Mitten, also gleich 6 (W.Hintze, 1982, S. 102).

10.2 Der 2× 2× 2-Wurfel

Abbildung 10.8: (Quelle: W. Hintze, 1982, S. 116)

Er besteht genau aus den Ecken des gewohnlichen Zauberwurfels, weshalbder fur die Ecken zustandige Teil einer Strategie fur den großen Wurfel stets ei-ne Strategie fur den kleinen Wurfel darstellt. Da keine Mitten vorhanden sind,um die Farbe einer Seite zu bestimmen, konnen wir eine beliebige Ecke desWurfels, z.B. uhl, als fest ansehen. Durch sie wird die Ordnung und der weitereAufbau des Wurfels festgelegt. Die verbleibenden 7 Ecken konnen durch dieZuge O, R und V positioniert und orientiert werden. Genauer gesagt konnen siebeliebig permutiert werden, da jedes Manover, das auf dem großen Wurfel ei-ne Ecken-Transposition und irgendeine ungerade Kanten-Permutation erzeugt,auf dem kleinen Wurfel nur noch die Ecken-Transposition bewirkt. Die Orien-tierungsbedingung bleibt fur die 7 bewegbaren Eckencubies (aus den gleichenGrunden wie beim großen Wurfel) bestehen, d.h. x1 + . . . + x7 ≡ 0 (mod3).Daher gilt

10.2.1 Satz

Der 2× 2× 2-Wurfel besitzt genau 7! · 36 = 3674160 mogliche Farbmuster (C.Bandelow, 1981, S.102).

89

Das ist 1/24 der Zahl der reinen Eckenzustande des großen Zauberwurfels,bei dem sich 8! · 37 ergibt. Der Faktor 1/24 entspricht gerade der Anzahl anSymmetrieabbildungen des Wurfels, d.h. an moglichen Drehungen des Wurfelsals Ganzes. Die 8 Ecken des Wurfels sind zwar auf 8! Arten permutierbar undauf 37 Arten orientierbar, aber 24 der so erhaltenen Stellungen unterscheidensich nur dadurch, dass der Wurfel als Ganzes gedreht ist, ohne die relative Lageder Cubies zu andern. (Beim

”normalen“ Zauberwurfel unterscheiden sich diese

24 Stellungen auch durch die relativ zu den Eckencubies unterschiedliche Lageder Cubies im Zentrum, die hier einen festen Bezugsrahmen vorgeben.)

In Anlehnung an das Modell von W. Hintze (1985, S. 73) finden wir folgendeAbschatzung fur den Durchmesser des 2× 2× 2-Wurfels:

Da man eine Ecke des Wurfels festhalten und alle moglichen Stellungenmit Manovern erreichen kann, die aus den 90-Zugen von nur 3 Randscheibenerzeugt werden, erreicht man nach k Zugen maximal

Gk = 1 + 6 + 6 · 5 + 6 · 52 + . . .+ 6 · 5k−1 = 1 + 6 · (50 + 51 + 52 + . . .+ 5k−1)= 1 + 6 · (5k − 1)/4

mogliche Stellungen. (Die Identitat ergibt eine Stellung, nach dem erstenZug erreicht man mit 3 Randscheiben, bei denen man jeweils zwei moglicheZuge hat - 90 im oder gegen den Uhrzeigersinn - maximal 6 Stellungen, nachdem zweiten Zug 6 · 5 neue Stellungen - nicht 6 · 6, weil man den ersten Zugnicht ruckgangig machen darf, um neue Stellungen zu erhalten - u.s.w.)

Die Zahl der Zuge k gibt uns eine untere Grenze fur den Durchmesser an,wenn die Zahl der erreichten Stellungen Gk großer oder gleich der Anzahl allermoglichen Positionen des Wurfels ist. Es gilt

Gk = 1 + 6 · (5k − 1)/4 ≥ 7! · 36 ⇔ k ≥ 10Somit ist der Durchmesser mindestens 10, d.h. es gibt eine Stellung, die

mindestens 10 Zuge vom Grundzustand entfernt ist. Zahlt man auch 180-Randscheibenzuge als nur einen Zug (und nicht, wie wir bisher, als zwei 90-Zuge), so gibt es eine exakte Bestimmung des Durchmessers durch P.P Weid-haas (in W. Hintze, 1985, S. 73), die er mit seinem Computerprogramm durch-gefuhrt hat. Danach betragt der Durchmesser des 2× 2× 2-Wurfels 11. LautHintze (1985, S. 74) gibt es 2644 Stellungen mit maximalem Abstand vomGrundzustand (sog. Antipoden). Weidhaas gibt folgendes Beispiel fur einenAntipoden an:

V OV OV R2V R′V R2O2.

90

10.3 Das magische Domino

Abbildung 10.9: Das magische Domino: links im Ausgangszustand, rechts ge-mischt (Quelle: C. Bandelow, 1981, S. 81 )

Im Unterschied zum 2× 2× 2-Wurfel erfordert es neue strategische Uber-legungen, da nur solche Wurfel-Manover-ubetragen werden konnen, die keine90-Zuge mit senkrechten Scheiben enthalten. Laut C. Bandelow (1981, S. 102)sind die wichtigsten Manover fur das Domino:

(R2O2)3(6) → (ov, oh),

R2V 2OH2O′V 2OH2O′R2(10) → (ovl, orv, ohr) und

R2V 2OH2O′V 2OH2O′R2O(11) → (olh, ohr)(oh, or, ov, ol).

Mit dem letzten Manover kann unter Zuhilfenahme von Konjugationen je-de Permutation der 8 Eckencubies erreicht werden. Anschließend lassen sichdie Kantencubies mit dem ersten Manover beliebig umordnen. Da jedoch Um-ordnungen, die sich durch eine Drehung des gesamten Dominos um seine senk-rechte Achse erreichen lassen, nicht erneut gezahlt werden durfen, ergeben sichfur das magische Domino genau

(8!)2/4 = 406425600

verschiedene mogliche Positionen (”Muster“).

91

Abbildung 10.10: (Quelle: W. Hintze, 1985)

10.4 Pyraminx - Die Zauberpyramide

10.4.1 Funktionsweise und Bezeichnungen

Die Segmentierung des Pyraminx erhalt man, indem man einem Tetraeder je-weis zwei Schnitte im gleichen Abstand parallel zu jeder seiner vier Flachenzufugt und dadurch jede Flache in neun gleichgroße gleichseitige Dreiecke zer-teilt. Es entstehen folgende Bestandteile:

• 4 tetraederformige Spitzen,

• 4 oktaederformige Mittelteile,

• 6 tetraederformige Kanten,

die jeweils in drei Schichten angeordnet sind.Im Grundzustand ist jede der vier Flachen mit nur einer Farbe belegt. Wir

nummerieren alle 36 Segmentflachen durch, wie es in folgender Grundrisszeich-nung (Abbildung 10.11) durchgefuhrt ist.

92

Abbildung 10.11: Grundrisszeichnung des Pyraminx (Quelle: D. Joyner, 2002, S.54)

Dabei muss man sich die Pyramide so zusammengefaltet vorstellen, dassdie Segmentflachen (1, 2, 3); (13, 28, 27); (22, 36, 23) und (17, 32, 18) jeweils eineEcke umschließen. Wir stellen die Pyramide nun so vor uns hin, dass dasmittlere Dreieck im Grundriss unten, das linke vorne, das obere rechts unddas rechte links ist und dass wir gerade auf das vordere Dreieck daraufblicken.Nun bezeichnen wir die 4 Ecken mit O(ben), R(echts), L(inks) und H(inten).Fur die Basismanover, die man mit Pyraminx durchfuhren kann, fuhren wirfolgende Bezeichnungen ein:

Sei X ∈ O,R,L,H. Die Seiten des Pyraminx nennen wir ihrer Lage ent-sprechend V (orne), R(echts), L(inks) und U(nten). Wir bezeichnen die Dre-hung der Scheibe, auf der die der Ecke X gegenuberliegende TetraederseiteF ∈ V,R, L, U liegt, um 120 im Uhrzeigersinn mit F1. Die Drehung derangrenzenden mittleren Scheibe um 120 im Uhrzeigersinn bezeichnen wir mitF2 und die Drehung der Ecke selbst um 120 im Uhrzeigersinn, die eigentlichnur einer Umorientierung der Ecke entspricht, mit F3.

Diese Drehzuge bewirken folgende Permutationen der Segmentflachen:

• V1 = (2, 32, 27)(8, 31, 26)(7, 30, 12)(19, 29, 11)(18, 28, 3)(1, 17, 13)(6, 15, 4)(5, 16, 14)

• V2 = (9, 35, 25)(21, 34, 24)(20, 33, 10)

• V3 = (23, 22, 36)

93

• R1 = (3, 36, 17)(11, 34, 16)(10, 35, 6)(24, 31, 5)(23, 32, 1)(2, 22, 18)(9, 20, 7)(8, 21, 19)

• R2 = (12, 33, 15)(26, 29, 14)(25, 30, 4)

• R3 = (27, 28, 13)

• L1 = (1, 28, 22)(5, 29, 21)(4, 33, 9)(14, 34, 8)(13, 36, 2)(3, 27, 23)(11, 26, 24)(12, 25, 10)

• L2 = (6, 30, 20)(16, 31, 19)(15, 35, 7)

• L3 = (17, 32, 18)

• U1 = (13, 18, 23)(14, 19, 24)(15, 20, 25)(16, 21, 26)(17, 22, 27)(28, 32, 36)(29, 31, 34)(30, 35, 33)

• U2 = (4, 7, 10)(5, 8, 11)(6, 9, 12)

• U3 = (1, 2, 3)

Alle moglichen Manover lassen sich als Kombination dieser Drehzuge erzeu-gen. Die Gruppe aller moglichen Positionen des Pyraminx, genannt die

”Pyra-

minx-Gruppe“, wird allerdings schon unter Verwendung von 8 Basismanoverneingehend beschrieben, fur die wir in Anlehnung an D. Joyner (2002, S. 213)und W. Hintze (1985, S. 12 ff.) folgende Manover auswahlen:

• l beschreibt die Drehung der linken Ecke L um 120 im Uhrzeigersinn(Blickrichtung auf die Ecke),

• L beschreibt die Drehung der linken Ecke L zusammen mit der Mittel-scheibe, die neben der linken Ecke liegt, um 120 im Uhrzeigersinn.

• Die weiteren Basismanover r, R, o, O, h und H werden analog definiert.

Außerdem legen wir folgende Notation fest:

• Sei E die Menge der Ecken (Spitzen) des Pyraminx,

• K die Menge der Kantenstucke,

• C die Menge der inneren Teile des Tetraeders (damit sind beweglicheTeile, die nicht in E oder K liegen, gemeint)

• SK die Permutationsgruppe von K und

• AK die alternierende Gruppe von K.

Es soll G = 〈R,L,O,H, r, l, o, h〉 die Pyraminx-Gruppe bezeichnen. JederZug g ∈ G verursacht eine Permutation der Kanten bezeichnet mit σ(g). Manbeachte, dass G die Ecken nicht permutiert!

94

Abbildung 10.12: Die Basismanover (Quelle: W. Hintze, 1985, S. 13)

10.4.2 Lemma

σ : G→ SK ist ein Gruppenhomomorphismus (D. Joyner, 2002, S. 213).

10.4.3 Orientierungen

Die Orientierungskoordinaten werden an einem geordneten Pyraminx festge-setzt. Wir wahlen bei jedem Ecken- bzw. Kantenstuck jeweils eine Seite aus,die wir mit einem imaginaren

”+“ markieren. Angenommen, wir entscheiden

uns fur folgende markierte Segmentflachen:

• 4, 6, 10, 15, 20, 25 (Kantenflachen)

• 1, 13, 17, 23 (Eckenflachen)

Fur jedes Kantenstuck ordnet man einem Zug g ∈ G

95

•”0“ zu, falls diejenige Seite dieses Stucks, die in der geordneten Position

mit”+“ markiert war, durch den Zug g zu jener Seite hingeschickt wurde,

die in der gegenwartigen Position mit”+“ markiert ist.

• Andernfalls ordnet man ihm”1“ zu.

Man erhalt so ein 6-tupel von Orientierungskoordinaten fur die Kanten:~w(g) = (w1, w2, . . . , w6) mit wi ∈ 0, 1∀i ∈ 1, . . . , 6.

Nachfolgend sind die Auswirkungen einiger Basiszuge auf die Kantenorien-tierungen dargestellt:

X ~w(X)H (0, 0, 0, 1, 0, 1)R (0, 0, 1, 0, 1, 0)L (1, 0, 1, 0, 0, 0)O (0, 1, 0, 1, 0, 0)

RO−1R−1O (1, 1, 0, 0, 0, 0)

Tabelle 10.1: Die Basismanover (Quelle: D. Joyner, 2002, S. 213)

Fur jedes Eckenstuck ordnet man einem Zug g ∈ G

•”0“ zu, falls diejenige Seite dieses Stucks, die in der geordneten Position

mit”+“ markiert war, durch den Zug g zu jener Seite hingeschickt wurde,

die in der gegenwartigen Position mit”+“ markiert ist.

•”1“ zu, falls diejenige Seite dieses Stucks, die in der geordneten Position

mit”+“ markiert war, durch den Zug g zu jener Seite hingeschickt wurde,

die man in der gegenwartigen Position mit einer 120-Drehung der”+“-

Seite im Uhrzeigersinn erreicht.

• Andernfalls ordnet man ihm”2“ zu.

Man erhalt so ein 4-tupel von Orientierungskoordinaten fur die Ecken:~v(g) = (v1, v2, v3, v4) mit vi ∈ 0, 1, 2∀i ∈ 1, . . . , 4.

Nachfolgend sind die Auswirkungen einiger Basiszuge auf die Eckenorien-tierungen aufgefuhrt:

X ~v(X)H (0, 0, 0, 1)R (0, 0, 1, 0)L (0, 1, 0, 0)O (1, 0, 0, 0)

96

Fur jedes Basismanover gilt, dass die Summe der Kantenkoordinaten gera-de ist. Da sich jedes g ∈ G als Hintereinanderschachtelung von Basismanoverndarstellen lasst und die Summe gerader Zahlen wieder gerade ist, folgt nachD. Joyner (2002, S. 214)

10.4.4 Proposition

Ist ~w(g) = (w1, w2, . . . , w6) der Orientierungskantenvektor eines Zuges g ∈ G,so gilt

w1 + w2 + . . .+ w6 ≡ 0 (mod2)

10.4.5 Definition

Sei H die illegale Pyraminx-Gruppe, die durch G und”illegale“ Zuge erzeugt

wird (das sind Zuge, die man nur machen kann, wenn man die Kantenstuckeentfernt, miteinander beliebig vertauscht und wieder anmontiert). Illegale Zugeder Mittelstucke oder Ecken sind in H nicht erlaubt.

Sei

H∗ = (s, v, w)|s ∈ SK , v ∈ Z43, w ∈ Z6

2.Analog zur Multiplikation in der Rubikschen Gruppe kann man auch hier

eine Multiplikation ∗ : H∗ ×H∗ → H∗ definieren:(s, v, w) ∗ (s′, v′, w′) = (s ∗ s′, v + v′, w + sw′) (D. Joyner, 2002, S. 215).Damit ergibt sich folgender Satz

10.4.6 Satz

• Mit oben definierter Operation ist H∗ eine Gruppe.

• Da sich die Ecken des Pyraminx beliebig orientieren lassen und die Per-mutationen und Umorientierungen der Kanten wie beim Wurfel durchein semidirektes Produkt beschrieben werden konnen, gilt

H ∼= H∗ ∼= Z43 × (SK n Z6

2).

• Die Abbildung G → H∗, definiert durch g → (σ(g), v(g), w(g)), ist einHomomorphismus.

Bei der Losung des Pyraminx braucht man sich um die Mittelstucke keineGedanken machen, denn:

• Die Mittelteile, die zu einer Ecke gehoren, konnen mit keinem Zug aufeine Mittelscheibe, die neben einer anderen Ecke liegt, gebracht werden.

• Die Mittelteile, die zu einer Ecke gehoren, konnen stets durch Drehungder Ecke mit dieser farblich abgestimmt werden.

97

10.4.7 Satz

G ist isomorph zu

(s, v, w) ∈ H∗|s ist eine gerade Permutation, w1 + w2 + . . .+ w6 ≡ 0(mod2).

Beweis:

1. Wir zeigen: AK = 〈σ(R), σ(L), σ(O), σ(H)〉.Da bei jedem Basismanover, R, L, O und H eine zyklische Vertauschungvon jeweils 3 Kanten passiert, also eine gerade Permutation der Kanten,wissen wir bereits, dass AK ⊇ 〈σ(R), σ(L), σ(O), σ(H)〉.Die Umkehrung zeigen wir folgendermaßen: Wir benennen die Kanten-stucke mit den Ziffern 1, . . . , 6 und zwar so, dass sich die Kanten 1 - 3 aufder Vorderseite von Pyraminx befinden. Die Kante vorne links bezeichnenwir mit 1, die Kante vorne rechts mit 2 und die Kante vorne unten mit3. Dann ist das Manover [R,O−1] = R · O−1 · R−1 · O die zyklischePermutation (1, 3, 2) der Kanten der Vorderseite im Gegenuhrzeigersinn.(Dieses Manover bewegt keine Ecken, orientiert jedoch einige Kanten um,was im Moment keine Rolle spielt, da wir jetzt nur die Permutationenbetrachten.) Da R−1 = R ·R und O−1 = O ·O gilt, kann man (1, 3, 2) alsProdukt von Elementen der Menge σ(R), σ(L), σ(O), σ(H) schreiben.Wahlt man nun i ∈ 4, 5, 6 beliebig und bestimmt s ∈ G so, dasss die Kante i zur Kante 2 hinbewegt ohne dabei die Kanten 1 oder 3zu bewegen (ein solches s lasst sich als Kombination von maximal 2Basiszugen immer finden), dann stellt das Manover s · [R,O−1] · s−1 den3-Zyklus (1, 3, i) dar. Es lasst alle Ecken und anderen Kanten bis aufeventuelle Umorientierungen fest.

Nun wissen wir, dass die Permutationen (1, 3, i) (i ∈ 2, 4, 5, 6) A6∼=

AK erzeugen. Daher gilt ebenfalls AK ⊆ 〈σ(R), σ(L), σ(O), σ(H)〉 undinsgesamt AK = 〈σ(R), σ(L), σ(O), σ(H)〉.

2. Mit eben Gezeigtem folgt, dass die Abbildung G → AK , g → σ(g) sur-jektiv ist.

3. Wir wissen bereits: ∀g ∈ G mit ~w(g) = (w1, w2, . . . , w6) gilt: w1 + w2 +. . .+ w6 ≡ 0 (mod2).

Es bleibt zu zeigen, dass die Abbildung G→ (w1, w2, . . . , w6) ∈ Z62|w1+

w2 + . . .+ w6 ≡ 0 (mod2), g → ~w(g) surjektiv ist.

Die Gruppe (w1, w2, . . . , w6) ∈ Z62|w1+w2+ . . .+w6 ≡ 0 ( mod 2) ∼= Z5

2

ist ein 5-dimensionaler Vektorraum uber Z2. Er wird vollstandig durch

98

die Vektoren ~w(g), g ∈ G aufgespannt, da die 5 Vektoren, die in Ta-belle 10.1 aufgelistet sind, linear unabhangig sind und somit eine Basisbilden. Daraus und aus der Tatsache, dass G eine Gruppe und die Ab-bildung g → ~w(g) ein Homomorphismus ist, folgt, dass die Abbildungauch surjektiv ist.

q.e.d. (D. Joyner, 2002, S. 216)

Bemerkung Eigentlich musste man bei der Betrachtung der Pyraminx Grup-pe die Umorientierung der Mittelstucke ebenfalls einbeziehen. Die oben inAnlehnung an D. Joyner beschriebene Gruppe betrifft daher lediglich dasEcken- und Kantenproblem. Zieht man die Mittelstucke auch in Betracht, sokann man fur sie analog zu den Ecken und Kanten den Orientierungsvektor ~ueinfuhren. Da man die vier Mittelstucke unabhangig voneinander auf dreierleiArten orientieren kann, ist die illegale Pyraminx-Gruppe eigentlich isomorphzu H∗ ∼= Z4

3 × Z43 × (SK n Z6

2) und die Pyraminx-Gruppe G isomorph zu(s, v, w, u) ∈ H∗|s ist eine gerade Permutation, w1 + . . . + w6 ≡ 0 (mod2).Fur diese vollstandige Pyraminx-Gruppe gilt nach W. Hintze (1985, S. 17):

10.4.8 Satz

Das Pyraminx besitzt N0 = 3434 6!25

2= 75582720 mogliche Positionen (Farb-

muster).Beweis: Jede der vier Spitzen kann unabhangig von den anderen auf drei-

erlei Weise orientiert sein. Das gleiche gilt fur die Mittelstucke, was zusammenbereits 34 ·34 = 81 ·81 = 6561 Stellungen ergibt. Nach obigem Satz konnen diesechs Kanten durch alle geraden Permutationen, also auf 6!

2Arten, vertauscht

werden. Weiters muss die Summe der Orientierungskoordinaten der Kanten ge-rade sein, man kann die Koordinate daher nur fur 5 der 6 Kanten frei wahlenund hat dafur 25 Moglichkeiten. Zusammen ergeben diese Uberlegungen dieBehauptung.

99