Möglichst wenige Züge bei Spiel herausfinden

03.08.2014, 12:14	thorray	Auf diesen Beitrag antworten »
Möglichst wenige Züge bei Spiel herausfinden Meine Frage: Moin an alle, Erstmal: ich bin neu hier im Forum und kein Mathestudent, und hoffe, das richtige Thema gewählt zu haben... Es geht um ein einfaches Spiel, in dem man ein Spielfeld hat wie in Bild 1 zu sehen. Eine Zelle kann nur 0,1, oder 2 annehmen. In jedem Zug kann man eine Zelle auswählen: es erhöht sich dann der Betrag dieser Zelle und der der Nachbarzellen um +1 (eine 2 würde zu einer 0 werden, der Betrag einer Zelle ist also immer xi modulo 3). Beispiel: Wählt man Zelle x(1,2), also oben in der Mitte, dann wäre das Spielfeld wie in Bild 2. Das Ziel ist es, mit möglichst wenig Zügen das Spielfeld homogen zu bekommen, d.h. alle Zellen enthalten eine 0, oder alle eine 1, oder alle eine 2. Ich überlege jetzt, ob man nicht-iterativ beweisen kann, wie viele Züge es gibt, oder sogar welche Zellen (oder Differenzen zw. Zellen) man angehen muss... Ist das möglich? Würde mich interessieren, wie und ob man sowas angehen kann! Danke schonmal! Meine Ideen: Mein Ansatz war erstmal den Ausgangszustand und Endzustand aufzuzeichnen, und dann die Differenz zwischen den Zellen. Auch habe ich versucht die Assoziationen zwischen den Zellen aufzuzeichnen (z.B. x11 verändert sich, wenn man sich in einem Zug für x12 oder x21 entscheidet). Oder auch: Die Differenz x11 und x12 verändert sich, wenn man x13,x21, oder x22 wählt. Aber ich bekomme die Ideen nicht unter einen Hut.
03.08.2014, 20:35	Leopold	Auf diesen Beitrag antworten »
Man betrachtet den Vektorraum $\begin{align} V \end{align}$ der 2×3-Matrizen über $\begin{align} K = \{ -1,0,1 \} \end{align}$ , dem Körper mit 3 Elementen. Es sei $\begin{align} E_{ij} \end{align}$ die Matrix mit $\begin{align} 1 \end{align}$ an der Position $\begin{align} (i,j) \end{align}$ und Nullen sonst. Dann bilden die Matrizen $\begin{align} E_{11},E_{12},E_{13},E_{21},E_{22},E_{23} \end{align}$ eine geordnete Basis von $\begin{align} V \end{align}$ . Jede Matrix $\begin{align} S \in V \end{align}$ läßt sich in eindeutiger Weise als Linearkombination bezüglich dieser Basis darstellen: $\begin{align} S = s_{11} E_{11} + s_{12} E_{12} + s_{13} E_{13} + s_{21} E_{21} + s_{22} E_{22} + s_{23} E_{23} \end{align}$ Die Koeffizienten $\begin{align} s_{ij} \in K \end{align}$ werden zu einem Spaltenvektor $\begin{align} s \end{align}$ angeordnet. Er gibt den Zustand des Spielfeldes an. Jeder Matrix $\begin{align} E_{ij} \end{align}$ entspricht dabei umkehrbar eindeutig ein Einheitsvektor $\begin{align} e_{ij} \end{align}$ als Zustandsvektor. Das erste Spielfeld in deinem Beispiel würde mit $\begin{align} S = E_{11} - E_{12} + E_{21} \end{align}$ angegeben und hätte damit $\begin{align} s = e_{11} - e_{12} + e_{21} \end{align}$ als Zustandsvektor. Wir gehen jetzt von einer Matrix $\begin{align} S \end{align}$ mit dem Zustandsvektor $\begin{align} s \end{align}$ aus. Wenn man für den nächsten Zug die Zelle $\begin{align} (1,1) \end{align}$ wählt, so geht $\begin{align} S \end{align}$ in $\begin{align} S' \end{align}$ und $\begin{align} s \end{align}$ in $\begin{align} s' \end{align}$ über mit $\begin{align} S' = S + E_{11} + E_{12} + E_{21} \, , \ \ s' = s + e_{11} + e_{12} + e_{21} \end{align}$ Wir fassen das, was zu $\begin{align} s \end{align}$ addiert wird, als Bildvektor von $\begin{align} e_{11} \end{align}$ auf: $\begin{align} e_{11} \mapsto e_{11} + e_{12} + e_{21} \end{align}$ Wenn man dagegen die Zelle $\begin{align} (1,2) \end{align}$ wählt, gilt $\begin{align} S' = S + E_{11} + E_{12} + E_{13} + E_{22} \, , \ \ s' = s + e_{11} + e_{12} + e_{13} + e_{22} \end{align}$ Wir fassen das, was zu $\begin{align} s \end{align}$ addiert wird, jetzt als Bildvektor von $\begin{align} e_{12} \end{align}$ auf: $\begin{align} e_{12} \mapsto e_{12} + e_{11} + e_{13} + e_{22} \end{align}$ Und so kann man das für jede Zellenwahl machen und bekommt insgesamt eine lineare Abbildung $\begin{align} K^6 \to K^6 \end{align}$ , beschrieben durch eine Matrix $\begin{align} T \end{align}$ . Wählt man für den nächsten Zug die Zelle $\begin{align} (i,j) \end{align}$ aus, so geht $\begin{align} s \end{align}$ in $\begin{align} s' \end{align}$ über: $\begin{align} s' = s + T \cdot e_{ij} \ \ \ \text{mit} \ \ \ T = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{align}$ Macht man mehrere Züge nacheinander, so werden diese in einem Vektor $\begin{align} x \end{align}$ gespeichert: $\begin{align} s' = s + T \cdot e_{ij} + T \cdot e_{kl} + \ldots = s + T \cdot \underbrace{\left( e_{ij} + e_{kl} + \ldots \right)}_{x} \end{align}$ Offenbar kommt es auf die Reihenfolge nicht an, in der man die Zellen wählt. Wird eine Zelle modulo 3 einmal gewählt, steht in $\begin{align} x \end{align}$ an der entsprechenden Position $\begin{align} 1 \end{align}$ , wird sie modulo 3 zweimal gewählt, steht $\begin{align} -1 \end{align}$ , und wird sie modulo 3 keinmal gewählt, steht $\begin{align} 0 \end{align}$ . Geht man also vom Ausgangszustand $\begin{align} s \end{align}$ aus und will man den Zustand $\begin{align} s' \end{align}$ erreichen, so muß man das lineare Gleichungssystem $\begin{align} s + T \cdot x = s' \end{align}$ lösen. Die Matrix $\begin{align} T \end{align}$ ist nicht invertierbar. Wenn man den Gaußschen Algorithmus ausführt, erkennt man unterwegs, daß das Gleichungssystem dann und nur dann lösbar ist, wenn $\begin{align} \left( s_{11} + s_{23} \right) - \left( s_{21} + s_{13} \right) = \left( s'_{11} + s'_{23} \right) - \left( s'_{21} + s'_{13} \right) \end{align}$ gilt. Die Lösungsmenge ist dann eindimensional.
03.08.2014, 23:19	thorray	Auf diesen Beitrag antworten »
Genial, vielen Dank für die ausführliche Antwort!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »