Das Schachbrett mit Dominos so überdecken, dass kein 2x2-Quadrat entsteht
Selbstverständlich ist es möglich, die 64 Felder eines Schachbretts mit 32
Dominosteinen der Größe 1x2 zu überdecken. Aber kann man das so erledigen,
dass niemals zwei Dominosteine an ihren langen Seiten aneinanderliegen und ein
2x2-Quadrat bilden?
DIY-Tipp: Besorgen Sie sich 32 Dominosteine und zeichnen Sie und ein
Blatt Papier das dazugehörige 8x8-Quadrat. Die Färbung in abwechselnd weiße
und schwarze Felder ist nicht nötig. Wenn Sie systematisch vorgehen, helfen
auch schon die die 28 Dominosteine eines normalen Dominospiels.
Also probieren wir es einfach. Aber es klappt auch nach vielen Versuchen
nicht, und wir kommen auf die Idee, dass es sich um eine unmögliche Aufgabe
handeln könnte. Gab es nicht schon eine Aufgabe, das Schachbrett (mit einer
zusätzlichen Bedingung) mit Dominosteinen zu überdecken? Ja, das war die
Unlösbare Schachbrettaufgabe, bei der zunächst zwei gegenüberliegende Ecken des Schachbretts entfernt
wurden und dann die restlichen 62 Felder mit 31 Dominosteinen überdeckt werden
sollten. Dies stellte sich als unmöglich heraus und konnte mit Hilfe der
Färbung des Schachbretts bewiesen werden. Können wir hier ähnlich vorgehen, um
die Unmöglichkeit zu beweisen?
Die Antwort ist leider nein, aber es gibt eine andere relativ einfachen Beweis
der Unmöglichkeit. Es ist noch nicht einmal wichtig, dass es sich um ein
Schachbrett handelt. Die in den Lösungshinweisen enthaltene Begründung
funktioniert für alle Rechtecke. Eine der Seiten muss natürlich eine
geradzahlige Seitenlänge besitzen, sonst wird die Überdeckung sowieso niemals
funktionieren.
Lösungshinweis: Der Einfachheit halber kümmern wir uns nur um
den Fall quadratischer Rahmen. Wir müssen uns gar nicht um das ganze Quadrat
kümmern, sondern wir versuchen nur, die Felder entlang einer Diagonale so zu
überdecken, dass kein 2x2-Quadraht entsteht. Fangen Sie einfach in der Ecke
links oben mit einem waagerechten Dominostein an. Die Möglichkeit, mit
einem senkrechten Dominostein zu beginnen, ist durch Spiegelung des
Schachbretts an der Diagonale von links oben nach rechts unten gleich mit
erledigt.
Jetzt kommt der zweite Stein links oben in der zweiten Zeile. Der muss
senkrecht liegen, sonst haben wir hier bereits ein 2x2-Quadrat. Der nächste
Stein daneben (auf dem zweiten Feld der Hauptdiagonale) muss wieder
senkrecht liegen usw. Versuchen Sie, immer weiter Steine entlang der
Diagonale zu legen, ohne dass ein 2x2-Quadrat entsteht!
Falls Ihnen der Lösungshinweis nicht ausreicht, finden Sie mehr
Informationen in der unten angegebenen Quelle [1].
Wenn wir es schon nicht schaffen, alle 32 Dominosteine wie gewünscht
unterzubringen: Wieviele können wir denn unterbringen? Genauer
gefragt:
Frage: Wie viele Dominosteine kann man maximal auf ein 8x8-Schachbrett
legen, ohne ein 2x2-Quadrat zu bilden?
Wahrscheinlich schaffen Sie es mit
Hilfe der Konstruktion aus dem Unmöglichkeitsbeweis oben, n(n-1)/2
Dominosteine auf die geforderte Art in einen Rahmen der Größe nxn zu packen,
auch für ungerades n. Geht noch mehr? Bekommen wir den Rahmen wenigstens fast
voll? Diese Frage war das Problem Nr. 150 in der Zeitschrift Chessics: The Journal of Generalised Chess (Volume 2, Nr. 23, 1985), siehe [2].
