Hab den Mut

Sicher hast Du Dich auch schon einmal mit dem Zauberwürfel beschäftigt, oder zumindest anderen dabei zugesehen. Natürlich hat dieser Würfel viel mit Mathematik zu tun — aber was genau? Auch das Puzzle „Hab den Mut“ ist von ähnlicher Natur. Die Gemeinsamkeit besteht darin, dass man kann gewisse Transformationen nacheinander anwenden kann, die sich alle wieder umkehren lassen.

Und nun … die Mathematik dazu:

Die Gruppentheorie ist eine mathematische Disziplin, die sich genau mit solchen Strukturen beschäftigt: Gegeben ist eine bestimmte Struktur (zum Beispiel der Zauberwürfel oder das Schiebepuzzle „Hab den Mut“), die sich in bestimmter Weise transformieren lässt. Damit meinen wir, dass es eine Menge von zulässigen Operationen gibt, die in einen anderen Zustand überführen, sodass sich je zwei dieser Operationen hintereinander ausführen lassen und es zu jeder Operation eine eindeutige inverse Operation gibt, die diese wieder rückgängig macht.Diese Operationen auf der Struktur erzeugen nun eine Gruppe. Du kennst bestimmt schon viele Gruppen aus dem Schulunterricht: Hier ein paar Beispiele:
- Nehmen wir einmal an, dass $X=\mathbb R$ die reelle Gerade ist, auf der wir einen Punkt $\mathbf p$ besonders auszeichnen. Wir können nun auf diese Gerade eine Verschiebung $\tau_r$ um eine reelle Zahl $r\in\mathbb R$ anwenden, d.h. $\tau_r$ überführt den Punkt $x$ in $x+r$ und damit insbesondere $\mathbf p$ in $\mathbf p+r$ . Man überlegt sich, dass das Hintereinanderausführen der Verschiebung $\tau_r$ und $\tau_s$ genau dasselbe ist wie $\tau_{r+s}$ . Daher lässt sich also $\tau_r$ durch Anwendung von $\tau_{-r}$ eindeutig umkehren. Damit erzeugt eine Menge $\{\tau_r\,|\,r\in R\}$ von zulässigen Verschiebungen eine Gruppe $G$ , die auf der reellen Geraden operiert. Hierbei können wir die Menge $R\subseteq\mathbb R$ beliebig wählen, sodass mit $r\in R$ auch $-r\in R$ gilt. Setzen wir zum Beispiel $R=\{-1,1\}$ , so erhalten wir für $G$ genau die ganzzahligen Verschiebungen: Jede Verschiebung um eine ganze Zahl $z\in\mathbb Z$ lässt sich als $|z|$ -fache Ausführung der Verschiebung $\tau_{\mathrm{sgn}(z)}$ auffassen. Ebenso können wir aber auch $R=[-1,1]$ wählen. Dann erhalten wir tatsächlich für $G$ alle Verschiebungen um beliebige reelle Zahlen: Jede Verschiebung $\tau_s$ mit $s\in\mathbb R$ beliebig, lässt sich als $\lceil|s|\rceil$ -fache Ausführung der Verschiebung $\tau_r$ mit $r=s/\lceil|s|\rceil\in[-1,1]$ auffassen.
- In ähnlicher Weise kann man auch eine Gruppe durch Drehungen erzeugen. Dazu nehmen wir als Struktur $X$ den Einheitskreis $K=\{(x,y)\in\mathbb R^2\,|\,x^2+y^2=1\}$ zusammen mit dem ausgezeichneten Punkt $\mathbf p$ . Sei nun $\rho_\alpha$ die Drehung um den Winkel $\alpha\in\mathbb R$ (im Bogenmaß). Wie oben überzeugt man sich davon, dass die Hintereinanderausührung von $\rho_\alpha$ und $\rho_\beta$ genau $\rho_{\alpha+\beta}$ ergibt ( $\alpha,\beta\in\mathbb R$ ). Wieder können wir die von den Drehungen $\{\rho_\alpha\,|\,\alpha\in R\}$ erzeugte Gruppe $G$ betrachten (für eine Menge $R\subseteq\mathbb R$ von zulässigen Winkeln, sodass mit $\alpha\in R$ auch $-\alpha\in R$ ). Nehmen wir zum Beispiel für $R=\{-2 \pi/n,2\pi/n\}$ , so erhalten wir für $G$ genau diejenigen Drehungen um ein Vielfaches des Winkels $2\pi/n$ . Das sind genau die orientierungserhaltenden Selbstabbildungen des regelmäßigen $n$ -Ecks. Ebenso könnten wir aber auch $R=(-\pi,\pi)$ wählen und erhielten auf diese Weise für $G$ alle Drehungen $\rho_\alpha$ um den Ursprung.
- Nimmt man als Struktur $X$ ein Deck mit $n$ Karten, die auf einem Tisch offen ausgelegt sind, so kann man als Operationen bestimmte zulässige Umordnungen dieser Karten betrachten. Wählt man zum Beispiel als zulässige Umordnungen die Vertauschungen von je zwei benachbarten Karten, so erzeugen diese eine Gruppe: In der Tat lässt sich jede dieser Umordnung rückgängig machen, indem man sie einfach erneut anwendet. Man überlegt sich jedoch auch, dass man jede beliebige Umordnung der Karten aus den paarweisen Vertauschungen zweier benachbarter Karten kombinieren kann. Diese Gruppe aller Vertauschungen wird als die sogenannte volle symmetrische Gruppe vom Grade $n$ bezeichnet.
Es gibt noch zahlreiche weitere solcher Beispiele. Vielleicht versuchst Du selbst einmal einige zu finden. Auch hinter dem Exponat „Hab den Mut“ verbirgt sich eine besondere Gruppe. Diese permutiert und dreht die neun Plättchen mit den Buchstaben. Im Folgenden wollen wir diese Gruppe — und damit das Exponat — genauer verstehen.

