Eine Reihe von kreisförmig angeordneten Lampen sind so installiert, dass die Lichtschalter jeweils nicht nur die zugehörige Lampe ein- oder ausschalten, sondern auch ihre Nachbarn.
Wie viele Lichtschalter musst du betätigen, um alle Lampen einzuschalten – und vor allem welche?
Zunächst ist es klar, dass jeder der Schalter höchstens einmal betätigt werden muss (zweimalige Betätigung macht die Änderung nur rückgängig).
Führt man bei dem Problem mit 4 Lampen die Variablen $x_1$, $x_2$, $x_3$, $x_4$ ein, die angeben, ob der jeweilige Schalter gedrückt wurde, kann man die Aufgabe als lineares Gleichungssystem formulieren:
Wenn die ursprüngliche Status der $i$-ten Lampe durch $b_i$ ($b_i$ = 1: Lampe ist eingeschalten, $b_i = 0$: Lampe ist ausgeschalten) gegeben ist, so lautet das Gleichungssystem \[ \begin{alignat}{7} x_1 && + x_2 && && + x_4 & = b_1\\ x_1 && + x_2 && + x_3 && & = b_2\\ && x_2 && + x_3 && + x_4 & = b_3\\ x_1 && && + x_3 && + x_4 & = b_4 \end{alignat} \]
Da alle Variablen nur 0 oder 1 annehmen können, und sich zweimaliges Betätigen des Schalters wieder aufhebt, können wir im $\mathbb{F}_2$, dem Körper mit 2 Elementen rechnen (es gilt also die Rechenregel $1 + 1 = 0$).
Die Aufgabe ist unabhängig von der Wahl der $b_i$ stets lösbar, weil die dem Gleichungssystem entsprechenden Vektoren stets linear unabhängig sind.
Additions- und Multiplikationstabelle für $\mathbb{F}_2 = \{0,1\}$, den endlichen Körper mit 2 Elementen.
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| × | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Sogar Chinchillas können über $\mathbb{F}_2$ rechnen.