Streichholzer wegnehmen ist ein Nullsummenspiel fur zwei Personen Es gibt zumindest folgende Varianten und die zugehorigen Negativspiele Nim Spiele zum Beispiel Marienbad Eins oder zwei Zwischen zwei Spielern liegt ein Haufen Streichholzer Bohnen Kiesel Feuerzeuge Beide Spieler nehmen abwechselnd ein Holz oder zwei Holzer 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 Streichholzer Man zieht abwechselnd Wer am Zug ist nimmt mindestens ein Holz Zugzwang Wer beginnt muss mindestens ein Holz ubrig lassen Danach nimmt jeder hochstens doppelt so viele Holzer wie der Gegner beim vorigen Zug genommen hat Wer das letzte Holz nimmt gewinnt Die Strategie dargestellt mit Rekursion Wenn man alle Holzer nehmen darf nimmt man alle und hat gewonnen Sonst suche man die grosste Fibonacci Zahl die nicht grosser ist als die aktuelle Anzahl Streichholzer 3 5 8 13 21 34 55 89 144 Fall 1 Sind beide Zahlen gleich dann gibt es fur diesen Spieler keinen Zug der sicher gewinnt Man nehme nur ein Holz um dem Gegner moglichst 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 ware sie die Haufengrosse Man beginne damit von vorn und gewinnt sicher dd dd Die Strategie iterativ dargestellt Solange einer der beiden folgenden Schritte moglich ist fuhre ihn aus Sonst nimm ein Holz Nimm alle Holzer Stelle durch Wegnehmen eine Summe von Fibonacci Zahlen her alle diese 3 verschieden und keine zwei benachbart die kleinste so gross dass der Gegner nicht diese Anzahl wegnehmen darf dd Beispiel In der Ausgangssituation liegen 20 Holzer wir beginnen Die grosste Fibonacci Zahl 20 ist 13 Die Differenz lautet 20 13 7 Wir nehmen 2 Holzer 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 dd Einzelnachweise Bearbeiten Erfinder Robert E Gaskell laut Martin Gardner Mathematischer Zirkus Ullstein ohne Ort 1988 ISBN 3 550 07692 4 Seite 177 Abgerufen von https de wikipedia org w index php title Streichholzer wegnehmen amp oldid 206866321
