WikiSort.ru - Не сортированное

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

Пример

Игра в поддавки, которая начинается с одной кучки из 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)

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

См. также

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

Литература

Ссылки

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