An Aus Spiel

22/01/2010 - 15:39 von Stephan Rosebrock | Report spam
Meine Frage ist hauptsàchlich: Gibt es das alles schon, was ich mir da überlegt habe und wo muss ich im Internet danach suchen?


Einführung

Gegeben ein $n\times k$-Gitter ($n,k\in\mathbb N$). Auf jedem Gitterpunkt sitzt
ein Làmpchen, das zwei Zustànde annehmen kann,
entweder ''an'' (Wert 1) oder ''aus'' (Wert 0). Am Anfang sind alle
Làmpchen aus. Auf jedes Làmpchen làsst sich klicken.
Ein Klick auf ein Feld (ein Làmpchen) àndert den Zustand des Feldes und all
seiner Nachbarfelder, also Felder, bei denen entweder die eine oder die andere
Koordinate um 1 abweicht, aber nicht beide. An dieser Stelle sind auch andere
Regeln denkbar, die Theorie im folgenden greift für beliebige Anschaltregeln.

Frage: Kann man durch endlich viele Klicks alle Làmpchen einschalten?

Leicht geht das im Fall $n=k=4$ mit nur 4 elementaren Klicks. Für größere
$n,k$ sieht man jedoch ganz elementar nichts mehr.

Das Spiel ist im Internet zu spielen (siehe Nr. 3 und Nr. 50 von
http://home.fonline.de/fo0126/spiele/index.htm)


Der gruppentheoretische Ansatz

Wir definieren eine Gruppe $G$: Ein $g\in G$ ist definiert durch die Angabe eines
Zustands (0 oder 1) für jedes der $n\cdot k$ Felder. Für $g,h\in G$ ist $g\cdot h$
definiert durch Addition in $\mathbb Z_2$ für jedes einzelne Feld.
Das neutrale Element ist das, bei dem jedes Feld 0 ist. Jedes Element ist
zu sich selbst invers. $G$ ist kommutativ. Es kommt bei den Klicks nur darauf
an, ob gerade oder ungerade oft geklickt wurde. Es gilt damit natürlich $G=\mathbb Z_2^{kn}$.

Seien die Elemente $g_1,\ldots ,g_{nk}\in G$ wie folgt definiert: $g_i$
entspricht dem Element das ich bekomme, wenn ich auf das $i$-te Feld klicke
vom Startzustand aus. Dabei sind die Felder zeilenweise durchnummeriert.

Man muss sich noch klar machen: Die Verknüpfung in $G$ entspricht dem
hintereinander ausführen der entsprechenden Klicks. $g_i\cdot g_j$ ist der
Zustand, den man erhàlt, wenn man erst auf das $i$-te und dann auf das $j$-te
Feld klickt (für alle $i,j$). Es gilt:

THEOREM: Sei $H=<g_1,\ldots ,g_{nk}>$ die von allen $g_i$ erzeugte Untergruppe in $G$. Ist $H=G$, dann lassen sich alle Làmpchen einschalten.

Im Fall $H=G$ làsst sich nàmlich jede mögliche Konfiguration mit den
$g_i$, also mit elementaren Klicks, erhalten, auch die, bei der alle
Làmpchen eingeschaltet sind.


Der Ansatz mit linearer Algebra

Da es nur um die Anzahl der Klicks Modulo 2 geht, rechnen wir viel einfacher
in einem Vektorraum mit Koeffizienten aus dem Körper $\mathbb Z_2$. Wir
fassen die $g_i$ als Vektoren in einem $nk$-dimensionalen Vektorraum auf und
fragen uns also, ob eine Linearkombination der $g_i$ existiert, die
$(1,1,1,\ldots ,1)$ ergibt. Ein Zustand ist also ein Vektor der Lànge $nk$
aus 0 und 1 (über $\mathbb Z_2$).
Erzeugt jede Linearkombination aus den $g_i$ einen anderen
Zustand, dann folgt $G=H$, weil es ebenso viele Zustànde gibt, wie
Elemente in $G$ nàmlich $2^{nk}$.

Wir prüfen das und
nehmen dazu an, 2 verschiedene Linearkombinationen erzeugen den selben Zustand, also

(1) \sum \lambda_ig_i=\sum\delta_ig_i

wobei die $\lambda_i$ und die $\delta_i$ nicht alle gleich sind. Gleichung
(1) ist aber àquivalent zu

\sum (\lambda_i+\delta_i)g_i=0.

Wir rechnen nàmlich über $\mathbb Z_2$. Die Frage ist also, ob es eine
Linearkombination der $g_i$ gibt, die 0 ist, aber nicht alle
Koeffizienten sind 0, also ob die $g_i$ linear abhàngig sind.
Wir haben also bewiesen:

LEMMA Die Vektoren $g_1,\ldots ,g_{kn}$ sind genau dann linear unabhàngig
in einem Vektorraum über $\mathbb Z_2$, wenn $G=H$ gilt.


Möglich ist auch, jeden Zustand als Matrix aufzufassen. Jedes $g_i$ ist eine
$n\times k$-Matrix über $\mathbb Z_2$ und die Verknüpfung $g_i\cdot g_j$ in der Gruppe $G$
entspricht einfach der Addition der entsprechenden Matrizen über $\mathbb Z_2$.


Der Fall $n=k=5$

Nach Mathematica sind im Fall $n=k=5$ die $g_i$ linear abhàngig und damit ist
$Ge H$. Z.B. gilt:

g_1+g_2+g_4+g_5+g_{11}+g_{12}+g_{14}+g_{15}+g_{21}+g_{22}+g_{24}+g_{25}=0

Sei $v=(1,1,1,\ldots ,1)$.
Eine Lösung der Frage aus Abschnitt 1 erhàlt man, indem man das Gleichungssystem
$\sum a_ig_i=v$ mit Unbekannten $a_i\in \mathbb Z_2$ löst. Mathematica gibt
einem mehrere Lösungen. Eine ist z.B.:

g_1+g_3+g_4+g_7+g_8+g_9+g_{11}+g_{12}+g_{13}+g_{16}+g_{17}+g_{19}+g_{20}+g_{24}+g_{25}=v


Und jetzt?

Interessant wàre jetzt allgemeiner zu verstehen, für welche Werte von $n,k$
ist $G=H$ und für welche Werte làsst sich $(1,1,1,\ldots ,1)$ erhalten?
Die unter Abschnitt 1 genannte website behauptet, dass $n\times n$ Felder
für $3\le n\le 8$ lösbar sind. Natürlich geht auch der Fall $n=2$ indem man
auf jeden Punkt klickt.

url:http://www.ureader.de/gp/1456-1.aspx
 

Lesen sie die antworten

#1 Thomas Plehn
22/01/2010 - 20:08 | Warnen spam
"Stephan Rosebrock" schrieb im Newsbeitrag
news:


THEOREM: Sei $H=<g_1,\ldots ,g_{nk}>$ die von allen $g_i$ erzeugte
Untergruppe in $G$. Ist $H=G$, dann lassen sich >alle Làmpchen einschalten.

Im Fall $H=G$ làsst sich nàmlich jede mögliche Konfiguration mit den
$g_i$, also mit elementaren Klicks, erhalten, auch die, bei der alle
Làmpchen eingeschaltet sind.



Interessante Formalisierung des Problems. Die Frage ist: Làsst sich die
Voraussetzung H=G irgendwie gruppentheoretisch entscheiden?

Ähnliche fragen