Zauberwürfel

Der Zauberwürfel ist ein Drehpuzzle in Würfelform. Mit seiner Hilfe kann man sich die Symmetrische Gruppe anschaulich vorstellen und mit ihre Hilfe Aussagen über die Lösbarkeit treffen. Wie ein Scharfschütze.

Das Logo des Wikis: ein prächtiger Zauberwürfel

Symmetrische Gruppe

Die Symmetrische Gruppe [math]S_n[/math] ist die Gruppe, die aus allen Permutationen (Vertauschungen) einer Menge besteht. Man bezeichnet [math] n \in ℕ [/math] den Grad der Gruppe (Anzahl der Elemente).

Der Operator in der symmetrischen Gruppe ist die Komposition (Hintereinanderausführung) der Permutationen.

Das neutrale Element der Gruppe ist die Identitätsabbildung, welche bewirkt, dass keine Permutation stattfindet.

Die symmetrische Gruppe [math]S_n[/math] ist endlich und besitzt die Ordnung [math]n![/math].

Für Grad [math]n\gt 2[/math] ist die [math]S_n[/math] nichtabelsch.

Zur Veranschaulichung folgt ein Beispiel anhand eines Bücherregals:

Zunächst führen wir die Anfangsaufstellung der Bücher ein.

Startaufstellung

Als nächstes wird die Permutation [math] \sigma [/math] auf die Aufstellung angewandt.

[math] σ = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 4 & 5 \end{pmatrix} [/math]

Permutation mit [math] \sigma [/math]

Zuletzt wird [math] \mu [/math] auf die bereits von σ permutierte Aufstellung angewandt. Hieraus ergibt sich für die Endaufstellung = [math] \sigma \circ \mu [/math]

[math] μ = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 5 & 1 & 2 \end{pmatrix} [/math]

Permutation mit [math] \sigma \circ \mu [/math]

Zykelschreibweise

Die Vertauschungen werden häufig in sogenannten "Zykeln" geschrieben. Dabei werden die Positionen die durch die Vertauschungen geändert werden hintereinander in eine Klammer geschrieben. Dementsprechend ist die Zykelschreibweise nicht eindeutig. ?Die klassische Notation ist in der Klammer aufsteigend?.

Die Zykelschreibweise von [math]\sigma[/math] wäre zum Beispiel:

[math] \sigma = ( 1 ~ 2 ~ 3) (4) (5)[/math]

Dabei werden in der Notation die Zyklen <2 nicht mitgeschrieben.

Analog zu oben wäre die Schreibweise zu [math]\mu[/math] :

[math] \mu = ( 1 ~ 4) (2 ~3 ~ 5)[/math]

[math]\mu[/math] Veranschaulicht

Zu beachten ist hierbei, dass die Zykelschreibweise im generellen nicht kommutiert:

[math] \sigma \circ \mu = ( 1 ~ 2 ~ 3) ( 1 ~ 4) (2 ~3 ~ 5)= (1 ~ 4 ~ 2)(3~5) [/math]

[math] \mu \circ \sigma = ( 1 ~ 4) (2 ~3 ~ 5)( 1 ~ 2 ~ 3)= (1 ~ 3 ~ 4)(2~5) [/math]

[math]\mapsto \sigma \circ \mu \neq \mu \circ \sigma [/math]

Nice to know: Disjunkte Zykel kommutieren

Signumsabbildung

Die Signumsabbildung ist eine surjektive Abbildung welche eine belibige Permutation auf [math] 1 [/math] oder [math] -1 [/math] abbildet. Dabei kann man die [math] 1 [/math] so interpretieren, dass die abgebildete Permutation eine grade Anzahl von Fehlstellen hat. Die [math] -1 [/math] zeigt somit eine ungerade Anzahl von Fehlstellen an.

Als Fehlstelle versteht man in diesem Kontext, dass ein Element welches vorher hinter einem anderen Element platziert war durch die Permutation vor das andere Element gezogen wurde. Ein Beispiel für eine Permutation mit einer Fehlstelle wäre:

[math] \mu = ( 1 ~ 2 ~ 3) \longrightarrow sng(\mu) = -1 [/math]

In diesem Beispiel entsteht die Fehlstell dadurch, dass die [math] 3 [/math] "vor" die [math] 1 [/math] geschoben wird.

Für eine generelle Berechnung der Fehlstellen kann die Formel:

[math]sgn(\pi) = \prod_{1 \leq i\lt j \leq n} \frac{\pi(j)-\pi(i)}{j-i}[/math]

genutzt werden.

Die Abbildung : [math]sgn: S_n \mapsto \{ \pm 1 \}[/math] ist dabei ein Gruppenhomomorphismus.

Alternierende Gruppe

Die alternierende Gruppe vom Grad [math]n[/math] ist eine Untergruppe der symmetrischen Gruppe [math]S_n[/math]. Sie besteht aus allen geraden Permutationen einer [math]n[/math]-elementigen Menge.

