Что такое Ним Фибоначчи?
В ним Фибоначчи играют одной кучей. Первый игрок может взять любое число предметов, кроме всей кучи. Дальше каждый ход берёт не меньше одного предмета и не больше удвоенного числа, только что взятого соперником. Побеждает тот, кто возьмёт последний предмет: в эту игру всегда играют обычным образом, поэтому переключатель мизера и опция начальных куч стандартной игры не применяются.
В куче 10 (маленький), 15 (средний, по умолчанию) или 20 (большой) предметов, выбирается как размер в настройках стола. Предел растёт и сжимается по ходу игры: большой ход позволяет сопернику взять ещё больше, а маленький держит его на коротком поводке, так что борьба идёт за размер следующего предела не меньше, чем за саму кучу.
Изменения правил
| Правило | Ним (стандарт) | Ним Фибоначчи |
|---|---|---|
| Кучи | Ним (стандарт)Несколько куч: по умолчанию 1, 3, 5 и 7 предметов или другой набор, выбранный в настройках стола. | Ним ФибоначчиОдна куча из 10, 15 (по умолчанию) или 20 предметов, выбирается как размер в настройках стола. |
| Первый ход | Ним (стандарт)Возьмите любое число предметов из одной кучи, в том числе всю кучу. | Ним ФибоначчиВозьмите любое число предметов, кроме всей кучи. |
| Следующие ходы | Ним (стандарт)Каждый ход берите любое число предметов из одной кучи. | Ним ФибоначчиВозьмите не меньше 1 и не больше удвоенного числа, взятого соперником на предыдущем ходу, и не больше, чем осталось. |
| Цель | Ним (стандарт)По умолчанию мизер: кто возьмёт последний предмет, проигрывает. В настройках можно переключиться на обычную игру, где взявший последний предмет побеждает. | Ним ФибоначчиВсегда обычная игра: кто возьмёт последний предмет, побеждает. |
| Выигрышная игра | Ним (стандарт)Оставляйте кучи с ним-суммой (побитовым XOR их размеров), равной нулю, с особенностью в эндшпиле мизера. | Ним ФибоначчиЗапишите кучу как сумму чисел Фибоначчи, никакие два из которых не стоят в последовательности рядом, и возьмите наименьшее из них, если предел позволяет. Первый игрок при лучшей игре проигрывает ровно тогда, когда начальная куча — число Фибоначчи; 10, 15 и 20 ими не являются, так что первый игрок может победить. |
История
Майкл Дж. Уинихан описал ним Фибоначчи в 1963 году в журнале The Fibonacci Quarterly и приписал игру Роберту Э. Гаскеллу, математику из Университета штата Орегон. Название происходит от роли, которую в решении играют числа Фибоначчи 1, 2, 3, 5, 8, 13, 21 и так далее.
Выигрышный метод опирается на то, что сейчас называют теоремой Цекендорфа: любое натуральное число единственным способом представляется суммой чисел Фибоначчи, никакие два из которых не идут подряд. Теорема названа в честь Эдуарда Цекендорфа, хотя Геррит Леккеркеркер опубликовал её ещё в 1952 году.