Czym jest Gra Wythoffa?
W grę Wythoffa gra się dwoma stosami. W swoim ruchu albo zabierasz dowolną liczbę żetonów z jednego stosu, jak w Nim, albo zabierasz tyle samo z obu stosów naraz. Gracz, który zabierze ostatni żeton, wygrywa: w tę grę zawsze gra się normalnie, więc przełącznik misère i opcja stosów początkowych ze standardowej gry nie mają zastosowania.
Wielkości stosów pochodzą z opcji rozmiaru w ustawieniach stołu: 5 i 7 (mały), 9 i 12 (średni, domyślny) lub 14 i 20 (duży). Znany sposób na wyobrażenie sobie gry to szachowy hetman, który może ruszać się tylko w lewo, w dół lub ukośnie w dół i w lewo: dwa stosy to jego odległości od dwóch krawędzi planszy, a kto wprowadzi go do narożnika, wygrywa.
Zmiany zasad
| Zasada | Nim (standard) | Gra Wythoffa |
|---|---|---|
| Stosy | Nim (standard)Kilka stosów: domyślnie 1, 3, 5 i 7 żetonów albo inny zestaw wybrany w ustawieniach stołu. | Gra WythoffaDwa stosy: 5 i 7, 9 i 12 (domyślnie) lub 14 i 20, wybierane jako rozmiar w ustawieniach stołu. |
| Ruchy | Nim (standard)Zabierz jeden lub więcej żetonów z jednego stosu. | Gra WythoffaAlbo zabierz jeden lub więcej żetonów z jednego stosu, albo zabierz tyle samo z obu stosów. |
| 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 WythoffaZawsze gra normalna: kto zabierze ostatni żeton, wygrywa. |
| Wygrywająca gra | Nim (standard)Zostaw stosy z sumą nim (bitowym XOR ich wielkości) równą zero, z niuansem w końcówce misère. | Gra WythoffaPozycje przegrane dla gracza, który ma ruch, to pary 1 i 2, 3 i 5, 4 i 7, 6 i 10, 8 i 13 i tak dalej: k-ta para to części całkowite k × φ i k × φ², gdzie φ to złoty podział. Żadna pozycja początkowa tutaj nie jest taką parą, więc pierwszy gracz może wygrać. |
Historia
Holenderski matematyk Willem Abraham Wythoff opublikował grę i jej rozwiązanie w 1907 roku w artykule „A modification of the game of nim” w Nieuw Archief voor Wiskunde. Pokazał, że pozycje przegrane wynikają ze złotego podziału. Mniejsze i większe liczby z par przegranych tworzą dwa ciągi Beatty'ego, które razem wymieniają każdą dodatnią liczbę całkowitą dokładnie raz, dlatego gra pojawia się w tekstach o teorii liczb tak samo jak o grach.
Martin Gardner pisał o tej grze w swojej prasowej rubryce Mathematical Games w marcu 1977 roku i podał tam, że w Chinach grano w nią pod nazwą jiǎn shízǐ, „zbieranie kamieni”. Nie znamy innego źródła tego twierdzenia.