Mathematisch argumentieren

Wie viele Springer kann man maximal auf einem Schachfeld platzieren, ohne dass sie sich gegenseitig angreifen?

Diese Frage werden wir uns genauso auch mit weiteren Schachfiguren stellen. Falls du noch nicht weißt, wie die Schachfiguren ziehen, kannst du das hier nachschauen. Für diesen Artikel reicht es aus, wenn du weißt, wie sich Springer, Turm, König und Läufer bewegen.

Du hast mehrere Möglichkeiten diesen Artikel zu lesen. Du kannst dir selber Gedanken zu den beschriebenen Aufgaben machen und probieren sie zu lösen. Alternativ kannst du ihn einfach lesen und den gesamten Gedankengang von den ersten Ideen bis zur vollständigen Lösung mit Beweis mitverfolgen.

Wie geht man so ein Problem an?

Es ist es immer eine gute Idee, am Anfang ein bisschen rumzuprobieren, um ein besseres Gefühl für die Aufgabe zu bekommen. Zum Beispiel können wir zunächst die Springer Feld für Feld so aufstellen, dass sie sich nicht angreifen. Wir gehen also zeilenweise von links nach rechts vor und stellen einen Springer auf das entsprechende Feld, sofern das Feld noch nicht bedroht ist.

Im Wesentlichen führen wir dabei einen „Greedy-Algorithmus“ durch. In jedem einzeilnen Schritt wählen wir gierig das nächste Feld aus, sofern das noch möglich ist.

In der ersten Zeile werden auf diese Weise alle Felder belegt.

Die nächsten beiden Zeilen können dann nicht belegt werden, weil alle Felder schon von Springern der ersten Zeile angegriffen sind.

Die vierte Zeile können wir wieder voll besetzen. Nun sind die fünfte und sechste Zeile nicht mehr möglich und die siebte wird wieder vollständig besetzt. In der letzen Zeile gibt es dann keine Möglichkeiten mehr.

Am Ende sieht die Belegung also folgendermaßen aus:

Insgesamt kommen wir mit diesem Verfahren auf 24 Springer. Das bedeutet, dass die Antwort auf die Frage mindestens 24 ist. Sie kann zum Beispiel nicht 20 sein, weil wir 24 Springer aufstellen können.

Wir sind aber lange noch nicht fertig, schließlich müssen wir jetzt noch bessere Lösungen mit mehr als 24 Springern finden oder beweisen, dass es nicht mehr als 24 sein können.

Ein erster Beweisversuch

Wir haben in jedem Schritt einen Springer platziert, wenn das möglich war. Am Ende sind alle anderen Felder bedroht, also können keine weiteren Springer auf das Feld gestellt werden. Also kann man nicht mehr als 24 Springer auf dem Schachfeld aufstellen.

Auch wenn dieser „Beweis“ zunächst vielversprechend aussieht, ist er leider falsch. Du kannst dir schon einmal überlegen, wo der Fehler liegt.

Eine wichtige Feststellung

Wenn man sich die Zugmöglichkeiten des Springers anschaut, stellt man fest, dass er in jedem Zug die Farbe wechselt. Das bedeutat aber, dass ein Springer auf einem schwarzen Feld nur weiße Felder bedroht und analog ein Springer auf einem weißen Feld nur schwarze.

Ein Springer bewegt sich immer drei Felder, zwei waagerecht und eins senkrecht oder umgekehrt. Wenn man die Felder einzeln durchgeht, wechselt sich immer die Farbe. Drei Farbwechsel, also eine ungerade Anzahl, führen insgesamt zu einem Farbwechsel.

Hier noch einmal das Schachbrettmuster zur Veranschaulichung:

Platzieren wir also Springer auf allen schwarzen Feldern, das sind genau die Hälfte, also insgesamt 32, können sie sich nicht angreifen. Wir haben eine bessere Lösung gefunden!

Spätestens jetzt ist klar, dass das obige Argument für 24 nicht ganz richtig gewesen sein kann. Schließlich kann nicht gleichzeitig 24 das Maximum sein und 32 eine mögliche Lösung besitzen.

Was war der Fehler?

In jedem Schritt haben wir immer nur ein einzelnes Feld angeschaut und nur für dieses Feld optimiert. Dabei haben wir nicht berücksichtigt, dass dadurch spätere Felder ausgeschlossen werden. Wir haben hier nur lokal (für einzelne Felder) statt global (für das gesamte Feld) argumentiert. Wir haben nur gezeigt, dass für diese eine Strategie nur 24 möglich sind. Es ist aber zu beweisen, dass das für alle Strategien maximal ist.

Mittlerweile wissen wir, dass die Lösung mindestens 32 ist, haben aber immer noch kein richtiges Argument für ein Maximum. Es liegt zumindest die Vermutung nahe, dass 32 das Maximum sein könnte, weil die Springer schon recht dicht stehen und jedes zweite Feld belegt ist. Das ist aber natürlich noch lange kein Beweis.