Zum Exponat „Hab den Mut“

Aber welche Gruppe verbirgt sich hinter dem Exponat genau? Das wollen wir jetzt besser verstehen. Gegeben sind neun gleichartige Plättchen, die in einem $3\times 3$ -Quadrat angeordnet sind und von denen wir jeweils vier, die an einer Ecke ein kleines $2\times 2$ -Quadrat bilden, zyklisch rotieren können. Dabei werden die einzelnen Teile allerdings auch um jeweils $90^\circ$ gekippt (siehe nachfolgende Abbildung 1).

Alle anderen Operationen setzen sich nun — wie in den obigen Beispielen — aus diesen vier Drehungen zusammen, d.h. unsere Gruppe von Umordnungen wird durch die vier Drehungen $x,y,z,w$ erzeugt. Führt man jede dieser Drehungen vier mal hintereinander aus, so gelangt man wieder zum Ausgangszustand, d.h. es gelten die Relationen $x^4=y^4=z^4=w^4=\mathrm{id}$ (die identische Abbildung). Aber lässt sich auch jede denkbare Anordnung der neun Teile durch Hintereinanderausführen der vier Drehungen erreichen? Das heißt: Kann man jede Umordnung und anschließende Verdrehung der neun Teile aus den Drehungen $x,y,z,w$ kombinieren?

Dieser Frage wollen wir im Folgenden nachgehen. (Mathematisch ausgedrückt: Welche Untergruppe des Kranzproduktes $C_4\wr S_9$ der zyklischen Gruppe mit vier Elementen, die den möglichen Drehungen einer Kachel entspricht, und der symmetrischen Gruppe auf neun Ziffern, die den möglichen Permutationen der Kacheln entspricht, erzeugen die Drehungen $x,y,z,w$ ?)

Dazu nummerieren wir die Kacheln von $1$ bis $9$ durch und identifizieren sie zunächst gemäß der nachstehenden Abbildung 2 miteinander:

