+2 Daumen
151 Aufrufe

Aufgabe:

Es sei n ∈ N gerade. Auf einem n × n Schachbrett ist jedes der n2 Felder entweder
schwarz oder weiß. Drückt man auf ein Feld, so ändert sich die Farbe von jedem Feld,
welches in derselben Zeile oder in derselben Spalte ist in schwarz, falls das betreffen-
de Feld weiß war, bzw. in weiß, falls das betreffende Feld schwarz war. Zeigen Sie,
dass man von jeder Ausgangssituation mit höchstens n2-maligem Drücken geeigneter
Felder das gesamte Schachbrett weiß färben kann.


Problem/Ansatz:

Ich Knobel schon seit einigen Tagen an dieser Aufgabe. Leider komme ich so gar nicht weiter und habe nichtmal einen Ansatz - habt ihr eine Idee?

von

Wie soll das gehen?

Falls sich das Feld auf das man drückt nicht verändert: Betrachte n=2

W W

W S

Egal wo man drückt, es werden immer zwei Felder verändert. Die Zahl der Schwarzen verändert sich um -2, 0 oder +2

Da wir mit 1 Schwarze Fläche starten werden durch Addition von Geraden Zahlen niemals 0 rauskommen.

Falls sich das gedrückte Feld verändert: gleiches Argument für n=2

W W

S S

Diesmal ändern sich genau 3 Felder. Die Anzahl der schwarzen Felder kann sich dann nur um

-3, -1, +1 oder +3 ändern

Mit Addition von ungeraden Zahlen auf 2 kommt man allerdings niemals auf 0.

Fehlt vielleicht eine Angabe?

@MatHaeMatician Ich denke die Aufgabenstellung ist falsch formuliert, es ist wahrscheinlich gemeint, dass unter der Prämisse, eine gegebene Anfangskonfiguration seie lösbar, man diese innerhalb von \(n^2\) Zügen lösen kann.

Diese Frage wurde hier in der gleichen Formulierung bereits vor 5 Jahren gestellt:

https://www.mathelounge.de/455782/schachbrett-weiss-farben

1 Antwort

0 Daumen
 
Beste Antwort

Übersetze das Problem erstmal in eines, welches Matrizen verwendet: Sei "weiss" kodiert durch 0 und "schwarz" kodiert durch 1. Wir arbeiten also über dem Körper \( \mathbb{F}_{2} \). Möchtest du nun z.B. den Knopf \( (1,2) \) drücken (wir betrachten den Fall \( n=3 \) ), so entrspricht dies der Addition der Anfangsmatrix zu

\( \left[\begin{array}{lll} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{array}\right] \)

und im Allgemeinen gilt, möchtest du den Knopf an der Position ( \( l, s) \) drücken, dass wir die jeweilige Matrix mit \( \boldsymbol{A}_{(l, s)} \) summieren, wobei

\( \left(\boldsymbol{A}_{(l, s)}\right)_{i, j}=\left\{\begin{array}{ll} 1, & i=l \text { oder } j=s \\ 0, & \text { sonst } \end{array} .\right. \)

Des Weiteren gilt \( \boldsymbol{A}_{(l, s)}+\boldsymbol{A}_{(l, s)}=0 \), was zusammen mit der Kommutativität der Matrixaddition dazu führt, dass wir jede der Matrizen \( \boldsymbol{A}_{(1, s)} \) für \( 1 \leqslant l, s \leqslant n \) nur maximal einmal zu unserer Anfangsmatrix hinzuaddieren können/müssen, da ein zweites Mal nichts an der Anfangsmatrix verändern würde und wir es daher garnicht erst machen müssten. Wir addieren also maximal \( \mathrm{n}^{2} \) Matrizen, was im ursprünglichen Kontext bedeutet, dass wir maximal \( n^{2} \) Mal einen Knopf drücken (die Prämisse ist hierbei jedoch, dass das Spiel tatsächlich lösbar ist). Für die Lösbarkeit kann man das Problem als ein LGS formulieren, das werde ich nach Bedarf gerne weiter ausführen.

von 3,7 k

Hey, prima, danke dir! :)

Ich tue mich sehr schwer damit, das Problem in Matrizen zu erfassen - kommt mir sehr abstrakt vor ..

Wie hast du denn dein LGS aufgestellt?

Lieben Gruß!

Das LGS knüpft an das obige an, also würde ich zuerst versuchen, dieses zu verstehen. Es ist eigentlich überhaupt nicht abstrakt, da ein Schachbrett ja quasi wie eine Matrix aussieht, oder?

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community