Игра Гранди

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