8x8 Schachbrett 8 weiße Spielsteine

Question

Achim hat auf einem 8x8 Schachbrett 8 weiße Spielsteine so verteilt, dass in jeder Zeile und Spalte genau ein weißer Stein steht. Benjamin belegt nun 27 der verbleibenden freien Felder mit schwarzen Steinen und entfernt alle weißen Steine. Zeigen Sie, dass Caro 8 weiße Steine so auf die nun freien Felder stellen kann, dass in jeder Zeile und Spalte genau ein weißer Stein steht, ohne dass dabei Achims Aufstellung komplett wiederholt wird. 

Ich bitte um Hilfe, haben diese Aufgabe für morgen aufbekommen, möchte nicht ohne Lösungen dastehen, würde es aber grundsätzlich vorziehen die Aufgabe zu verstehen und nicht die Lösung zu kennen :)

Comments

Und wieder eine Aufgabe aus der aktuellen Mathe-Olympiade!

http://www.gsglebach.de/fileadmin/Dokumente_und_Grafiken/MaOly/MO531_Aufgaben_5-12.pdf

Answer 1

man kann ohne Beschränkung der Allgemeinheit annehmen, dass die 8 weißen Steine auf die Diagonale gelegt wurden. Jede andere Lege-Art und -Weise kann nämlich durch Zeilen- und Spalten-Permutationen auf die Diagonale zurückgeführt werden. In diesem Sinne sind alle Lege-Arten äquivalent.

Mit 27 Blockadesteinen kann man nun unmöglich alle verbleibenden Permutationen verhindern. Denn angenommen, man will die Wahl des ersten weißen Steins komplett einschränken (der z.B. (und o.B.d.A.) links unten auf der Diagonalen liege), dann braucht man 9 + 9 = 18 Steine. Um die Wahl des zweiten Steines nun komplett einzuschränken, bräuchte man 8 + 8 = 16 Steine. 16 und 18 übersteigt zusammen aber schon die Zahl 27. Somit ist mit Hilfe der Spalten- und Zeilenpermutationen immer eine neue Permutation möglich, die nicht komplett der alten entspricht. Man kann sogar sagen, dass nicht mehr als ein weißer Stein auf seinen Ursprungsort fixiert werden kann.

MfG

Mister

Comments

und ich dachte schon ich bräuchte eine formel und hab gegrübelt und gegrübelt... haben nämlich gerade formeln in mathe (7.klasse). Da hat uns unser Lehrer aber ganz schön auf den Arm genommen...


Vielen Dank, ist alles einleuchtend uns verständlich erklärt, und das so schnell!
PS: das wort permutation werde ich wohl erstmal googeln müssen

---

ich habe auch gerade einen Fehler in meiner Argumentation entdeckt: Der zweite Absatz stimmt so nicht. Ich korrigier' ihn gerade mal.

MfG

Mister

---

Korrektur: Das mit der 9 ist natürlich falsch. Wir haben ja nicht 10 mal 10, sondern nur 8 mal 8 Felder.

Zur Fixierung des ersten Steines braucht es 7 schwarze Steine. Für die des zweiten 6, etc.. Macht man so weiter, erreicht man 7 + 6 + 5 + 4 + 3 + 2 = 27 Blockierungen. Der letzte Stein hat freie Wahl.

Um alle möglichen Permutationen zu verhindern, bräuchte man 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 schwarze Steine.

Answer 2

Naja. Nehmen wir mal an Achim hat eine Diagonale aufgebaut. A1, B2, C3, ...

Nun könnte man immer 2 Steine umlegen um eine neue Anordnung zu bekommen. Also A1 auf A2 und B2 auf B1 oder A1 auf A3 und C3 auf C1.

Theoretisch müsste Benjamin also alle diese 2er Umordnungen verhindern. Das geht aber mit 27 Steinen nicht.

Man benötigt um alle möglichen 2er Ordnungen zu unterbinden

7 +6 + 5 + 4 + 3 + 2 + 1 = 28 Steine.

Es bleibt also irgendwo eine Lücke die man dann ausnutzen kann.

Comments

Stimmt! und es gibt ja noch viel mehr als nur diese zwei Vertauschungsmöglichkeiten.
Folglich reichen 27 Steine vorne und hinten nicht, oder?

---

Nein, 28 schwarze würden langen