Was ist Subtraktionsspiel?
Das Subtraktionsspiel ist Nim mit einer Grenze für jeden Zug. Sie nehmen weiterhin Objekte aus einem Haufen Ihrer Wahl, aber mindestens eines und höchstens k, wobei k gleich 2, 3, 4 oder 5 ist und im Tisch-Setup gewählt wird (standardmäßig 3). Einen ganzen Haufen dürfen Sie nur nehmen, wenn er k oder weniger Objekte enthält.
Alles andere ist wie im Standardspiel: Die Starthaufen kommen aus derselben Setup-Option (standardmäßig 1, 3, 5 und 7), und der Misère-Schalter entscheidet, ob das Nehmen des letzten Objekts verliert (hier der Standard) oder gewinnt. Die Obergrenze verändert die Arithmetik des Spiels. Ein großer Haufen lässt sich nicht mehr in einem Zug leeren, kann die Stellung also nicht mit einem Schlag in Ordnung bringen, und was bei jedem Haufen zählt, ist seine Größe geteilt durch k + 1: der Rest.
Regeländerungen
| Regel | Standard-Nim | Subtraktionsspiel |
|---|---|---|
| Züge | Standard-NimEin oder mehrere Objekte aus einem Haufen nehmen, so viele Sie wollen, bis zum ganzen Haufen. | SubtraktionsspielMindestens 1 und höchstens k Objekte aus einem Haufen nehmen; k ist 2, 3, 4 oder 5, im Tisch-Setup gewählt (standardmäßig 3). |
| Haufen | Standard-NimMehrere Haufen: standardmäßig 1, 3, 5 und 7 Objekte oder eine andere im Tisch-Setup gewählte Aufstellung. | SubtraktionsspielDieselben Haufen, mit derselben Option gewählt. |
| Ziel | Standard-NimStandardmäßig Misère: Wer das letzte Objekt nimmt, verliert. Im Setup lässt sich auf normales Spiel umschalten, bei dem das Nehmen des letzten Objekts gewinnt. | SubtraktionsspielGenauso, mit demselben Misère-Schalter. |
| Gewinnstrategie | Standard-NimNormales Spiel: Hinterlassen Sie die Haufen mit einer Nim-Summe (dem bitweisen XOR ihrer Größen) von null. Misère: genauso, bis nur noch Haufen mit einem Objekt übrig blieben; dann hinterlassen Sie eine ungerade Anzahl davon. | SubtraktionsspielNormales Spiel: Jeder Haufen zählt als Rest seiner Größe geteilt durch k + 1, und Sie hinterlassen diese Reste mit einer Nim-Summe von null; ein einzelner Haufen ist für den Spieler am Zug genau dann verloren, wenn seine Größe ein Vielfaches von k + 1 ist. Misère: Ein einzelner Haufen ist für den Spieler am Zug genau dann verloren, wenn seine Größe um eins größer als ein Vielfaches von k + 1 ist. |
Geschichte
Zählspiele mit einer Obergrenze pro Zug sind alt. Claude-Gaspard Bachet de Méziriacs Problèmes plaisants et délectables, eine Sammlung mathematischer Unterhaltungen, erstmals 1612 in Paris erschienen, beschreibt ein Spiel, in dem zwei Spieler abwechselnd eine Zahl von 1 bis 10 zu einer laufenden Summe addieren, und wer zuerst 100 erreicht, gewinnt. Der Gewinnplan ist, die Summen 12, 23, 34 und so weiter bis 89 zu erreichen, in Schritten von 11: dieselbe Arithmetik wie bei einem einzelnen Haufen von 100, aus dem jeder Zug 1 bis 10 nimmt.
Nim selbst erhielt seinen Namen und seine vollständige Theorie 1901 von Charles L. Bouton. Die Arbeiten von Roland Sprague (1935) und Patrick Grundy (1939) zeigten, dass sich jedes Spiel dieser Art, auch das Subtraktionsspiel, wie ein Nim-Haufen einer bestimmten Größe verhält, und so wird die Version mit mehreren Haufen gelöst. Subtraktionsspiele sind ein Standardbeispiel der Theorie kombinatorischer Spiele, etwa in Winning Ways for your Mathematical Plays von Elwyn Berlekamp, John Conway und Richard Guy.