Was bedeutet nun diese Identifikation und warum ist unsere gewählte Identifikation so gut geeignet für das Studium des Exponats? Nun, die Identifikation erlaubt es uns, zu jeder Permutation $\sigma\in S_9=\mathrm{Sym}(\{1,\ldots,9\})$ eine Umordnung des Exponats zu assoziieren, indem wir das Plättchen $i$ in das Plättchen $\sigma(i)$ überführen — gemäß der gewählten Identifikation der Plättchen in Abbildung 2. Auf diese Weise erhalten wir also eine Einbettung der symmetrischen Gruppe $S_9$ auf neun Ziffern in die Gruppe aller Umordnungen unseres Exponats. Sei zusätzlich noch $t$ diejenige Umordnung, die nur das mittlere Plättchen (Nummer $5$ ) um $180^\circ$ verdreht (sodass $t^2=\mathrm{id}$ die identische Umordnung ist). Unsere gewählte Identifikation ist so günstig, da sich die Erzeuger $x,y,z,w$ jetzt sehr schön mit Hilfe der gewählten Kopie von $S_9$ und der Drehung $t$ ausdrücken lassen:

Die Drehung $x$ rotiert die Plättchen $1,2,5,4$ zyklisch und entspricht genau dem $4$ -Zyklus $(1,2,4,5)$ von $S_9$ (denn sie ist mit der gewählten Identifikation der Plättchen kompatibel; hierbei verwenden wir die Zyklenschreibweise für Permutationen). Ebenso erhalten wir auch, dass genau $w=(5,6,9,8)$ gilt. Bei den anderen beiden Drehungen $y$ und $z$ müssen wir allerdings mehr aufpassen. Wenn wir zum Beispiel den $4$ -Zyklus $(2,3,6,5)$ mit der Drehung $y$ vergleichen, so erkennen wir, dass die Plättchen $2$ und $3$ unter beiden Umordnungen gleich abgebildet werden, die Plättchen $5$ und $6$ hingegen werden zwar an die gleiche Stelle rotiert, sind jedoch am Ende unter den beiden Umordnungen jeweils um $180^\circ$ entgegengesetzt ausgerichtet. Man überlegt sich daher, dass $y=t^{-1}(2,3,6,5)t=t(2,3,6,5)t$ . In gleicher Weise erhält man auch, dass $z=t(4,5,8,7)t$ gilt. Dies alles wird nochmal in folgender Abbildung 3 zusammengefasst:

Aus den eben ausgeführten Überlegungen ergibt sich somit, dass die von $x,y,z,w$ erzeugte Gruppe $G$ von Umordnungen eine Untergruppe des Kranzproduktes $\langle t\rangle\wr S_9$ ist. Hierbei ist $S_9$ die gemäß der Identifikation in Abbildung 2 gewählte „Kopie“ und $\langle t\rangle\cong C_2$ die von $t$ erzeugte Gruppe mit zwei Elementen.

Aber welche Untergruppe erhalten wir nun genau? Dazu bemerken wir, dass sich jede aus $x,y,z,w$ erzeugbare Umordnung $g\in G$ eindeutig als Produkt $g=\sigma.r\in S_9\ltimes C_2^9$ schreiben lässt (als Element des semidirekten Produktes). Hierbei überführt $\sigma$ jedes Plättchen $i$ an die gewünschte Stelle $\sigma(i)$ und $r$ rotiert anschließend jedes einzelne Plättchen, sodass es die gewünschte Ausrichtung bekommt (verändert die Position der Plättchen also nicht mehr). Wir nennen $\sigma$ den Permutationsanteil von $g$ und $r$ den Rotationsanteil.