Man könnte jetzt wieder argumentieren, dass 32 Felder belegt sind und alle weiteren Felder bedroht sind, also nicht mehr als 32 möglich sind. Das ist allerdings das gleiche Argument, das wir vorhin schon bei 24 hatten. Es wäre nur für diese Strategie gezeigt, dass nicht mehr als 32 möglich sind. Nur weil jetzt vielleicht das Ergebnis richtig ist, ist es der Beweis dafür noch lange nicht!

Schließlich ist es noch nicht ausgeschlossen, dass es mit einer ganz anderen Strategie noch mit viel mehr Springern möglich ist, vielleicht gehen zum Beispiel 40 Springer. Die Aufgabe ist eben genau zu beweisen, dass das nicht geht.

Wie beweist man dann überhaupt eine Maximalzahl?

Sind 100 Springer möglich? Natürlich nicht, weil es nur 64 Felder gibt. Wir können uns auch noch überlegen, dass es nicht 64 sein können, weil dann alle Felder belegt wären und sich dann auch Springer bedrohen. Also können es maximal 63 sein. Wir wissen jetzt also schon einmal, dass die Lösung zwischen 32 und 63 liegt.

Doch wie finden wir eine sinnvolle Maximalzahl? Meistens ist es so, dass man dafür auch noch einmal eine gute Idee braucht. Wenn man diese Idee noch nicht hat, kann man mal ein bisschen üben.

Schauen wir uns also mal ein etwas einfacheres Problem an, die gleiche Aufgabe mit Türmen. Die Hoffnung ist, dass wir durch das Turmproblem sehen, wie man eine Maximalzahl beweisen kann und dieses Prinzip dann auf die Springer zu übertragen.

Auch beim Turmproblem kann man erst einmal etwas herumprobieren. Zum Beispiel können wir eine der beiden Diagonalen mit Türmen belegen, also sind auf jeden Fall 8 Türme möglich.

Es gibt 8 Zeilen und in jeder dieser Zeilen kann maximal ein Turm stehen, weil sie sich sonst angreifen. Daher kann man insgesamt maximal 8 Türme auf einem Schachfeld aufstellen, ohne dass sie sich gegenseitig angreifen.

Für diese Anzahl haben wir aber schon ein Beispiel konstruiert. Wir haben also gezeigt, dass man 8 Türme auf einem Schachfeld platzieren kann, ohne dass sie sich bedrohen. Gleichzeitig haben wir bewiesen, dass es auch nicht mehr als 8 sein können. Also sind 8 Türme hier die richtige Lösung.

Das Schubfachprinzip

Im Prinzip haben wir hier ein recht einfaches, aber doch mächtiges mathematisches Werkzeug angewendet, nämlich das Schubfachprinzip.

Zunächst werden wir sehen, was dieses Prinzip besagt. In einem zweiten Schritt werden wir die Lösung für das Turmproblem etwas umformulieren und das Schubfachprinzip verwenden. Damit wird es später leicher fallen, den Beweis auf das Springerproblem zu übertragen.

Beim Schubfachprinzip verteilt man Perlen auf Schubfächer. Dabei gibt es mehr Perlen als Schubfächer. Dann folgt, dass es mindestens ein Schubfach gibt, in dem mindestens 2 Perlen sind. Etwas exakter:

Sei n eine natürliche Zahl. Verteilt man mehr als n Perlen auf n Schubladen, so existiert mindestens eine Schublade, in der mindestens 2 Perlen sind.

Angenommen eine solche Schublade existiert nicht. Dann sind in jeder Schublade maximal eine (also keine oder eine) Perle. Es gibt n Schubladen, also insgesamt maximal n Perlen. Allerdings muss es insgesamt mehr als n Perlen geben, ein Widerspruch. Also war die Annahme falsch und ein solches Schubfach existiert.

Im Beweis haben wir ein sehr häufig verwendetes Beweismittel benutzt, den Beweis durch Widerspruch. Wir nehmen an, dass etwas gilt und führen das dann zum Widerspruch.

Bei der Verwendung des Schubfachprinzips muss man geeignete Perlen und Schubfächer finden, das probieren wir jetzt für das Turmproblem aus.

Wir nehmen mal an, dass es eine Belegung mit mehr als 8 Türmen gibt. Die Türme sind die Perlen und die Zeilen des Schachfelds die Schubfächer. Mit dem Schubfachprinzip für n=8 erhalten wir, dass es eine Zeile (Schubfach) gibt, in der zwei Türme (Perlen) stehen. Das ist aber nicht möglich, weil sie sich dann angreifen. Widerspruch! Also kann man nicht mehr als 8 Türme platzieren und somit maximal 8.

Zurück zum Ursprungsproblem

Was haben wir gelernt, was wir für das Springerproblem anwenden können? Wir versuchen zu beweisen, dass 32 die Maximalzahl ist. Wenn wir versuchen, genauso wie bei den Türmen vorzugehen, nehmen wir also an, dass mehr 32 als Springer möglich wären. Die Springer sind unsere Perlen.

Wir müssen noch geeignete Schubfächer suchen. Als Anzahl der Schubfächer bietet sich 32 an, weil dann mit dem Schubfachprinzip in einem Schubfach mindestens 2 Springer sind. Das muss dann irgendwie zum Widerspruch führen.

Die geeigneten Schubfächer finden

Wir suchen also nach 32 Schubfächern für die 64 Felder, sodass sich ein Widerspruch ergibt, wenn 2 Springer in einem Schubfach sind. Es bietet sich geradezu an, 32 Paare von Feldern zu bilden, die eine Springerbewegung voneinander entfernt sind, weil sich dann 2 Springer in diesem Schubfach angreifen würden. Die Frage ist also, ob wir das Schachfeld in solche Paare aufteilen können.

Hier gilt wieder: Ausprobieren! Es ist besonders hilfreich, wenn man nicht wahllos ausprobiert, sondern mit einer gewissen Struktur, die sich wiederholt.

Beispielsweise kann man in einem 2 \times 4-Rechteck vier solche Paare bilden. Außerdem kann man das Schachbrett in acht solche Rechtecke aufteilen. Es ist also tatsächlich möglich, 32 geeignete Schubfächer zu finden.

Wie sieht eine vollständige Lösung aus?

Wir haben jetzt alle nötigen Ideen und müssen sie noch zu einem Beweis zusammenfügen. Die erste Idee mit den 24 Feldern brauchen wir dabei natürlich nicht erwähnen, genauso wie den Einschub der Turmaufgabe. Eine Lösung könnte dann wie folgt aussehen:

Man kann maximal 32 Springer auf einem Schachfeld platzieren, ohne dass sie sich gegenseitig angreifen. Es sind 32 Springer möglich, indem alle schwarzen Felder verwendet werden. Dann bedroht jeder Springer nur weiße Felder, also bedrohen sie sich insbesondere nicht gegenseitig.

Angenommen es geht mit mehr als 32 Springern. Bilde 32 Paare von Schachfeldern, indem das Brett in acht 2 \times 4-Rechtecke zerlegt wird und in diesen jeweils vier Paare gebildet werden (hier könnte man jetzt noch einmal die obigen Abbildungen einfügen). Nach dem Schubfachprinzip gibt es mindestens ein Paar, das mit zwei Springern belegt ist. Dann greifen sie sich aber an, ein Widerspruch! Also sind maximal 32 Springer möglich.

Da mit 32 Springern eine Belegung der Springer existiert und auch nicht mehr möglich sind, ist 32 die Lösung für das Problem.

Wie funktioniert das ganze mit Königen?

Wir können als Erstes wieder die erste Idee des Greedy-Algorithmus anwenden und Feld für Feld durchgehen. Damit erhalten wir 16 Könige in der folgenden Aufstellung:

Gleichzeitig gibt diese Belegung aber auch gleich eine gute Idee für eine Schubfachauswahl. Das Brett kann in 16 Quadrate mit 2\times 2 Feldern zerlegt werden. Dann argumentieren wir wieder genauso mit dem Schubfachprinzip, dass bei mehr als 16 Königen in einem dieser Quadrate zwei Könige oder mehr stehen müssen. Dann greifen sie sich aber an. Also ist 16 die Maximalzahl und weil 16 wegen dem Beispiel möglich sind, ist es auch die Lösung.

Hier sehen wir, dass die erste Idee beim Springerproblem allgemein gesehen doch gar nicht so schlecht war, nur im konkreten Fall leider nicht funktioniert hat.

Was ist mit Läufern und Damen?

Für Läufer kannst du dir mal selber überlegen, was das Maximum ist, wie das Beispiel dazu aussieht und wie man das beweisen kann.

Auch hier hat die Aufgabe wieder zwei Teile. Zum Einen muss man ein Beispiel für die gefundene Lösung angeben. Zum Anderen ist zu beweisen, dass nicht mehr möglich sind.

Ich habe die Antwort und Beweisideen (aber keine ausführlichen Beweise!) mal versteckt.

Beispiel für diese Anzahl	SelectAnzeigen

Für Damen ist das ganze etwas komplizierter, das Problem ist auch als das Damenproblem bekannt. Tatsächlich ist es mit 8 Damen möglich. Der Maximalitätsbeweis sollte recht klar sein, das Beispiel ist aber nicht so einfach zu konstruieren, aber eine ganz nette Knobelaufgabe.

Was du aus diesem Artikel lernen kannst

Natürlich ist es unbedeutend, dass du jetzt weißt, wie viele Springer man auf einem Schachfeld stellen kann, ohne dass sie sich bedrohen. Die dabei verwendeten Methoden und Denkweisen sind dafür umso nützlicher und vielseitig einsetzbar.

Für ein besseres, klareres und strukturierteres Denken ist es wichtig, dass du verstehst, wie die Argumentationen funktionieren, warum sie notwendig sind und auch wieso der erste Beweis für 24 Springer nicht richtig war.

Es gibt auch eine gute Möglichkeit zu testen, ob du alles wirklich verstanden hast: Gib jemandem die Aufgabe und nach und nach sofern nötig Tipps für die Lösung.

Im nächsten Artikel sollst du dann einmal selbst aktiv werden und mithilfe von Tipps einen Beweis finden.