Flipper

Binärzahlen und das Prinzip der $0$ – $1$ -Dualität sind aus der Welt der Informatik nicht mehr wegzudenken. Auch das Exponat „Flipper“ verkörpert dieses Prinzip der Dualität. Es besteht aus insgesamt vierzehn Weichen, die sich pyramidenförmig auf vier Ebenen mit jeweils 2, 3, 4 und 5 Weichen verteilen, wie in Abbildung 1 zu erkennen.

Das Exponat hat seinen Namen aufgrund der Abschussvorrichtung erhalten, mit der man eine Kugel wahlweise rechts oder links in die oberste Weichenebene befördern kann. Jede Weiche kann die Kugel nach rechts oder nach links ablenken, wobei sie ihre Stellung nach dem Durchlauf der Kugel ändert. Ihnen kann also entweder der Zustand „Kugel läuft nach rechts“ oder „Kugel läuft nach links“ zugeordnet werden. Da jeder Weiche eindeutig einer von zwei Zuständen zugeordnet

(1) $\begin{equation*}2^{14} = 16 384\end{equation*}$

verschiedene Weichenstellungen bzw. Zustände im Exponat möglich. Die Frage, die sich stellt, ist, ob man von einem beliebigen Zustand aus jeden anderen erreichen kann. Dies wollen wir im Folgenden klären.

Und nun … die Mathematik dazu:

Zuerst einmal stellen wir folgende Beobachtungen an, von denen du dich selbst am Exponat vor Ort überzeugen kannst.

(1) Bei einer Serie von Einwürfen der Kugel kommt es nicht auf deren Reihenfolge an. Wirfst du z.B. die Kugel erst links und dann rechts ein, dann ergibt dies denselben Zustand als wenn du die Kugel erst rechts und dann links eingeworfen hättest.

(2) Wirfst du die Kugel auf einer Seite 16 mal ein (also alle links oder alle rechts), dann landest du beim selben Zustand wie vorher. Andersherum, falls du von einem beliebigen Zustand aus links $n$ -mal und rechts $m$ -mal die Kugel einwirfst und der Anfangszustand herauskommt, dann sind sowohl $n$ als auch $m$ durch $16$ teilbar.

Nehmen wir an, wir befinden uns im Zustand $z_0$ . Falls wir die Kugel nun 16-mal links oder rechts einwerfen, erhalten wir nach 2. erneut den Zustand $z_0$ . Um also einen von $z_0$ verschiedenen Zustand zu erhalten, könnten wir z.B. die Kugel 15-mal links und 1-mal rechts einwerfen. Nach 1. ist es in dieser Serie von Einwürfen egal, an welcher Stelle wir den auf der rechten Seite machen. Falls wir zudem ausgehend von $z_0$ 14-mal links und 2-mal rechts in einer beliebigen Reihenfolge die Kugel einwerfen, dann erhalten wir wieder einen von $z_0$ verschiedenen Zustand. Wenn man so fortfährt, erhalten wir ausgehend von $z_0$ , zusätzlich 15 neue Zustände. Von diesen neuen Zuständen aus können wir mit der eben beschriebenen Konstruktionsmethode jeweils weitere 15 neue Zustände konstruieren. Dies lässt sich insgesamt 16-mal wiederholen, bis wir zwangsläufig wegen der Eigenschaft 2. wieder als Zustand $z_0$ erhalten. Insgesamt lassen sich also ausgehend von einem beliebigen Zustand $z_0$ $16^2 - 1 = 255$ verschiedene Zustände konstruieren.

Dies bedeutet aber, dass wir niemals jeden einzelnen Zustand des Gerätes von einem beliebigen Zustand aus erreichen können. Vielmehr gliedern sich die insgesamt $16 384$ Zustände in 64 „Inseln“, zu jeweils 256 Zuständen. Innerhalb der „Inseln“ kann man jeden der 256 Zustände durch Einwerfen der Kugel erhalten. Jedoch wird man niemals mithilfe eines Kugeleinwurfs die „Insel“ wechseln können.

Wie lässt sich feststellen, dass von einem gegebenen Zustand aus, ein anderer erreichbar ist? Um dies beantworten zu können, bezeichnen wir die möglichen Weichenstellungen mit $0$ (Kugel läuft nach links) und 1 (Kugel läuft nach rechts). Jeder Zustand des Exponats lässt sich dann eindeutig in einem Schema der folgenden Art darstellen.

Des Weiteren bezeichnen wir mit $\lambda$ die Operation „Kugeleinwurf links“ und mit $\rho$ die Operation „Kugeleinwurf rechts“. Beachte, dass der Zustand der linken Dachhälfte}, also der Weichen $a,c,f,j$ , nur mittels $\lambda$ , und die der rechten „Dachhälfte“, also der Weichen $b, e, i, n$ , nur mittels $\rho$ geändert werden können. Falls sich die Weichen $a,c,f$ und $j$ dann jeweils im Zustand 0 befinden, duchlaufen deren Zustände durch Anwendung von $\lambda$ die Binärzahlen von 0 bis 15, wie in Abbildung 3 dargestellt.

Genauso verhält es sich, falls sich die Weichen $b, e, i, n$ jeweils im Zustand 1 befinden, dann durchlaufen die Zustände die Zahlen von 0 bis 15 rückwärts, wie in Abbildung 4 dargestellt.

Mithilfe dieser Überlegungen lässt sich die Erreichbarkeit eines Zustandes ausgehend von einem anderen bestimmen. Um dies einzusehen, betrachten wir die folgenden beiden Zustände des Exponats.