Zuerst wollen wir den Permutationsanteil von $G$ verstehen, also die möglichen Umordnungen, die wir aus $x,y,z,w$ erzeugen können, wenn wir die Drehungen der einzelnen Plättchen vernachlässigen (d.h. wir wollen den Quotienten $\overline{G}$ von $G$ entlang der natürlichen Abbildung $\langle t\rangle\wr S_9\to S_9$ verstehen). Wir behaupten, dass wir alle überhaupt möglichen Permutationen der neun Plättchen aus $x,y,z,w$ kombinieren können (d.h. $\overline{G}=S_9$ ):

Dazu berechnen wir den Ausdruck $[\overline{x},\overline{y}]=\overline{xyx^{-1}y^{-1}}$ (den sogenannten Kommutator der Permutationen $\overline{x}$ und $\overline{y}$ ): $\overline{xy}=(1,3,6,5,4)$ , $\overline{x^{-1}y^{-1}}=(1,4,6,3,2)$ , und somit

$\overline{xyx^{-1}y^{-1}}=(1,3,6,5,4)(1,4,6,3,2)=(1,2)(5,6).$

Durch Konjugation (d.h. Verschiebung der vier Ziffern $1,2,5,6$ mittels Vorkompostion mit $\overline{g}^{-1}$ und Knachkomposition mit $\overline{g}$ für eine geeignete Umordnung $g\in G$ ) lässt sich nun jede beliebige Permutation der Form $(a,b)(c,d)$ ( $a,b,c,d\in\{1,\ldots,9\}$ paarweise verschieden) erreichen (d.h. vom gleichen Zykeltyp). Damit ist aber die gesamte Konjugationsklasse des Elementes $(1,2)(5,6)$ unter der symmetrischen Gruppe auf neun Ziffern $S_9$ in der von den vier Basisdrehungen $x,y,z,w$ erzeugten Gruppe enthalten. Damit muss diese mindestens die davon erzeugte alternierende Gruppe $A_9$ enthalten (denn diese ist einfach). Da jede der Drehungen $x,y,z,w$ aber ein Zyklus gerader Länge ist, also eine ungerade Permutation liefert, muss die erzeugte Gruppe sogar ganz $S_9$ sein. Es lassen sich also alle denkbaren Permutationen der Kacheln aus $x,y,z,w$ kombinieren. Wir müssen also nur noch die möglichen Rotationsanteile von Elementen $g\in G$ verstehen.

Dieser Aufgabe widmen wir uns jetzt: Dazu beobachten wir zunächst, dass sich bei allen Erzeugern $x,y,z,w$ die Rotationsanteile der einzelnen Plättchen jeweils zu null aufsummieren (d.h. es werden nur gerade viele Plättchen um $180^\circ$ umgedreht). In der Tat ist $x=(1,2,4,3)$ und $w=(5,6,9,8)$ — diese Elemente haben also gar keine Rotationsanteile (d.h. insbesondere werden null $=$ gerade viele Plättchen um $180^\circ$ nachrotiert). Für die Elemente $y,z$ erhalten wir: $y=t(2,3,6,5)t=(2,3,6,5)t^{(2,3,6,5)}t$ und $z=t(4,5,8,7)t=(4,5,8,7)t^{(4,5,8,7)}t$ (hierbei bedeutet $a^b=a^{-1}ba$ das mit $a$ konjugierte Element $b$ ). Damit werden bei $y$ die Plättchen $2$ und $5$ und bei $z$ die Plättchen $5$ und $8$ um $180^\circ$ nachrotiert (also gerade viele).

Man überlegt sich nun weiter, dass die Bedingung, dass sich alle Rotationen der einzelnen Plättchen zur identischen Rotation aufsummieren, eine unter Permutation der „Koordinaten“ (d.h. der Plättchen $1$ bis $9$ ) invariante Untergruppe $U$ von $C_2^9$ definiert (d.h. $u=(u_1,\ldots,u_9)\in U$ genau dann, wenn $u_1\cdots u_9=\mathrm{id}$ ). Damit rechnet man nach, dass dann alle Rotationsanteile von Elementen aus $G$ in $U$ liegen müssen (dies folgt aus der Invarianz der Bedingung unter Permutation der neun Plättchen und daraus, dass die Rotationsanteile der Erzeuger $x,y,z,w$ in $U$ liegen).

