Pflasterung eines 8 x 8 Schachbrettes?
Man soll ein 8x8 Schachbrett durch 2x1 Dominosteine decken/pflastern. Jetzt sollen wir beweisen, dass a) die Gesamtzahl aller Pflasterungen gerade ist b) jede Pflasterung ein 2x2 Quadrat aus zwei Dominosteinen enthält.
ich könnte zu jedem einfach ein Beispiel malen aber beweisen ist das ja nicht Kann das jemand richtig mathematisch beweisen? Danke schonmal :)
3 Antworten
Nummerieren wir die Spalten mit A - H und die Zeilen mit 1- 8, wie beim Schachbrett.
Dann würde ich einen graphischen Beweis fahren.
Zeichne ein Feld 8x8, zeichne einen Stein links oben in die Ecke ein, wie er liegt ist egal, das Problem ist hier symmetrisch.
Sagen wir er liegt A1-A2. Dann zeichne immer einen weiteren Stein so ein, von dem du weißt, dass er nur so liegen kann, um nicht ein 2x2 Quadrat mit 2 Steinen entstehen zu lassen.
B1-B2 darf nicht liegen, weil wir sonst mit AB12 ein solches Quadrat hätten. Also muss B1-C1 liegen.
Solche Steine, die liegen müssen, kannst du immer weiter zeichnen, in deinem Beweis schreibst du dann, dass die einzelnen Steine zwingend so liegen müssen, sonst würde es das Quadrat geben.
Dann kommst du zu dem Punkt, bei DE45, wo du nicht mehr aus kannst und ein Quadrat zeichnen musst, willst du weitere Steine legen.
Da alle anderen Steine zwingend so liegen mussten, damit kein Quadrat entsteht, folgt hier daraus, dass es immer ein solches Quadrat geben muss.
Du tust so als würdest du versuchen ein Bild zu malen, welches kein solches Quadrat beinhaltet.
Links oben muss ein Stein liegen, wie ist hier egal. Danach kannst du immer einen weiteren Stein legen, bei dem du gezwungen bist, ihn so zu legen, bis es eben nicht mehr geht.
Damit hast du einen Beweis geführt, dass es nicht möglich ist, weil du ja unterwegs nichts anders machen konntest als du es getan hast. Wenn du das so erklärst, steht der Beweis.
----
Das mit der geraden Gesamtzahl kannst du leicht über die Symmetrie beweisen.
Zu jeder Pflasterung die A1-A2 beinhaltet gibt es auch eine um 90° gedrehte Variante, die A1-B1 beinhaltet.
Jede Variante ohne Drehung ist von jeder Variante mit Drehung verschieden.
Also ist die Gesamtzahl an Varianten gerade.
---
In welchem Rahmen wurde diese Aufgabe gestellt ?
@samudee: Ich verstehe AnglerAut so: Für Teil b) ist die Belegung - bis auf Symmetrie - eindeutig, sofern Du in einer Ecke beginnst. Das Ganze sieht dann aus wie ein Fischgräten-Muster, das zwar oben und links bündig abschließt, aber rechts und unten keinen geraden Rand mehr erlaubt — egal, wie groß das Schachbrett sein mag.
Grundsätzlich pflichte ich dem bei, aber ich halte es für sehr schwierig, dies nicht nur anschaulich, sondern mathematisch exakt zu zeigen...
Aber ich unterstreiche seine letzte Frage: Diese Aufgabe ist ziemlich anspruchsvoll. Sei mal ehrlich: Ist sie Teil eines Wettbewerbs? Das wäre ziemlich schäbig von Dir :-(
Der Beweis ist nicht schwierig, man kommt sehr schnell an die Stelle, an der man das Quadrat legen muss, dafür ist nicht einmal eine fallunterscheidung notwendig. Zumal es hier ja nur um 8x8 geht und nicht um den allgemeinen Beweis für jedes Quadrat mit gerader Seitenzahl.
Bei a ist es natürlich eine Spiegelung, keine Drehung, das hatte ich falsch geschrieben.
wenn man die steine waagerecht und senkrecht 'abwechselnd' legt brauche ich kein quadrat?
Du musst ja die Ränder ausfüllen, daher klappt dein Plan nicht. Zeichne es dir auf. Sobald du einen Stein in die Ecke gelegt hast musst du zwingend alle anderen der Reihe nach in einer bestimmten Ordnung legen und dann kommst du zu dem Punkt, wo es nicht mehr geht.
Diese Aufgabe wurde in der diesjährigen Matheolympiade gestellt
Hey, bei euren Lösungen habt ihr leider nicht bedacht, dass eine Pflasterung nicht heißt, dass keine 4x4 Felder entstehen dürfen, sondern nur, dass jedes Feld des Schachbrettes mit einem Domino-Stein bedeckt sein muss.
MfG Challenger =)
In der gesamten Lösung kommt kein 4x4 Feld vor. In der a) geht es nur über die Pflasterung, in der b) um 2 Steine, die ein 2x2 Feld ergeben. Hast du den selben Text gelesen wie ich ?
Hey, bei euren Lösungen habt ihr leider nicht bedacht, dass eine Pflasterung nicht heißt, dass keine 4x4 Felder entstehen dürfen, sondern nur, dass jedes Feld des Schachbrettes mit einem Domino-Stein bedeckt sein muss.
MfG Challenger =)
Was sind „2x1 Dominosteine”?
Ein normaler Dominostein besteht schon aus einem 2x1-Feld, also zwei Felder lang und eins breit.
Ist damit also gemeint, das Schachbrett mit Dominosteinen abzudecken, wobei die Größe der Felder analog zur Feldgröße der Dominosteine ist, also zwei Schachfelder je Dominostein?
Für diesen Fall träfe b) nicht zu, weil zwei Dominosteine auch als 4x1 Schachfelder ablegen kannst, wodurch das ganze Brett bedeckt werden kann ohne Quadratanordnung.
Oder heißt das, für jedes Schachfeld brauchst zwei Steine nebeneinander, die dann quadratisch angeordnet sind?
Das heißt dass ein dominostein 2 felder nebeneinander auf dem schachbrett belegt. und mit aufgabe b ist gemeint: zeige dass es nicht möglich ist ein schachbrett mit den steinen zu belegen, ohne das sich ein Quadrat bildet, also zwei dominosteine direkt nebeneinander liegen
Also gilt das als beweis dass ich ein bild zeichne und es daran zeige? und wieso ist die anzahl der pflasterungen gerade? das kann ich doch nicht mit zeichnen belegen oder?