Jana und Amira haben im Deutschunterricht Langeweile.
Amira erinnert sich an ein interessantes Rätsel, das ihr vor Kurzem begegnet ist. Kurzerhand zückt sie ein kariertes Blatt und zeichnet darauf den unten abgebildeten Umriss ein:
Ein 8×8-Quadrat, an dem an zwei (gegenüberliegenden) Ecken ein Kästchen fehlt. Daneben zeichnet Sie exemplarisch einen Dominostein ein, der zwei Kästchen bedeckt.
Amira möchte, dass Jana den vorgegebenen Umriss mit diesen Dominosteinen vollständig ausfüllt. Dabei dürfen sich die Dominosteine natürlich nicht überlappen oder über den Rand hinausragen.
Kann Jana den Umriss mit solchen Dominosteinen parkettieren? Falls ja, gib eine mögliche Parkettierung an. Falls nein, gib eine Begründung an, warum es nicht geht.
Achtung: Solltest du es nach einigen Versuchen nicht hinbekommen haben, ist das kein Beweis dafür, dass es unmöglich ist. Überlege dir immer, wie viel Geld du bereit wärst, auf deine Entscheidung zu setzen!
Lösungshinweis
Färbe die Kästchen wie bei einem Schachbrett.
Lösung
Tatsächlich ist es unmöglich, den gegebenen Umriss mit Dominosteinen zu parkettieren.
Doch wie kann man sich dieser Sache zu 100 % sicher sein? Wie in der Aufgabenstellung bereits angemahnt, reicht es nicht, einfach einige Male beim Versuch zu scheitern. (Allerdings wäre es hinreichend, alle möglichen Varianten zu untersuchen und auszuschließen. Diese Brute-Force-Methode ist allerdings weder praktikabel, noch sonderlich elegant.)
Wir fragen uns nun, unter welchen Umständen eine solche Parkettierung mit 2er-Dominosteinen auf jeden Fall unmöglich ist.
Der naheliegendste Fall wäre eine ungerade Anzahl an zu bedeckenden Feldern. Wir haben es hier jedoch mit einer geraden Anzahl, nämlich 62 Feldern, zu tun, sodass zumindest diese notwendige Bedingung erfüllt ist.
Wir brauchen also eine stärkere notwendige Bedingung, die unser Umriss nicht mehr erfüllen kann. An dieser Stelle kommt der Schachbrett-Tipp ins Spiel. Wir färben die Kästchen folgendermaßen ein:
Wir machen uns nun bewusst, dass ein Dominostein immer gleichzeitig genau ein weißes und genau ein schwarzes Kästchen bedeckt. Allerdings haben wir in unserem Umriss 32 schwarze, jedoch nur 30 weiße Felder, da die beiden weißen Ecken des Schachbrettes fehlen.
Eine Überdeckung mit Dominosteinen kann also niemals funktionieren. Wetten?
Schreibe einen Kommentar