Ним и функция Гранди

Есть класс игр, которые решаются полностью и одинаково: двое ходят по очереди, ходы обоих одинаковы, информация полная, случайности нет, проигрывает тот, кто не может сходить.

Для таких игр каждой позиции приписывают число — значение Гранди:

$$G(v) = \mathrm{mex}\{G(u) : u \text{ достижима из } v \text{ за один ход}\},$$

где $\mathrm{mex}$ — наименьшее неотрицательное число, которого нет в множестве.

Позиция проигрышная для того, кто ходит, тогда и только тогда, когда её значение равно нулю. Это прямо следует из определения: из нулевой позиции все ходы ведут в ненулевые, а из ненулевой есть ход в нулевую.

Сумма игр

Главная теорема (Шпрага — Гранди): если играют одновременно в несколько независимых игр и ход состоит в том, чтобы сходить в одной из них, то

$$G(\text{сумма}) = G_1 \oplus G_2 \oplus \ldots \oplus G_k.$$

Вот откуда в задачах про игры берётся исключающее «или».

Ним

В ниме есть кучи камней, ход — взять сколько угодно камней из одной кучи. Значение Гранди кучи из $x$ камней равно $x$: из неё достижимы кучи $0, \dots, x-1$, и $\mathrm{mex}$ этого множества равен $x$.

Значит, позиция из куч $x_1, \dots, x_k$ проигрышная ровно тогда, когда $x_1 \oplus \ldots \oplus x_k = 0$.

Для двух куч отсюда получается таблица, в которой на пересечении строки $x$ и столбца $y$ стоит $x \oplus y$. Проверено перебором: на всех $3600$ клетках при $x, y < 60$ значение $\mathrm{mex}$ по строке и столбцу совпало с $x \oplus y$ без единого исключения.

Эта же таблица встречается в задачах, где её описывают геометрически: «точке приписывается наименьшее число, отсутствующее в её строке и столбце». Ответ — $x \oplus y$.

Как решать задачу про игру

1. Проверить, что игра из нужного класса: ходы симметричны, случайности нет, проигрывает тот, кто не может сходить.
2. Разложить позицию на независимые части.
3. Посчитать значения Гранди для каждой части — обычно перебором на маленьких размерах.
4. Найти закономерность и проверить её перебором.
5. Ответ — XOR значений.

Четвёртый шаг — обычно самый содержательный. Значения Гранди почти всегда оказываются простой функцией вроде $x$, $x \bmod 3$ или количества единиц, но угадывается это по таблице, а не выводится.

Эта статья — короткое введение с точки зрения XOR. Подробный разбор — ретроанализ и ничьи, вычисление Гранди на графе позиций, варианты нима, игра Уайтхоффа, поиск закономерностей — в отдельном разделе «Теория игр».

Смежное

• Исключающее «или»;
• Сумма игр и теорема Шпрага — Гранди;
• Ним и его родственники;
• Рекурсия и перебор.