Streichhölzer wegnehmen

Streichhölzer wegnehmen ist ein Nullsummenspiel für zwei Personen.

Es gibt zumindest folgende Varianten und die zugehörigen Negativspiele:

1. Nim-Spiele, zum Beispiel Marienbad
2. Eins oder zwei: Zwischen zwei Spielern liegt ein Haufen Streichhölzer (Bohnen, Kiesel, Feuerzeuge, ...). Beide Spieler nehmen abwechselnd ein Holz oder zwei Hölzer. Wer das letzte Holz nimmt, gewinnt. – Strategie: Wer ein ganzes Vielfaches von 3 herstellt, kann immer wieder so ein Vielfaches herstellen und dadurch sicher gewinnen.
3. Verdoppeln oder Fibonacci-Nim: Zwischen zwei Spielern liegt ein Haufen Streichhölzer. Man zieht abwechselnd. Wer am Zug ist, nimmt mindestens ein Holz (Zugzwang). Wer beginnt, muss mindestens ein Holz übrig lassen. Danach nimmt jeder höchstens doppelt so viele Hölzer, wie der Gegner beim vorigen Zug genommen hat. Wer das letzte Holz nimmt, gewinnt.

Die Strategie, dargestellt mit Rekursion:

• Wenn man alle Hölzer nehmen darf, nimmt man alle und hat gewonnen.
• Sonst suche man die größte Fibonacci-Zahl, die nicht größer ist als die aktuelle Anzahl Streichhölzer: 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

• Fall 1: Sind beide Zahlen gleich, dann gibt es für diesen Spieler keinen Zug, der sicher gewinnt. Man nehme nur ein Holz, um dem Gegner möglichst oft Gelegenheit zu einem Fehler zu geben. Antwortet er einmal falsch, verliert er.
• Fall 2: Sonst bilde man die Differenz beider Zahlen. Man betrachte nur noch diese Differenz, als wäre sie die Haufengröße. Man beginne damit von vorn – und gewinnt sicher.

Die Strategie, iterativ dargestellt:

• Solange einer der beiden folgenden Schritte möglich ist, führe ihn aus. Sonst nimm ein Holz.
  • Nimm alle Hölzer.
  • Stelle durch Wegnehmen eine Summe von Fibonacci-Zahlen her, alle diese ≥ 3, verschieden und keine zwei benachbart, die kleinste so groß, dass der Gegner nicht diese Anzahl wegnehmen darf.

Beispiel: In der Ausgangssituation liegen 20 Hölzer, wir beginnen. Die größte Fibonacci-Zahl ≤ 20 ist 13. Die Differenz lautet 20-13=7. Wir nehmen 2 Hölzer (von diesen 7, mit dem Ziel 5), lassen ihm 18=13+5.

• Gegner nimmt 1, Rest 17: Wir lassen ihm 16=13+3.
  • Danach kann er nur 1 oder 2 nehmen; wir lassen ihm dann 13 (weiter wie unten).
• Gegner nimmt 2, 3 oder 4 (mehr darf er nicht), Rest 16, 15 oder 14: Wir lassen ihm 13.
  • Nimmt er dann 1, lassen wir ihm 11=8+3.
  • Nimmt er 2, 3 oder 4, Rest 11, 10 oder 9, lassen wir ihm 8.
  • Nimmt er 5 oder 6 (mehr darf er nicht), nehmen wir alle.