Spielregel

An diesem Spiel nehmen zwei Spieler teil. Ein Stapel mit einer gewissen Anzahl von Spielmarken ist gegeben.

Die Spieler entnehmen dem Stapel abwechselnd Spielmarken. Sieger ist derjenige Spieler, der die letzte Spielmarke entnimmt.

Das Entnehmen der Spielmarken ist folgenden Regeln unterworfen:

Jeder Spieler muß mindestens eine Spielmarke entnehmen, wenn er an der Reihe ist.
Der Spieler, der das Spiel beginnt, muß bei seinem ersten Zug mindestens eine Spielmarke auf dem Stapel belassen.
Jeder Spieler darf höchstens doppelt so viele Spielmarken vom Stapel entnehmen, wie sein Mitspieler unmittelbar davor entnommen hat.

Beispiel

Anna und Bert haben vereinbart, daß Anna mit dem ersten Zug beginnt. Auf dem Stapel seien zu Beginn 75 Spielmarken.

Dann wäre folgende Zugfolge erlaubt:

A: 24              ergibt 51
B: 16 (Maximum 48) ergibt 35
A:  6 (Maximum 32) ergibt 29
B:  5 (Maximum 12) ergibt 24
A:  2 (Maximum 10) ergibt 22
B:  4 (Maximum  4) ergibt 18
A:  5 (Maximum  8) ergibt 13
B:  4 (Maximum 10) ergibt  9
A:  2 (Maximum  8) ergibt  7
B:  2 (Maximum  4) ergibt  5
A:  1 (Maximum  4) ergibt  4
B:  1 (Maximum  2) ergibt  3
A:  1 (Maximum  2) ergibt  2
B:  2 (Maximum  2) Damit hat Bert gewonnen.

Die Aufgabe

Dieses Spiel hat einen interessanten mathematischen Hintergrund, den es herauszufinden gilt. Wenn beide Spieler das Spiel perfekt beherrschen, dann kann, in Abhängigkeit von der Zahl der Spielmarken zu Beginn, einer der Spieler den Sieg erzwingen. Wie kann man einer Zahl von Spielmarken auf dem Anfangsstapel ansehen, ob der beginnende Spieler gewinnen kann?

Hier einige erste Überlegungen dazu: Sei N die Anzahl der Spielmarken zu Beginn. Damit das Spiel überhaupt beginnen kann, muß N > 1 sein. Schauen wir uns die Situation in einigen einfachen Fällen etwas genauer an:

N = 2: Der erste Spieler muß genau eine Spielmarke entnehmen. Der zweite entnimmt dann die verbleibende Marke und hat gewonnen.
N = 3: Der erste Spieler könnte eine oder zwei Spielmarken entnehmen, in jedem der beiden Fälle kann der zweite Spieler den Rest nehmen und hat abermals gewonnen.
N = 4: Falls der erste Spieler zwei oder drei Spielmarken entnimmt, kann der zweite den Rest nehmen. Somit wird sich Spieler eins für das Entnehmen einer Spielmarke entscheiden. Von den restlichen drei kann nun der zweite Spieler eine oder zwei Marken entnehmen. in jedem Falle hat danach der beginnende Spieler die Möglichkeit, den Stapel aufzubrauchen. Damit kann in diesem Falle der beginnende Spieler immer gewinnen.

Beim Spiel gegen die Maschine kann man erste Erfahrungen sammeln bzw. testen, ob man das Spiel durchschaut hat. Da bei dem angebotenen Programm vom menschlichen Mitspieler festgelegt werden kann, wer mit dem ersten Zug beginnt, ist es möglich, jedes Spiel gegen die Maschine zu gewinnen (bei beliebiger Zahl von Spielmarken zu Beginn)!

Viel Spaß!