Czym jest Gra z odejmowaniem?
Gra z odejmowaniem to Nim z limitem na każdy ruch. Nadal zabierasz żetony z jednego wybranego stosu, ale co najmniej jeden i najwyżej k, gdzie k wynosi 2, 3, 4 lub 5 i wybierasz je w ustawieniach stołu (domyślnie 3). Cały stos możesz zabrać tylko wtedy, gdy ma k żetonów lub mniej.
Wszystko inne jest jak w standardowej grze: stosy początkowe pochodzą z tej samej opcji ustawień (domyślnie 1, 3, 5 i 7), a przełącznik misère decyduje, czy zabranie ostatniego żetonu przegrywa (tutaj domyślnie), czy wygrywa. Limit zmienia arytmetykę gry. Dużego stosu nie da się już opróżnić jednym ruchem, więc nie można nim naprawić pozycji za jednym zamachem, a o każdym stosie decyduje reszta z dzielenia jego wielkości przez k + 1.
Zmiany zasad
| Zasada | Nim (standard) | Gra z odejmowaniem |
|---|---|---|
| Ruchy | Nim (standard)Zabierz jeden lub więcej żetonów z jednego stosu, ile chcesz, aż do całego stosu. | Gra z odejmowaniemZabierz co najmniej 1 i najwyżej k żetonów z jednego stosu; k wynosi 2, 3, 4 lub 5 i wybierasz je w ustawieniach stołu (domyślnie 3). |
| Stosy | Nim (standard)Kilka stosów: domyślnie 1, 3, 5 i 7 żetonów albo inny zestaw wybrany w ustawieniach stołu. | Gra z odejmowaniemTe same stosy, wybierane tą samą opcją. |
| Cel | Nim (standard)Domyślnie misère: kto zabierze ostatni żeton, przegrywa. W ustawieniach można przełączyć na grę normalną, w której zabranie ostatniego żetonu wygrywa. | Gra z odejmowaniemTak samo, z tym samym przełącznikiem misère. |
| Wygrywająca gra | Nim (standard)Gra normalna: zostaw stosy z sumą nim (bitowym XOR ich wielkości) równą zero. Misère: tak samo, dopóki nie zostałyby same stosy po jednym żetonie; wtedy zostaw ich nieparzystą liczbę. | Gra z odejmowaniemGra normalna: każdy stos liczy się jako reszta z dzielenia jego wielkości przez k + 1, a ty zostawiasz te reszty z sumą nim równą zero; pojedynczy stos przegrywa gracz, który ma ruch, dokładnie wtedy, gdy jego wielkość jest wielokrotnością k + 1. Misère: pojedynczy stos przegrywa gracz, który ma ruch, dokładnie wtedy, gdy jego wielkość jest o jeden większa od wielokrotności k + 1. |
Historia
Gry w liczenie z limitem na każdy ruch są stare. Problèmes plaisants et délectables Claude'a-Gasparda Bacheta de Méziriac, zbiór matematycznych rozrywek wydany po raz pierwszy w Paryżu w 1612 roku, opisuje grę, w której dwaj gracze na zmianę dodają liczbę od 1 do 10 do bieżącej sumy, a kto pierwszy osiągnie 100, wygrywa. Plan wygranej to osiągać sumy 12, 23, 34 i tak dalej aż do 89, co 11: ta sama arytmetyka co w pojedynczym stosie 100 żetonów, z którego każdy ruch zabiera od 1 do 10.
Samo Nim dostało nazwę i pełną teorię od Charlesa L. Boutona w 1901 roku. Prace Rolanda Sprague'a (1935) i Patricka Grundy'ego (1939) pokazały, że każda gra tego rodzaju, także gra z odejmowaniem, zachowuje się jak stos Nim pewnej wielkości, i tak rozwiązuje się wersję z kilkoma stosami. Gry z odejmowaniem to standardowy przykład w teorii gier kombinatorycznych, na przykład w Winning Ways for your Mathematical Plays Elwyna Berlekampa, Johna Conwaya i Richarda Guya.