Schachbrett weiß färben

Question

Es sei n ∈ 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.
Hinweis: Betrachten Sie den Vektorraum F_2^{nxn} und für k,l ∈ {1, …, n} speziell die Matrix D(k,l)=(d_(i,j)) ∈ 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 von i=1 bis n) D(i,l)+ (Summe von i=1 bis n) D(k,j) für k,l ∈ {1, …, n}.

Meine Ansätze: 

Die Matrix D(k,l) sieht dann aus wie ein Schachbrett mit 1 und 0 abwechseln. Man kann die einser-Felder gleich die weißen Felder setzen. Ich habe mir eine 5x5-Matrix aufeschrieben, damit ich die Aufgabe besser verstehe, aber ich müsste nur 2x drücke, damit das Brett komplett weiß wird. Jetzt frage ich mich, ob das Feld auf das man drückt auch die Farbe ändern muss, dann wäre es nämlich nicht nach 2x fertig und ob es vielleicht möglich ist, dass das Schachbrett gar nicht typisch gemustert ist, sondern die Felder willkürliche Farben annehmen können.

Ich freue mich über jede Hilfe ! :) 

Answer 1

> Die Matrix D(k,l) sieht dann aus wie ein Schachbrett mit 1 und 0 abwechseln.

Nein. Die Einträge dieser Matrix sind 1 genau bei den Feldern, die durch Drücken des Feldes in Zeile k, Spalte l die Farbe wechseln.

> (d_i,j) ∈ F_2^nxn

Angenommen ein Feld hat die Farbe n.

Ist n = 0, dann ist n + 1 = 1 in F₂ . Ist n = 1, dann ist n + 1 = 0 in F₂ . Krasser Sсheiß, man kann einfach durch Addition von 1 die Farbe wechseln. Jetzt wären Matrizen praktisch, die genau dort eine 1 haben, wo Felder durch Drücken eine Feldes die Farbe wechseln.

> M(k,l):= D(k,l)+(Summe von i=1 bis n) D(i,l)+ (Summe von i=1 bis n) D(k,j) für k,l ∈ {1, …, n}.

Berechne das mal angesichts der neuen Erkentnisse, die du über D(k,l) jetzt hast.

> Jetzt frage ich mich, ob das Feld auf das man drückt auch die Farbe ändern muss.

Zitat: "Drückt man auf ein Feld, so ändert sich die Farbe von jedem Feld, welches in derselben Zeile ...". Ist as Feld auf das gedrückt wird, in der selben Zeile wie das Feld auf das gedrückt wird?

Comments

Danke für deine Hilfe!!! :)

Also: ich habe mich nochmal drangesetzt:

Also die Matrix D(k,l) ist jetzt jede Matrix die an der Stelle a_i,j und in der Spalte a_i und der Zeile a_j nur Einsen stehen haben. Davon gibt es n^2 Möglichkeiten, da dies für jedes Feld vom Schachbrett gilt, und deshalb brauch es höchstens n^2-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 0 enthält. Wenn man 0 gleich weiß definiert ist also das ganze Schachbrett weiß.

Ist das alles richtig so?

---

> D(k,l) ist jetzt jede Matrix die an der Stelle a_i,j

Woher kommen das i und das j?

---

Dass i, j kann von {1,..,n} laufen und a_i,j kommt den Koeffizienten in der i-ten Spalte und j-ten Zeile an.

Mittlerweile ist mir aber aufgefallen, dass wenn man M(k,l) berechnet nicht die Nullmatrix rauskommt sondern eine Matrix voll mit 0 außer der Koeffizient a_k,l. Dieser ist dann 1.

Jetzt frage ich mich, wie ich stattdessen auf die Nullabbildung komme. Wenn ich M(1,1)+...+M(1,n)+...+M(n,n) addiere, bekomme ich eine Matrix voll mit Einsen. Ist das dann die Lösung? Da man n^2 Matrizen zusammen rechnet.

---

> wenn man M(k,l) berechnet nicht die Nullmatrix rauskommt sondern eine Matrix voll mit 0 außer der Koeffizient a_k,l. Dieser ist dann 1.

Durch Drücken aller in der Summe vorkommenden Felder hintereinander ändert also nur dieses eine Feld seine Farbe. Problem ist, dass du dann schon 2n+1 Felder gedrückt hast. Sind n Felder schwarz, dann müsstest du mit dieser Strategie n·(2n+1) = 2n² + n > n² Felder drücken.

Aber du hast zumindest schon mal eine Strategie, wie du überhaupt das gesamte Feld weiß färben kannst. Das muss nur noch optimiert werden. Tipp: es macht keinen Unterschied, ob du ein Feld zwei mal drückst oder überhaupt nicht, selbst dann wenn dazwischen andere Felder gedrückt wurden.