Streichhölzer wegnehmen

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

Es gibt folgende Varianten:

• Nim-Spiele, zum Beispiel Marienbad
• 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.
• Verdoppeln oder Fibonacci-Nim:^[1] 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. – Strategie:
  • (a) Ein Weg zum Ziel, dargestellt mit Rekursion:
    • Wenn man alle Hölzer nehmen darf, nimmt man alle.
    • Man suche 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, ...
      • Sind beide Zahlen gleich, nimmt man ein Holz, um dem Gegner möglichst oft Gelegenheit zu einem Fehler zu geben. – Macht er keinen Fehler, gewinnt er sicher. Antwortet er einmal falsch, gewinnt dieser Spieler mit dieser Strategie sicher.
      • Sind beide Zahlen verschieden, dann 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.
  • (b) Alle möglichen sicheren Wege zum Ziel:
    Wenn man alle Hölzer nehmen darf, tut man das. Sonst versucht man, durch Wegnehmen eine Summe von Fibonacci-Zahlen ≥3 herzustellen, alle diese verschieden und keine zwei benachbart, die kleinste so groß, dass der Gegner nicht diese Anzahl wegnehmen darf. Wenn das gelingt, kann man es im Fortgang des Spiels immer wieder und gewinnt sicher. Wenn nicht, kann der Gegner mit dieser Strategie sicher gewinnen.

Einzelnachweise

1. ↑ Erfinder: Robert E. Gaskell – laut Martin Gardner, Mathematischer Zirkus, Ullstein [ohne Ort] 1988, ISBN 3550076924, Seite 177