Ним Витхоффа

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

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

Визуализация нима Витхоффа

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

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

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

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

Например, все позиции вида (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\,.$

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

См. также

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

Ссылки

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