Wir behaupten nun sogar, dass jede Rotation $u\in U$ in $G$ liegt, also aus den Erzeugern $x,y,z,w$ kombiniert werden kann. Damit muss dann $G=U\cdot S_9=U\rtimes S_9$ gelten und wir können genau überprüfen, ob eine gegebene Umordnung des Exponats aus den Drehungen $x,y,z,w$ kombiniert werden kann, indem wir erst den Permutationsanteil „abziehen“ und dann überprüfen, ob der übrigbleibende Rotationsanteil die obige Bedingung erfüllt (also in $U$ liegt).

Es bleibt also zu zeigen, dass $U$ eine Untergruppe von $G$ ist. Dazu berechnen wir den Ausdruck $([x,y])^2=(xyx^{-1}y^{-1})^2$ (also das Quadrat des Kommutators von $x$ und $y$ ) in der folgenden Abbildung 4:

Die Rechnung zeigt, dass $g=([x,y])^2$ alle Plättchen an ihrem Platz lässt und genau die Plättchen $1,2$ und $5,6$ um $180^\circ$ umdreht. Also liegt $g=([x,y])^2$ in der Untergruppe $U$ und ist nicht das neutrale Element $\mathrm{id}$ , das kein Plättchen verändert. Aus der Darstellungstheorie wissen wir aber, dass der $S_9$ -Modul $U$ irreduzibel ist, d.h. die von $g$ unter $S_9$ invariante erzeugte Untergruppe muss ganz $U$ sein. Damit haben wir aber gezeigt, dass $\langle g^{S_9}\rangle=U\subseteq G$ gilt (hierbei ist $g^{S_9}$ die Menge der Konjugierten von $g$ untere Elementen von $S_9$ ), was zu zeigen war. Wir haben somit also die Gruppe $G$ vollständig verstanden. Es lässt sich also leicht überprüfen, ob wir eine gegebene Anordnung des Exponats wieder in den Ausgangszustand überführen können.

Die Anzahl der zulässigen (d.h. aus $x,y,z,w$ kombinierbaren) Anordnungen ist somit gleich der Größe der Gruppe $G$ , also $|G|=|U||S_9|=2^8\cdot 9!=92897280$ (hierbei ist $n!=n\cdot(n-1)\cdots1$ die Fakultätsfunktion). Nimmt man es ganz genau, so beachtet man noch, dass die Buchstaben $\mathrm{H}$ und $\mathrm{N}$ punktsymmetrisch sind. Ob also bei diesen beiden eine $180^\circ$ -Drehung ausführen oder nicht, ist egal. Daher würde es dann nur $|G|/2=46448640$ mögliche Anordnungen geben (denn, wenn man einen der beiden Buchstaben „flippt“, muss man auch den anderen flippen, gemäß der Bedingung an die Elemente von $U$ ).

Aber wie löst man nun das Puzzle?

Wie viele Züge braucht man höchstens von einer zulässigen Anordnung des Exponats in den Ausgangszustand? Diese Frage ist deutlich schwieriger zu beantworten als die Bestimmung der von $x,y,z,w$ erzeugten Gruppe $G$ oben. Zunächst wollen wir eine (viel zu grobe) obere Schranke dafür angeben: Jedes Element der Gruppe $G$ lässt sich als Verkettung der Drehungen $x,y,z,w$ und ihrer Inversen schreiben. Sagen wir, dass die „Elementaroperationen“ genau die Drehungen $x,x^2,x^3,y,y^2,y^3,z,z^2,z^3,w,w^2,w^3$ sind.

Wir fragen uns nun, wie viele solcher Elementaroperationen wir mindestens hintereinander ausführen müssen, um ein beliebiges Element $g\in G$ zu erreichen.

