Что такое Игра Витхоффа?
В игру Витхоффа играют двумя кучами. В свой ход вы либо берёте любое число предметов из одной кучи, как в ниме, либо берёте поровну из обеих куч сразу. Побеждает тот, кто возьмёт последний предмет: в эту игру всегда играют обычным образом, поэтому переключатель мизера и опция начальных куч стандартной игры не применяются.
Размеры куч задаются опцией размера в настройках стола: 5 и 7 (маленький), 9 и 12 (средний, по умолчанию) или 14 и 20 (большой). Известный способ представить игру — шахматный ферзь, который может ходить только влево, вниз или по диагонали вниз-влево: две кучи — это его расстояния до двух краёв доски, а побеждает тот, кто загонит его в угол.
Изменения правил
| Правило | Ним (стандарт) | Игра Витхоффа |
|---|---|---|
| Кучи | Ним (стандарт)Несколько куч: по умолчанию 1, 3, 5 и 7 предметов или другой набор, выбранный в настройках стола. | Игра ВитхоффаДве кучи: 5 и 7, 9 и 12 (по умолчанию) или 14 и 20, выбираются как размер в настройках стола. |
| Ходы | Ним (стандарт)Возьмите один или несколько предметов из одной кучи. | Игра ВитхоффаЛибо возьмите один или несколько предметов из одной кучи, либо возьмите поровну из обеих куч. |
| Цель | Ним (стандарт)По умолчанию мизер: кто возьмёт последний предмет, проигрывает. В настройках можно переключиться на обычную игру, где взявший последний предмет побеждает. | Игра ВитхоффаВсегда обычная игра: кто возьмёт последний предмет, побеждает. |
| Выигрышная игра | Ним (стандарт)Оставляйте кучи с ним-суммой (побитовым XOR их размеров), равной нулю, с особенностью в эндшпиле мизера. | Игра ВитхоффаПроигрышные для ходящего позиции — пары 1 и 2, 3 и 5, 4 и 7, 6 и 10, 8 и 13 и так далее: k-я пара — целые части k × φ и k × φ², где φ — золотое сечение. Ни одна начальная позиция здесь не является такой парой, поэтому первый игрок может победить. |
История
Голландский математик Виллем Абрахам Витхофф опубликовал игру и её решение в 1907 году в статье «A modification of the game of nim» в журнале Nieuw Archief voor Wiskunde. Он показал, что проигрышные позиции следуют золотому сечению. Меньшие и большие числа проигрышных пар образуют две последовательности Битти, которые вместе содержат каждое натуральное число ровно один раз, поэтому игра встречается в работах по теории чисел, а не только об играх.
Мартин Гарднер писал об игре в своей журнальной колонке Mathematical Games в марте 1977 года и утверждал там, что в Китае в неё играли под названием цзянь шицзы (jiǎn shízǐ), «собирать камни». Другого источника этого утверждения мы не знаем.