Handbuch für Meistergärtner

Betrachte nur die Situation, wo genau zwei Blätter und null Äste vorhanden sind. Wenn der Computer in dieser Situation zum Zug kommt, kannst Du das letzte Blatt wegnehmen und Du gewinnst das Spiel. Die Frage ist somit: kann der beginnende Spieler von Anfang an auf die "zwei-Blatt-null-Äste"-Situation hinspielen?

Nimm an, dass es für Dich als beginnenden Spieler möglich ist, durch jeden Deiner Züge die Situation "gerade Anzahl Blätter und gerade Anzahl Äste" herzustellen. (Im Folgenden werden wir das die gerade-gerade-Strategie nennen). Wir beobachten, dass beim Spiel nach jedem erlaubten Zug mehr Blätter als Äste übrig bleiben werden. Also wird die gerade-gerade-Strategie zwangsläufig nach einem Deiner Spielzüge zur Situation "zwei-Blatt-null-Äste" führen und Du gewinnst das Spiel.

Nun müssen wir noch untersuchen, ob die gerade-gerade-Strategie überhaupt realisierbar ist: Am Anfang des Spiels haben wir einen Baum bestehend aus N Blättern und N-1 Ästen. (Beim Erzeugen des Baums wird, ausgehend von einer Wurzel, jeweils ein Blatt mit einem Ast zum Baum befestigt.) Man muss zwei Fälle unterscheiden: Blätterzahl N gerade oder Blätterzahl N ungerade. Im ersten Fall erreichst Du durch Wegnehmen eines Astes, dass eine gerade Anzahl Äste (nämlich N-2) und eine gerade Anzahl Blätter (nämlich N) übrigbleiben. Im zweiten Fall muss man sicher ein Blatt wegnehmen. Da durch Entfernen des Blattes auch alle hinzuführenden Äste verschwinden, muss man also ein Blatt wegnehmen, bei dem die Zahl der damit verbundenen Äste gerade ist (zum Beispiel zwei oder null). Man kann sich überlegen, dass es so ein Blatt geben muss, in jeder Anfangssituation mit ungeradem N. Wäre nämlich, für jedes Blatt, die Anzahl damit verbundener Äste ungerade, so wäre die Summe dieser Anzahlen auch ungerade, weil sie die Summe von N ungeraden Zahlen ist. Andererseits ist diese Summe aber auch gerade, weil sie genau zweimal die Anzahl Äste ist (jeder Ast wird doppelt gezählt: für jedes seiner Blätter einmal). Dieser Widerspruch zeigt, dass die Annahme, dass es kein Blatt mit einer ungeraden Anzahl Äste gebe, falsch ist.

Wir haben also gezeigt, dass im ersten Zug die gerade-gerade Strategie anwendbar ist. Wie geht es weiter? Der Computer kommt nun an die Reihe. Nach seinem Spielzug kann die Situation "gerade Anzahl Blätter, gerade Anzahl Äste" nicht mehr herrschen: entweder nimmt er ein Blatt weg, dann hat man eine ungerade Anzahl Blätter nach seinem Zug, oder er enfernt einen Ast, was zu einer ungeraden Anzahl Ästen führt. Sein Zug wird also eine der folgenden Situationen herstellen:

Gerade Anzahl Blätter, ungerade Anzahl Äste
Ungerade Anzahl Blätter, gerade Anzahl Äste
Ungerade Anzahl Blätter, ungerade Anzahl Äste

Kannst Du nun auf all diese Situationen wieder mit der gerade-gerade-Strategie reagieren? Falls Situation 1. oder Situation 2. eingetroffen ist, weisst Du schon, wie Du vorgehen musst, nämlich genau wie beim Eröffnungszug beschrieben. Bei Situation 3. nimmst Du ein Blatt weg, das mit einer ungeraden Anzahl Ästen verbunden ist; zum Beispiel mit genau einem Ast. Solche "Endblätter", die mit genau einem Ast verbunden sind, gibt es, so lange es noch Äste gibt. (Beobachte, dass wir hier benutzen, dass es im Diagramm keinen Zykel gibt! In allgemeinen Diagrammen, in denen auch Zykel erlaubt sind, ist das Spiel denn auch viel schwieriger, und bisher ungelöst in dem Sinn, dass man keine einfache Gewinnstrategie kennt.)

Wir haben also bewiesen, dass Du, falls Du das Spiel beginnen darfst, in jedem Zug die gerade-gerade-Strategie anwenden kannst, und somit immer als Sieger hervorgehen wirst!