Русская Википедия:Ним Витхоффа
Ним Витхоффа, или игра Витхоффа, — стратегическая математическая игра для двоих игроков с двумя кучками фишек. Игроки по очереди берут фишки из одной или обеих кучек; в последнем случае из обеих кучек берется поровну фишек. Выигрывает тот, кто забирает последнюю или последние фишки.
Мартин Гарднер в книге «От мозаик Пенроуза к надежным шифрам» (глава 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 — произвольное натуральное число, и
- <math>n_k = \lfloor k \phi \rfloor = \lfloor m_k \phi \rfloor -m_k</math>
- <math>m_k = \lfloor k \phi^2 \rfloor = \lceil n_k \phi \rceil = n_k + k</math>,
где φ — золотое сечение, то (nk, mk) — k-я плохая позиция. Эти две последовательности называются нижней и верхней последовательностями Витхоффа и имеют в Энциклопедии Целочисленных последовательностей номера Файл:OEISicon light.svg A000201 и Файл:OEISicon light.svg A001950 соответственно.
Две последовательности nk и mk являются последовательностями Битти, связанными с уравнением
- <math>\frac{1}{\phi} + \frac{1}{\phi^2} = 1 \,.</math>
Эти две последовательности являются взаимодополняющими: каждое положительное целое число появляется ровно один раз в любой последовательности.
См. также
- Ним
- Игра Гранди
- Вычитание квадратов
- Таблица Витхоффа
References
Ссылки
- ↑ Николай Николаевич Воробьев. Числа Фибоначчи. М.:Наука, 1978
- ↑ Матулис А., Савукинас А., Ферзя - в угол, "цзяньшицзы" и числа Фибоначчи, Квант, 1984
- ↑ Wythoff’s game at Cut-the-knot Шаблон:Wayback, quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers
