Beweis zur Bedeckung eines Schachbrettes

Question

ich verzweifle an folgender Aufgabe: Ich habe ein leeres Schachbrett (8x8 Felder) und 32 Dominosteine, die jeweils genau 2 Felder des Schachbrettes bedecken. Ich soll alle Felder des Schachbrettes mit den 32 Dominosteinen bedecken. Dazu lege ich 4 Dominosteine in jeder Zeile nebeneinander. So weit, so klar.

Jetzt wird mir ein Dominostein weggenommen, dafür wird jeweils eine Münze auf die linke obere und die rechte untere Ecke des Schachbretts gelegt. Die Frage ist, kann ich mit den 31 verbliebenen Dominosteinen alle restlichen 62 Felder des Schachbrettes bedecken?

Die Frage soll auch für ein beliebiges (n x n Felder) großes Schachbrett und n^2/2-1 Dominosteine beantwortet werden.

Habt ihr einen Tipp für mich?

Answer 1

Aloha :)

Wenn \(n\) ungerade ist, ist \(n^2-2\) ungerade, d.h. es muss eine ungerade Anzahl von Feldern abgedeckt werden. Da ein Dominostein immer über 2 Felder geht, kann man damit das Schachbrett nicht bedecken.

Wenn \(n\) gerade ist, haben die linke obere und die rechte untere Ecke dieselbe Farbe (beide weiß oder beide schwarz). Da jeder Dominostein über 2 Felder geht, muss er stets ein weißes und ein schwarzes Feld bedecken. Da es jedoch in unserer Situation von einer Farbe 2 Felder mehr gibt, kann man das Schachbrett nicht vollständig mit Dominosteinen bedecken.

Answer 2

Das ist eine sehr bekannte Aufgabe, die hier sehr schön anhand eines 8x8 Feldes erklärt wird.

https://www.mathe-online.at/galerie/spiel/schach/schach.html

Für n ungerade gibt es eine ungerade Anzahl an Feldern. Die kann man nicht mit Dominosteinen bedecken, weil immer ein Feld übrigbleibt.

Für n Gerade haben die diagonal gegenüberliegenden Felder die gleiche Farbe. Damit hat man keine Farbverteilung von 32 zu 32 sondern von 30 zu 32. Hier müssen durch bedeckung mit Dominosteinen also immer zwei gleiche Farben am Ende übrig bleiben auf die der letzte Dominostein eben nicht mehr passt.