Streichhölzer wegnehmen

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

Es gibt folgende Varianten:

  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:[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:
    • Schritt 1: Wenn man alle Hölzer nehmen darf, nimmt man alle und hat gewonnen.
    • Schritt 2: 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, ...
  • Fall 1: Sind beide Zahlen gleich, dann gibt es für diesen Spieler keinen Zug, der immer gewinnt. Man nehme 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 erneut mit Schritt 1 – und gewinnt sicher.
  • (b) Alle möglichen 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.
  • Beispiel: In der Ausgangssituation liegen 20 Hölzer. Die nächstkleinere Fibonacci-Zahl ist 13. Die Differenz lautet 20-13=7. Wir nehmen 2 Hölzer (wegen des Ziels 5), Rest 18=13+5. Der Gegner kann ein Holz entfernen; dann betrachten wir 17-13=4 und nehmen eins, Rest 16=13+3. Er kann zwei, drei oder vier Hölzer entfernen, dann nehmen wir den Rest des Differenzenstapels und bringen den Haufen auf die Fibonacci-Zahl 13. (Nimmt er fünf oder mehr, nehmen wir alles.) Danach bringen wir ihn auf 8, 5, 3 und gewinnen schließlich.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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