Hat jemand eine Idee, wie diese Aufgabe mit spieltheoretischen Prinzipien gelöst werden kann?

Question

Aufgabe:

Auf einem nxn Quadrat sind Spielsteine derart platziert, dass in jeder Reihe und in jeder Spalte genau ein Stein liegt. Die Steine sind in einer gewissen Anordnung a positioniert. Nun existiert auch eine weitere Anordnung B, für die gilt:

In jedem Rechteck aus Gitterquadraten, dass eine Ecke in der oberen linken des gesamten nxn Quadrats hat, sind mindestens so viele Spielsteine wie in Anordnung A.

Aufgabe: Mit folgendem Zug soll aus Anordnung A die Anordnung B konstruiert werden (Zu zeigen ist, dass das immer möglich ist).

Es wird ein Rechteck aus Gitterquadraten gewählt, in dem sich oben rechts und unten links ein Spielstein befindet. Jetzt werden die Steine in die beiden freien Ecken des Rechtecks gelegt.

Problem/Ansatz:

Hat jemand eine Idee, wie diese Aufgabe mit Spieltheoretischen Prinzipien gelöst werden kann? Mir scheint es zwar logisch kann, dass mit diesem Zug Anordnung B erzeugt werden kann (da ja ein Spielstein weiter nach links oben wandert), aber ich habe keine Idee für einen korrekten Beweis. Vielen Dank für jede Hilfe!!!

Answer 1

In dem p×q-Rechteck von der linken oberen Ecke aus betrachtet befinden sich vorher s Steine.

Es wird das Rechteck mit den belegen Ecken (a,b) und (c,d) ausgewählt.

Begründe, warum die beiden anderen Ecken (a,d) und (c,b) frei sind.

Mache dann eine Fallunterschiedung in Abhängigkeit davon, wie viele Ecken des abcd-Rechtecks in dem p×q-Rechteck liegen.

Comments

Ich glaube ich kann soweit folgen und der Ansatz erscheint sehr sinnvoll. Allerdings darf sich in dem Rechteck mit den belegten Ecken (a,b) und (c,d) kein weiterer Stein befinden. Es reicht also nicht zu zeigen, dass die anderen Ecken frei sind.

---

Allerdings darf sich in dem Rechteck mit den belegten Ecken (a,b) und (c,d) kein weiterer Stein befinden.

Doch. Aber deren Verteilung ändert sich durch den Zug nicht. Deshalb reicht es, zu betrachten was sich durch den Zug an den Ecken verändert.

---

Okay, ich fürchte das habe ich unsauber formuliert. Nach Aufgabenstellung darf sich in dem Rechteck mit den belegten Ecken (a,b) und (c,d) kein weiterer Stein befinden.

---

Nach Aufgabenstellung darf sich in dem Rechteck mit den belegten Ecken (a,b) und (c,d) kein weiterer Stein befinden.

Das kann ich der Aufgabenstellung nicht entnehmen. Und auch wenn das in der Aufgabenstellung so stehen würde, würde das die Aufgabe nur vereinfachen, weil es weniger Möglichkeiten gäbe, a, b, c und d zu wählen.

---

Wie gesagt, das habe ich nicht ordentlich übernommen, in der Aufgabenstellung die ich bekommen habe steht, dass ein Rechteck zu wählen ist, dass nur genau in der Ecke oben rechts und der unten links je einen Spielstein hat.

Mir ist leider immer noch nicht klar, wieso die Aufgabe dadurch einfacher wird. Dadurch muss man doch nicht nur zeigen, dass die beiden anderen Ecken (a,d) und (c,b) frei sind, sondern auch, dass das restliche Rechteck frei ist (eben abgesehen von den Steinen oben rechts und unten links).

Übrigens noch mal vielen Dank für die Hilfe!!!

---

zeigen, dass ... das restliche Rechteck frei ist ...

Das muss man nicht zeigen. Das ist durch die Regeln für die Wahl des Rechtecks so vorgegeben.