Игра Grundys - Википедия - Grundys game

Стеки монет. Любую из этих стопок можно разделить на две стопки разного размера: после того, как крайняя левая стопка из трех будет разделена, ее больше нельзя будет разделить.

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

Иллюстрация

Обычная игра, начинающаяся с одной кучи из 8, является выигрышем для первого игрока при условии, что он начинает с разделения кучи на кучи из 7 и 1:

игрок 1: 8 → 7 + 1

У игрока 2 теперь есть три варианта: разделить кучу 7 на 6 + 1, 5 + 2 или 4 + 3. В каждом из этих случаев игрок 1 может гарантировать, что следующим ходом он вернет своему противнику кучу размер 4 плюс кучи размера 2 и меньше:

игрок 2: 7 + 1 → 6 + 1 + 1 игрок 2: 7 + 1 → 5 + 2 + 1 игрок 2: 7 + 1 → 4 + 3 + 1 игрок 1: 6 + 1 + 1 → 4 + 2 + 1 + 1 игрок 1: 5 + 2 + 1 → 4 + 1 + 2 + 1 игрок 1: 4 + 3 + 1 → 4 + 2 + 1 + 1

Теперь игрок 2 должен разделить кучу 4 на 3 + 1, а игрок 1 впоследствии разбивает кучу 3 на 2 + 1:

игрок 2: 4 + 2 + 1 + 1 → 3 + 1 + 2 + 1 + 1 игрок 1: 3 + 1 + 2 + 1 + 1 → 2 + 1 + 1 + 2 + 1 + 1 игрок 2 не имеет ходов и проигрывает

Математическая теория

Игру можно проанализировать с помощью Теорема Спрага – Гранди. Это требует, чтобы размеры кучи в игре были сопоставлены с эквивалентными размер кучи ним. Это отображение зафиксировано в Он-лайн энциклопедия целочисленных последовательностей в качестве OEIS: A002188:

Размер кучи: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... Эквивалентная куча Nim: 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ...

Используя это отображение, стратегия игры Ним также может использоваться для игры Гранди. Становится ли когда-либо последовательность ним-значений в игре Гранди периодической - нерешенная проблема. Элвин Берлекамп, Джон Хортон Конвей и Ричард Гай предположили[1] что последовательность со временем становится периодической, но, несмотря на вычисление первых двух35 значения по Ахим Фламменкамп, вопрос не решен.

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

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

  1. ^ Э. Берлекамп, Дж. Х. Конвей, Р. Гай. Выигрышные способы для ваших математических игр. Академическая пресса, 1982.

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