Ним Витхоффа

Ним Витхоффа, или игра Витхоффа, — стратегическая математическая игра для двоих игроков с двумя кучками фишек. Игроки по очереди берут фишки из одной или обеих кучек; в последнем случае из обеих кучек берется поровну фишек. Выигрывает тот, кто забирает последнюю или последние фишки.

Мартин Гарднер в книге «От мозаик Пенроуза к надежным шифрам» (глава 8) утверждает, что игра известна в Китае под названием 捡石子 цзяньшицзы^[1]^[2] («взятие камней»).^[3] Голландский математик Виллем Витхофф^[англ.] сделал анализ игры в 1907 году.

Оптимальная стратегия

Любую позицию в игре можно описать парой чисел (n, m), при n ≤, где n и m — количество фишек в кучках. Стратегия игры строится на определении хороших и плохих позиций: плохая позиция (англ.: cold position) — позиция, проигрышная даже при оптимальных действиях игрока, который находится в ней; хорошая (hot) позиция — та, начиная с которой игрок при оптимальных действиях выигрывает. Оптимальной стратегией для игрока, находящейся в хорошей позиции — переводить игру в любую из плохих позиций, передавая право хода сопернику, который, в свою очередь, будет переводить игру в хорошую позицию для первого игрока.

Классификация позиций на хорошие и плохие может осуществляться рекурсивно с помощью следующих трех правил:

(0,0) — плохая позиция (проигрыш).
Любая позиция, из которой плохая позиция может быть достигнута одним ходом — хорошая позиция.
Позиция, каждый ход из которой ведёт к хорошей позиции — плохая позиция.

Например, все позиции вида (0, m) и (m, m) при m > 0 — хорошие (по правилу 2). При этом позиция (1,2) является плохой, поскольку из неё можно попасть только в позиции (0,1), (0,2), и (1,1), а они все хорошие, как указывалось в предыдущем предложении. Первые несколько плохих позиций (n, m) с наименьшими значениями n и m — это (0, 0), (1, 2), (3, 5), (4, 7), (6,10) и (8, 13).

Формула для плохих позиций

Витхофф доказал, что плохие позиции следуют схеме, определяемой золотым сечением. В частности, если k — произвольное натуральное число, и

n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}

m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil =n_{k}+k

,

где φ — золотое сечение, то (n_k, m_k) — k-я плохая позиция. Эти две последовательности называются нижней и верхней последовательностями Витхоффа и имеют в Энциклопедии Целочисленных последовательностей номера A000201 и A001950 соответственно.

Две последовательности n_k и m_k являются последовательностями Битти, связанными с уравнением

{\frac {1}{\phi }}+{\frac {1}{\phi ^{2}}}=1\,.

Эти две последовательности являются взаимодополняющими: каждое положительное целое число появляется ровно один раз в любой последовательности.

См. также

Ним
Игра Гранди
Вычитание квадратов
Таблица Витхоффа

Примечания

↑ Николай Николаевич Воробьев. Числа Фибоначчи. М.:Наука, 1978
↑ Матулис А., Савукинас А., Ферзя - в угол, "цзяньшицзы" и числа Фибоначчи, Квант, 1984
↑ Wythoff’s game at Cut-the-knot Архивная копия от 9 февраля 2021 на Wayback Machine, quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers

Ссылки

Weisstein, Eric W. Wythoff's Game (англ.) на сайте Wolfram MathWorld.

[1] Николай Николаевич Воробьев. Числа Фибоначчи. М.:Наука, 1978

[2] Матулис А., Савукинас А., Ферзя - в угол, "цзяньшицзы" и числа Фибоначчи, Квант, 1984

[3] Wythoff’s game at Cut-the-knot Архивная копия от 9 февраля 2021 на Wayback Machine, quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers

[1]

[2]

[3]