Co je Fibonacciho Nim?
Fibonacciho Nim se hraje s jedinou hromádkou. První hráč smí vzít libovolný počet předmětů kromě celé hromádky. Potom každý tah vezme nejméně jeden předmět a nejvýš dvakrát tolik, kolik soupeř právě vzal. Vyhrává hráč, který vezme poslední předmět: 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í.
Hromádka obsahuje 10 (malá), 15 (střední, výchozí) nebo 20 (velká) předmětů, volené jako velikost v nastavení stolu. Limit roste a klesá s hrou: velké braní dovolí soupeři vzít ještě víc, zatímco malé ho drží na krátké uzdě, takže hra je stejně tak bojem o velikost dalšího limitu jako o hromádku.
Změny pravidel
| Pravidlo | Standardní Nim | Fibonacciho Nim |
|---|---|---|
| Hromádky | Standardní NimNěkolik hromádek: výchozí 1, 3, 5 a 7 předmětů, nebo jiná sada zvolená v nastavení stolu. | Fibonacciho NimJedna hromádka o 10, 15 (výchozí) nebo 20 předmětech, volená jako velikost v nastavení stolu. |
| První tah | Standardní NimVezměte libovolný počet předmětů z jedné hromádky, i celou hromádku. | Fibonacciho NimVezměte libovolný počet předmětů kromě celé hromádky. |
| Další tahy | Standardní NimV každém tahu vezměte libovolný počet předmětů z jedné hromádky. | Fibonacciho NimVezměte nejméně 1 a nejvýš dvakrát tolik, kolik soupeř vzal v předchozím tahu, a ne víc, než zbývá. |
| 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á. | Fibonacciho NimVž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. | Fibonacciho NimZapište hromádku jako součet Fibonacciho čísel, z nichž žádná dvě nejsou v posloupnosti vedle sebe, a vezměte nejmenší z nich, když to limit dovolí. První hráč při nejlepší hře prohrává právě tehdy, když je počáteční hromádka Fibonacciho číslo; 10, 15 a 20 jimi nejsou, takže první hráč může vyhrát. |
Historie
Michael J. Whinihan popsal Fibonacciho Nim v roce 1963 v časopise The Fibonacci Quarterly a hru připsal Robertu E. Gaskellovi, matematikovi z Oregon State University. Název pochází z role, kterou v řešení hrají Fibonacciho čísla 1, 2, 3, 5, 8, 13, 21 a tak dále.
Vítězná metoda stojí na tom, čemu se dnes říká Zeckendorfova věta: každé kladné celé číslo je právě jedním způsobem součtem Fibonacciho čísel, z nichž žádná dvě nejdou po sobě. Věta je pojmenována po Édouardu Zeckendorfovi, ačkoli Gerrit Lekkerkerker ji publikoval už v roce 1952.