Игра Витхоффа

Математическая игра на вычитание для двух игроков

В игре Витхоффа используются две стопки фишек.

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

Эквивалентное описание игры таково: одна шахматная королева помещается где-то на большой сетке из клеток, и каждый игрок может переместить королеву в нижний левый угол сетки: на юг, запад или юго-запад, на любое количество шагов. Победителем становится игрок, который переместит королеву в угол. Две декартовы координаты королевы соответствуют размерам двух стопок в формулировке игры, включающей удаление фишек из стопок.

Мартин Гарднер в своей статье « Математические игры » в журнале Scientific American за март 1977 года утверждает, что в эту игру играли в Китае под названием 捡石子jiǎn shízǐ («выбор камней»). ^[1] Голландский математик У. А. Вайтхофф опубликовал математический анализ игры в 1907 году. ^[2]

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

Визуализация игры Витхоффа в Ним. Самый нижний левый квадрат — это позиция (1,1), а красные квадраты — это холодные позиции. Обратите внимание, что выигрышный квадрат не включен в изображение.

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

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

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

Например, все позиции вида (0, m ) и ( m , m ) с m  > 0 являются горячими, согласно правилу 2. Однако позиция (1,2) является холодной, поскольку единственные позиции, которые могут быть достигнуты из нее, (0,1), (0,2), (1,0) и (1,1), являются горячими. Холодные позиции ( n , m ) с наименьшими значениями n и m — это (0, 0), (1, 2), (3, 5), (4, 7), (6, 10) и (8, 13). (последовательность A066096 и A090909 в OEIS ) (Также см. OEIS : A072061 )

Для игры мизер этой игры (0, 1) и (2, 2) являются холодными позициями, а позиция ( n , m ) с m ,  n  > 2 является холодной тогда и только тогда, когда ( n , m ) в нормальной игре является холодной.

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

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

${\displaystyle n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\,}$

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

где φ — золотое сечение, и мы используем функцию пола , тогда ( n _k , m _k ) — k ^-я холодная позиция. Эти две последовательности чисел записаны в Онлайн-энциклопедии целочисленных последовательностей как OEIS : A000201 и OEIS : A001950 соответственно.

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

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

Как и в случае с парами последовательностей Битти, эти две последовательности являются дополнительными : каждое положительное целое число появляется ровно один раз в любой из последовательностей.

Смотрите также

• Ним
• Игра Гранди
• Вычесть квадрат
• Массив Вайтхоффа

Ссылки

1. Игра Витхоффа в Cut-the-knot, цитирующая книгу Мартина Гарднера «От плиток Пенроуза до шифров с секретом»
2. Витхофф, Вашингтон (1907), «Модификация игры в ним», Nieuw Archief voor Wiskunde , 7 (2): 199–202

Внешние ссылки

• Вайсштейн, Эрик В. «Игра Витхоффа». MathWorld .
• Грайм, Джеймс. "Wythoff's Game (Get Home)" (видео) . YouTube . Брэди Харан . Архивировано из оригинала 2021-12-15 . Получено 21 августа 2017 .