Игра Гранди

Игра Гранди — стратегическая математическая игра для двух игроков. Сначала существует одна куча предметов. Два игрока по очереди разделяют любую из куч на две кучи разных размеров. Игра заканчивается, когда остаются только кучи из двух или одного предметов, т.к. ни одна не может быть разделена на кучи разных размеров. Выигрывает игрок, который сделал последний ход.

Пример

Игра, которая начинается с одной кучки из 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 должен разделить кучу из четырех предметов на 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 не может сделать ход и проигрывает.

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

Игра может быть проанализирована с помощью теории Шпрага-Гранди. Для этого нужно размерам куч в игре Гранди поставить в соответствие эквивалентные размеры куч в игре Ним. Это соответствие описывается последовательностью:

Размеры куч                 : 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...
Эквивалентные размеры Ним куч : 0  0  0  1  0  2  1  0  2  1  0  2  1  3  2  1  3  2  4  3  0 ... (последовательность A002188 в OEIS)

Используя это соответствие, стратегия для игры Ним может быть также использована и для игры Гранди. Вопрос, становится ли последовательность Ним-значений для игры Гранди периодичной, это нерешенная проблема. Элвин Берлекэмп, Джон Хортон Конвей и Ричард Гай предположили, что она периодична, несмотря на то, что первые 2³⁵ значений, найденные Achim Flammenkamp, этого не подтверждают.

См. также

• Ним (игра)
• Функция Шпрага-Гранди

Ссылки

• Weisstein, Eric W. Grundy's game (англ.) на сайте Wolfram MathWorld.
• A. Flammenkamp, Sprague-Grundy values for Grundy's Game