Sie ist definiert als: [math]A_n[/math] := [math]\{\sigma \in S_n |sgn(\sigma)=1\} \subset S_n [/math].

Die Verknüpfung der alternierenden Gruppe ist, wie auch die der symmetrischen Gruppe, die Verkettung (Hintereinanderausführung) der Permutationen.

Lemma: [math]A_n[/math] wird erzeugt von Zykeln der Form [math](12i)[/math] mit [math]i \in \{3,...,n\}[/math] mit [math]n \geq 3[/math].

D.h. für jedes [math]\sigma \in A_n[/math] gibt es eine Darstellung [math]\sigma = (12i_1)(12i_2)...(12i_n)[/math] mit [math]i_1 ...i_n \in \{3,...,n\}[/math].

Anwendung auf den Zauberwürfel

Gruppeneigenschaften

Sowohl bei der Betrachtung der Würfelecken, als auch der Würfelkanten stellt, jede Drehung (jeweils entgegen des mathematischen Uhrzeigersinns) einer der Würfelscheiben eine zyklische Permutation dar, die als Element der symmetrischen Gruppe [math]S_8[/math] (für die Permutionen der Eckwürfelchen) oder [math]S_12[/math] (für die Permutationen der Kanten) aufgefasst werden kann. Jede mögliche Würfeldrehung ist dabei als Zusammensetzung von Verknüpfungen der genannten sechs Grundpermutationen [math]\{V,H,R,L,O,U\}[/math] darstellbar.

Sei [math]G[/math] die Menge aller möglichen Drehoperationen am Zauberwürfel. Mit der Verknüpfung [math]\circ: G \times G \rightarrow G [/math] wird G eine Gruppe:

1. Die Abgeschlossenheit durch die Verknüpfung [math]\circ[/math] der Gruppenelemente ist gegeben.
2. Da auf Elemente aus [math]S_n, n \in \{8,12\}[/math] zurückgegriffen wird, gilt das Assoziativgesetz.
3. Das neutrale Element [math]e_n, n \in \{8,12\}[/math] ist die Nulloperation, also das Nicht-Verdrehen des Würfels, sodass gilt: [math]\forall g \in G g \circ e = e \circ g =p [/math]
4. Es existiert ein eindeutiges Inverses [math]g^{-1}[/math]zu jedem [math] g \in G : g \circ g^{-1} = g^{-1} \circ g = e [/math]. Für die Grundpermutationen ist dies anschaulich jeweils die Rückdrehung im mathematischen Uhrzeigersinn.

Die Gruppe [math]G[/math] ist nicht abelsch; so ist beispielsweise [math]V \circ L \neq L \circ V [/math].

Ordnung

Die Ordnung der Gruppe G ergibt sich aus der Anzahl [math]\vert G \vert[/math] der möglichen Drehoperationen. Zu deren Bestimmung ist die natürliche Bijektion zwischen der Gruppe [math]G[/math] und aller möglichen, durch ein [math]g \in G[/math] erreichten Würfelposition, nützlich:

Die Würfelposition kann eindeutig durch den Positionsvektor [math](\rho, \sigma, x, y) \in S_8 \times S_12 \times (\mathbb{Z} / 3\mathbb{Z})^8 \times (\mathbb{Z} / 2\mathbb{Z})^{12} [/math] dargestellt werden. Dabei zeigt [math]\rho \in S_8[/math] die Permutation der Eckwürfelchen, [math]\sigma \in S_12 [/math] die Permutation der Kanten, [math]x \in (\mathbb{Z} / 3\mathbb{Z})^8[/math] die Orientierung der Eckwürfelchen und [math]y \in (\mathbb{Z} / 2\mathbb{Z})^{12}[/math] die Orientierung der Kanten ausgehend von der Grundstellung, an. Die Orientierungen sind dabei folgendermaßen definiert:

Für die Orientierung der Ecken wird die Tatsache verwendet, dass jeder Eckwürfel genau eine gelbe oder weiße Seite hat. Ist diese Seite auf der Deckenfläche (diese wird so gewählt, dass sich eine weiße oder gelbe Teilfläche auf der mittleren Position befindet) positioniert, so wird der Orientierung die Äquivalenzklasse [math][0][/math] zugeordnet.Ist sie zur Seite orientiert, wird ihr die [math][1][/math] zugeordnet, und ist sie nach vorne orientiert, die [math][2][/math]. Wird dies für jedes der acht Eckwürfelchen [math]x_i, i \in \{1, \ldots, 8\}[/math]durchgeführt, erhält man den Orientierungsvektor [math]x=(x_1, \ldots, x_8) \in (\mathbb{Z} / 3\mathbb{Z})^8 [/math].

Für die Orientierung der Kanten