Wir wissen, dass $|G|=2^8\cdot 9!$ gilt (siehe oben). Damit überlegt man sich, dass wir spätestens nach $(|G|-1)$ -vielen Zügen jede zulässige Umordnung $g\in G$ erreichen können, bis man also die Worte „Hab den Mut“ wieder lesen kann. Diese Zahl ist allerdings viel viel viel zu groß. zum Vergleich: Ein Zauberwürfel lässt sich immer in höchstens $22$ Zügen in seinen Ausgangszustand überführen.

Daher wollen wir nun noch eine untere Schranke angeben, die der Realität schon näher kommt: Dazu überlegen wir uns, wie viele zulässige Umordnung wir nach Ausführung von genau $n$ -vielen Elementaroperationen wir höchstens erhalten können ( $n\in\mathbb N$ ). Sei $u_n$ die Anzahl dieser Umordnungen. Für $n=0$ erhalten wir schlicht $u_n=1$ , denn wir können, ohne etwas zu tun, nur die identische Umordnung erzeugen. Für $n=1$ ergibt sich $u_1=4\cdot 3$ , denn dies ist genau die Anzahl der Elementaroperationen und jede von diesen liefert eine andere Umordnung. Nehmen wir nun an, wir würden $u_n$ ( $n\geq 1$ ) kennen. Sagen wir, dass wir genau $n$ Elementaroperationen $x,x^2,x^3,y,y^2,y^3,z,z^2,z^3,w,w^2,w^3$ ausgeführt haben und, dass die letzte ein Vielfaches von $x$ war. Dann ergibt es keinen Sinn, erneut ein Vielfaches von $x$ anzuwenden, denn dadurch erhielte man eine Umordnung, die sich schon in $n$ oder weniger Zügen erreichen lässt. Also kann angenommen werden, dass dann im $(n+1)$ -ten Zug eine der Elementaroperationen $y,y^2,y^3,z,z^2,z^3,w,w^2,w^3$ ausgeführt wird. Wir erhalten also, dass $u_{n+1}\leq 9u_n$ . Es ergibt sich also für $n\geq 1$ und die Anzahl aller in $n$ oder weniger Zügen erreichbaren Konfigurationen $s_n$ , dass

$s_n\coloneqq\sum_{i=0}^n{u_n}\leq 1+12\cdot\sum_{i=0}^{n-1}{9^i}=1+12\frac{9^n-1}{9-1}=1+\frac{3}{2}(9^n-1).$

Wieviele Züge braucht man also mindestens um jede zulässige Umordnung zu erreichen? Sagen wir $n\geq 1$ sei die kleinste Zahl, sodass alle Elemente $g\in G$ in höchstens $n$ Zügen erreicht werden können. Dann muss sicher $s_n=|G|$ gelten, und damit gemäß unserer obigen Rechnung

$z_n=|G|\leq 1+\frac{3}{2}(9^n-1).$

Dies führt auf $n\geq 9$ . Das ist schon deutlich realistischer. Aber wie groß ist die kleinste Zahl $n$ an benötigten Zügen wirklich? Finde es selbst heraus, indem Du am Exponat herumprobierst. Vielleicht willst Du ja auch ein kleines Computerprogramm schreiben, dass das Problem löst?

Es ist sinnvoll, das Problem in Etappen zu unterteilen: Zunächst rotiert man das Plättchen $1$ (als $\mathrm{H}$ ) an die richtige Stelle (oben links). Danach löst man das kleinere übriggebliebene Teilproblem usw.

Literatur

[1] https://de.wikipedia.org/wiki/Symmetrische_Gruppe

[2] https://de.wikipedia.org/wiki/Freie_Gruppe

[3] https://de.wikipedia.org/wiki/Cayleygraph

[4] https://de.wikipedia.org/wiki/Zauberwürfel

[5] https://de.wikipedia.org/wiki/Kranzprodukt