WikiDer > Игра Wythoffs - Википедия

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

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

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

Мартин Гарднер в его марте 1977 г. "Колонка "Математические игры"" в Scientific American утверждает, что в игру играли в Китае под названием 捡 石子 jin shízǐ («собирать камни»).^[1] Голландский математик W. A. ​​Wythoff опубликовал математический анализ игры в 1907 году.^[2]

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

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

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

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

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

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

За мерзкая игра в этой игре (0, 1) и (2, 2) - холодные позиции, а позиция (п, м) с м, п > 2 холодно тогда и только тогда, когда (п, м) в обычной игре холодно.

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

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

${ Displaystyle п_ {к} = 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 ,}$

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

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

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

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

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

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

Рекомендации

внешняя ссылка

• Вайсштейн, Эрик В. "Игра Уайтхоффа". MathWorld.
• Грайм, Джеймс. "Игра Уайтхоффа (домой)" (видео). YouTube. Брэди Харан. Получено 21 августа 2017.