Schachbrett durch "drücken" weiß färben

21.06.2017, 23:20

Mathlete1

Schachbrett durch "drücken" weiß färben

Meine Frage:
Es sei n Element N gerade. Auf einem nxn Schachbrett ist jedes der n^2 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 betreffende Feld weiß war, bzw. in weiß, falls das betreffende Feld schwarz war. Zeigen Sie, dass man von jeder Ausgangssituation mit höchstens n^2-maligen Drücken geeigneter Felder das gesamte Schachbrett weiß färben kann.
Hinweiß: Betrachten Sie den Vektorraum F_2^(nxn) und für k,l Element {1, ..., n} speziell die Matrix D(k,l)=(d_(i,j)) Element F_2^(nxn) mit Einträgen
d_(i,j) = {1 falls i=k oder l=j, 0 sonst .
Was hat D(k,l) mit der Aufgabe zu tun? Berechnen Sie nun M(k,l):= D(k,l)+Summe D(i,l) +Summe D(k,j) für k,l Element {1, ..., n}. (Die Summen sind für i=1 und j=1 bis n)

Meine Ideen:
Also die Matrix D(k,l) ist jede Matrix die an der Stelle a_i,j und in der Spalte a_i und der Zeile a_j nur Einsen stehen hat. Davon gibt es n2 Möglichkeiten, da dies für jedes Feld vom Schachbrett möglich ist, und deshalb brauch es höchstens n2-maliges Drücken.

Wenn man M(k,l) berechnet mit D(k, l) wie oben und für die Summe von D(i,l) gilt dass die i-te Spalte nur Einsen enthält und bei D(k,j) ist die j-te Zeile voll mit Einsen. Wenn man diese drei addiert bekommt man eine Matrix die nur Nullen enthält, außer an der Stelle a_(k,l), wo eine Eins steht. Die Matrix M(k,l) gibt also die Änderung eines Feldes an.
Nun kann ich mit M(k,l) jede Änderung auf meinem Schachbrett aufspannen und ist deshalb die Basis mit Mächtigkeit n^2 mit der man jedes beliebiges "Schachbrett" mit höchstens n^2-maligem "drücken" als eine Nullmatrix schreiben kann und deshalb komplett weiß ist.

Ist das alles richtig so? Und wenn ja, hätte ich nur eine Frage: Wieso ist n als gerade definiert/muss n gerade sein?

Ich bin für jede Hilfe dankbar!

22.06.2017, 16:15

Mathlete1

Auf diesen Beitrag antworten »

RE: Schachbrett durch "drücken" weiß färben
Hat niemand eine Idee oder kann helfen? verwirrt

22.06.2017, 19:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mathlete1
Davon gibt es n2 Möglichkeiten, da dies für jedes Feld vom Schachbrett möglich ist, und deshalb brauch es höchstens n2-maliges Drücken.

Wie du zu diesem Zeitpunkt bereits diese Schlussfolgerung ziehen kannst, musst du mal begründen. Eigentlich steht diese Erkenntnis erst nach den nächsten Überlegungen - sonst könnte man ja hier bereits abbrechen. Augenzwinkern

Was man allenfalls sagen kann, und zwar wegen des Grundraums $\begin{align*} \mathbb{F}_2 \end{align*}$ mit nur den Elementen 0 und 1: Wenn es überhaupt klappt, dann mit maximal $\begin{align*} n^2 \end{align*}$ -maligem Drücken. Aber dass es auch tatsächlich klappt, ist noch nicht gezeigt.

Zitat:

Original von Mathlete1
Wenn man M(k,l) berechnet mit D(k, l) wie oben und für die Summe von D(i,l) gilt dass die i-te Spalte nur Einsen enthält und bei D(k,j) ist die j-te Zeile voll mit Einsen. Wenn man diese drei addiert bekommt man eine Matrix die nur Nullen enthält, außer an der Stelle a_(k,l), wo eine Eins steht. Die Matrix M(k,l) gibt also die Änderung eines Feldes an.

Korrektes Endergebnis, auch wenn mir deine Begründung ziemlich unzureichend vorkommt: Schließlich sollte man für alle $\begin{align*} n^2 \end{align*}$ Felder diskutieren, wie die hier vorliegenden $\begin{align*} (2n+1) \end{align*}$ D-Operationen wirken, da gibt es durchaus Unterschiede, wie die ganzen Nullen zustandekommen (ob in der gleichen Zeile/Spalte wie (k,l) oder nicht...). Und auch die Tatsache, dass $\begin{align*} n \end{align*}$ gerade ist, wird hier benötigt!!!

Zitat:

Original von Mathlete1
Nun kann ich mit M(k,l) jede Änderung auf meinem Schachbrett aufspannen und ist deshalb die Basis mit Mächtigkeit n^2 mit der man jedes beliebiges "Schachbrett" mit höchstens n^2-maligem "drücken" als eine Nullmatrix schreiben kann und deshalb komplett weiß ist.

Jetzt ist man soweit, dieses Fazit zu ziehen.

22.06.2017, 20:12

Mathlete1

Auf diesen Beitrag antworten »

Danke erstmal für die Antwort! smile

Beim ersten Zitat ist mir auch aufgefallen, dass das irgendwie nicht stimmen kann.

Ich weiß nicht genau, wie du das meinst mit den (2n+1) D Operationen. Da kommt man jetzt drauf, weil es zwei Summen von 1 bis n für D gibt und eine einzelne D Matrix, oder wie muss ich das verstehen? Haben jetzt diese (2n+1) D Operationen was damit zu tun, dass n gerade sein muss? Da (2n+1) ja die Darstellung einer ungeraden Zahl ist..

22.06.2017, 20:14

HAL 9000

Auf diesen Beitrag antworten »

Bei manchen muss man alles erst paarmal wiederholen, bis es wirkt. Na dann:

Zitat:

Original von HAL 9000
Schließlich sollte man für alle $\begin{align*} n^2 \end{align*}$ Felder diskutieren, wie die hier vorliegenden $\begin{align*} (2n+1) \end{align*}$ D-Operationen wirken, da gibt es durchaus Unterschiede, wie die ganzen Nullen zustandekommen (ob in der gleichen Zeile/Spalte wie (k,l) oder nicht...). Und auch die Tatsache, dass $\begin{align*} n \end{align*}$ gerade ist, wird hier benötigt!!!

Führe es z.B. mal für n=4 aber dann auch mal n=3 komplett durch - um zu sehen, dass es bei letzterem nicht klappt.

22.06.2017, 20:41

Mathlete1

Auf diesen Beitrag antworten »

Ich habe es jetzt mit n=4 und n=3 ausprobiert, finde aber leider keinen Unterschied oder eine Stelle an der es hakt

22.06.2017, 20:57

HAL 9000

Auf diesen Beitrag antworten »

Dann hast du D(k,l) nicht verstanden. Im Fall n=3 bewirkt etwa M(1,1) auf die Nullmatrix angewandt die Matrix

1 1 1
1 0 0
1 0 0

also identisch mit D(1,1) statt der angestrebten Matrix

1 0 0
0 0 0
0 0 0

Also bitte nochmal nachdenken, und diesmal genauer.

22.06.2017, 21:25

Mathlete1

Auf diesen Beitrag antworten »

Ich komme nicht drauf..
Soll D(i,1) = 1 0 0 und D(j,1)= 1 0 0
0 0 0 0 0 0
0 0 0. 0 0 0 sein für n=3?
Weil für n=4 wäre es dann ja wieder die ganze Spalte und Zeile voller Einsen. Deshalb verstehe ich nicht wieso D(i,1),D(1,j) sich ändern sollen, man nimmt doch jedes Mal die Summe von 1 bis n.

22.06.2017, 21:29

HAL 9000

Auf diesen Beitrag antworten »

Also ehrlich, dass du nicht mal die Basisoperation

Zitat:

Original von Mathlete1
Matrix D(k,l)=(d_(i,j)) Element F_2^(nxn) mit Einträgen
d_(i,j) = {1 falls i=k oder l=j, 0 sonst .

hier aufschreiben kannst... unglücklich

D(1,1)
1 1 1
1 0 0
1 0 0

D(2,3)
0 0 1
1 1 1
0 0 1

usw.

22.06.2017, 21:34

Mathlete1

Auf diesen Beitrag antworten »

Ja das D(k,l) so aussieht habe ich verstanden, aber was bringt es mir jetzt die verschiedenen Möglichkeiten aufzuschreiben? Das habe ich doch schon gemacht. Aber wie säh denn dann D(i,1) und D(1,j) für n=3 aus.
Die beiden können dann doch keine Spalte bzw. Zeile voller Einsen mehr sein, da M(1,1) sonst ja ungleich D(1,1) für n=3 wäre.

22.06.2017, 21:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mathlete1
Das habe ich doch schon gemacht.

Es ist aber nicht zu erkennen, dass du sie richtig addierst, da du immer steif und fest behauptest, was anderes rauszubekommen - irgendwie niederschmetternd. Forum Kloppe

Also was passiert bei Spaltensumme $\begin{eqnarray*} \sum_{i=1}^n D(i,l) \end{eqnarray*}$ :

Alle Elemente der Matrix außer denen in Spalte $\begin{eqnarray*} l \end{eqnarray*}$ werden je genau einmal invertiert. Alle Elemente in Spalte $\begin{eqnarray*} l \end{eqnarray*}$ hingegen werden genau $\begin{eqnarray*} n \end{eqnarray*}$ -mal invertiert. Was bedeutet, dass es hier sehr wohl eine Rolle spielt, ob $\begin{eqnarray*} n \end{eqnarray*}$ gerade ist oder ungerade.

Analog jetzt bei der Zeilensumme $\begin{eqnarray*} \sum_{j=1}^n D(k,j) \end{eqnarray*}$ :

Alle Elemente der Matrix außer denen in Zeile $\begin{eqnarray*} k \end{eqnarray*}$ werden je genau einmal invertiert. Alle Elemente in Zeile $\begin{eqnarray*} k \end{eqnarray*}$ hingegen werden genau $\begin{eqnarray*} n \end{eqnarray*}$ -mal invertiert.

Beides kombiniert zu $\begin{eqnarray*} \sum_{i=1}^n D(i,l)+\sum_{j=1}^n D(k,j) \end{eqnarray*}$ ergibt sich für gerade $\begin{eqnarray*} n \end{eqnarray*}$ :

In Zeile $\begin{eqnarray*} k \end{eqnarray*}$ sowie Spalte $\begin{eqnarray*} l \end{eqnarray*}$ außer am Kreuzungspunkt $\begin{eqnarray*} (k,l) \end{eqnarray*}$ stehen Einsen, sonst im Rest der Matrix Nullen. Das abschließende $\begin{eqnarray*} D(k,l) \end{eqnarray*}$ bringt dann das gewünschte Ergebnis.

Für ungerades $\begin{eqnarray*} n \end{eqnarray*}$ ist hingegen $\begin{eqnarray*} \sum_{i=1}^n D(i,l)+\sum_{j=1}^n D(k,j) = 0 \end{eqnarray*}$ , d.h., die Nullmatrix - sozusagen $\begin{eqnarray*} 2n \end{eqnarray*}$ sinnlose Operationen. Augenzwinkern

22.06.2017, 21:51

Mathlete1

Auf diesen Beitrag antworten »

Danke.
Wie gesagt: Ich habe verstanden was bei D(k,l) rauskommt, nur die Summen habe ich wohl falsch verstanden und wusste nicht bzw. Bin nicht drauf gekommen, dass sie n-mal invertiert werden.
Ich danke dir für deine Geduld, bin halt leider ein Anfänger.

22.06.2017, 22:01

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mathlete1
Bin nicht drauf gekommen, dass sie n-mal invertiert werden.

Es ist eine einfache sture Umsetzung der Definition von D(i,l), kein übermenschlicher Geistesblitz ist dazu nötig. Wenigstens beim konkreten n=3 hättest du mal die 7 Operationen unfallfrei ausführen können müssen. unglücklich

22.06.2017, 22:32

Mathlete1

Auf diesen Beitrag antworten »

Wenn ich die Summen schon nicht verstanden habe, wie hätte ich es dann unfallfrei ausführen sollen?

Neue Frage »

Antworten »

Schachbrett durch "drücken" weiß färben

Verwandte Themen