Co je Wythoffova hra?
Wythoffova hra se hraje se dvěma hromádkami. Na tahu buď vezmete libovolný počet předmětů z jedné hromádky, jako v Nimu, nebo vezmete stejný počet z obou hromádek najednou. Vyhrává hráč, který vezme poslední předmět: tato hra se vždy hraje normálním způsobem, takže přepínač misère a volba počátečních hromádek ze standardní hry zde neplatí.
Velikosti hromádek určuje volba velikosti v nastavení stolu: 5 a 7 (malá), 9 a 12 (střední, výchozí) nebo 14 a 20 (velká). Známou představou hry je šachová dáma, která smí táhnout jen doleva, dolů nebo úhlopříčně doleva dolů: dvě hromádky jsou její vzdálenosti od dvou okrajů šachovnice a kdo ji dotáhne do rohu, vyhrává.
Změny pravidel
| Pravidlo | Standardní Nim | Wythoffova hra |
|---|---|---|
| Hromádky | Standardní NimNěkolik hromádek: výchozí 1, 3, 5 a 7 předmětů, nebo jiná sada zvolená v nastavení stolu. | Wythoffova hraDvě hromádky: 5 a 7, 9 a 12 (výchozí) nebo 14 a 20, volené jako velikost v nastavení stolu. |
| Tahy | Standardní NimVezměte jeden nebo více předmětů z jedné hromádky. | Wythoffova hraBuď vezměte jeden nebo více předmětů z jedné hromádky, nebo stejný počet z obou hromádek. |
| Cíl | Standardní NimVýchozí je misère: kdo vezme poslední předmět, prohrává. Nastavení lze přepnout na normální hru, kde vzetí posledního předmětu vyhrává. | Wythoffova hraVždy normální hra: kdo vezme poslední předmět, vyhrává. |
| Vítězná hra | Standardní NimNechte hromádky s nim-součtem (bitovým XOR jejich velikostí) rovným nule, se zvláštností v misère koncovce. | Wythoffova hraPozice prohrané pro hráče na tahu jsou dvojice 1 a 2, 3 a 5, 4 a 7, 6 a 10, 8 a 13 a tak dále: k-tá dvojice jsou celé části k × φ a k × φ², kde φ je zlatý řez. Žádná výchozí pozice zde takovou dvojicí není, takže první hráč může vyhrát. |
Historie
Nizozemský matematik Willem Abraham Wythoff publikoval hru a její řešení v roce 1907 v článku „A modification of the game of nim“ v časopise Nieuw Archief voor Wiskunde. Ukázal, že prohrané pozice sledují zlatý řez. Menší a větší čísla prohraných dvojic tvoří dvě Beattyho posloupnosti, které spolu obsahují každé kladné celé číslo právě jednou, a proto se hra objevuje v textech o teorii čísel stejně jako o hrách.
Martin Gardner o hře psal ve svém časopiseckém sloupku Mathematical Games v březnu 1977 a uvedl tam, že se v Číně hrála pod názvem jiǎn shízǐ, „sbírání kamínků“. Jiný zdroj tohoto tvrzení neznáme.