Um die Erreichbarkeit von (A) nach (B) zu untersuchen, müssen wir jeweils die Zustände der linken und rechten „Dachhälfte“ vergleichen. Bei (A) sind die Weichen der linken Dachhälfte (grün) $(a,c,f,j)$ im Zustand $0110$ , was der Zahl $6$ entspricht und bei (B) (blau) im Zustand $1100$ , also $12$ . Um also von der linken Dachhälfte von (A) auf die von (B)) zu kommen, müssen wir nach der Überlegung in Abbildung 3 die Kugel $12 - 6 = 6$ mal links einwerfen. Entsprechend ist für die rechte Dachhälfte (rot) eine Änderung von 1101, also 13, zu $1011$ , also $11$ , nötig. Nach der Überlegung von Abbildung 4 ist dies nach einem Einwurf von $13 - 11 = 2$ Kugeln auf der rechten Seite erreicht. Wenn man also in einer beliebigen Reihenfolge 6 mal links und 2 mal rechts die Kugel einwirft, dann stimmt der sich ergebende Zustand mit (B) zumindest auf den beiden Dachhälften überein. Dies ist auch der einzige erreichbare Zustand innerhalb der Insel von (A) mit dieser Eigenschaft. Eine mögliche Abfolge von Übergängen ist in Abbildung 6 dargestellt.

Der erreichte Zustand stimmt jedoch nicht vollständig mit (B) überein, womit (B) von (A) also unerreichbar ist. Dieses Beispiel verdeutlicht insbesondere, dass jeder Zustand innerhalb der Inseln durch seine Dachhälften eindeutig bestimmt ist. Die restlichen Weichen spielen dabei keine Rolle.

Im folgenden Abschnitt wollen wir das Exponat über sogenannte Permutationsgruppen beschreiben. Für den Text sind vertiefende Kenntnisse aus universitärer Algebra nötig.

Permutationsgruppen

Wir bezeichnen mit $Z$ die Menge aller möglichen Zustände des Exponats, welche nach (1) genau $16 384$ Elemente umfasst.

Die Operation „Kugeleinwurf links“ bzw. „Kugeleinwurf rechts“ lassen sich als Abbildungen

$\lambda \colon Z \to Z, \qquad \text{bzw.} \qquad \rho \colon Z \to Z$

der Zustandsmenge in sich selbst auffassen. Im Speziellen erzeugen $\lambda$ und $\rho$ eine Gruppe $(G,\circ)$ mit Einselement $\operatorname{id} \in G$ und der Hintereinanderausführung

$\begin{align*}\circ \colon G \times G, \qquad f \mapsto f \circ g.\end{align*}$

als Gruppenoperation. Die Gruppe $(G,\circ)$ operiert auf der Zustandsmenge $Z$ mittels der Abbildung

$\begin{align*}G \times Z \to Z, \qquad (g,z) \mapsto gz.\end{align*}$

Hierbei beschreibt $z$ den Zustand des Exponats vor dem Kugeleinwurf und $gz$ danach. Wie oben bemerkt, ändert sich der aktuelle Zustand nach 16 Kugeleinwürfen auf einer Seite nicht. Es gilt also

$\begin{align*}\lambda^{16} = \operatorname{id} = \rho^{16},\end{align*}$

wobei $\lambda^{16} \coloneqq \overbrace{\lambda \circ \dots \circ \lambda}^{16-mal}$ . Somit sind $\lambda$ und $\rho$ Permutationen auf $Z$ . Nach 1. hängt der resultierende Zustand bei einer Serie von Einwürfen nicht von deren Reihenfolge ab. Somit kommutieren $\lambda$ und $\rho$ im Speziellen miteinander, sprich

$\begin{align*}\lambda \circ \rho = \rho \circ \lambda.\end{align*}$

Die von $\lambda$ und $\rho$ erzeugte Permutationsgruppe $(G,\circ)$ ist daher kommutativ. Insbesondere ist $G$ isomorph zu $\mathbb{Z}^2_{16}$ und enthält demnach

$\begin{align*}|G| = |\mathbb{Z}^2_{16}| = 256\end{align*}$

verschiedene Elemente. Wie oben bemerkt können wir, ausgehend von einem vorgegebenen Zustand $z \in Z$ insgesamt $255$ andere Zustände erreichen, sprich die Gruppenoperation auf $Z$ ist nicht transitiv. Im Speziellen ändern wir den Zustand $z$ des Exponats genau dann nicht, falls wir die Identitätsabbildung $\operatorname{id}$ anwenden. Die Permutationsgruppe $G$ operiert also semiregulär auf $Z$ . Insbesondere enthält der Stabilisator eines beliebigen Zustands $z\in Z$ nur die Indentitätsabbildung, sprich

$\begin{align*}G_z \coloneqq \{g \in G \mid gz = z\} = \{\operatorname{id}\}.\end{align*}$

Nach der Bahnenformel gilt dann

$\begin{align*}|G| = |Gz| |G_z| = |Gz|.\end{align*}$

Somit enthält die Bahn eines beliebigen Punktes $z \in Z$ genau 256 Elemente. Hier ist die Bahn eines Zustandes $z \in Z$ gegeben durch die Menge

$\begin{align*}Gz \coloneqq \{ gz \mid g \in G\},\end{align*}$

Durch das Lemma von Burnside könnnen wir auch die Anzahl der Bahnen $|Z/G|$ bestimmen. Demnach gilt

$\begin{align*}|Z/G| = \frac{1}{|G|} \sum_{z \in G_z} |G_z| = \frac{16384}{256} = 64.\end{align*}$

Die Bahnen eines Zustandes $z \in Z$ sind also genau die „Inseln“ aus dem Abschnitt weiter oben.

Literatur

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

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