Как искать закономерность

В олимпиадной задаче про игру редко просят доказательство. Просят число при $n \le 10^{18}$ — а значит нужна формула. Стандартный путь такой.

1. Написать честный перебор с запоминанием и напечатать значения Гранди для $x = 0, 1, \dots, 100$.
2. Посмотреть на строку и угадать.
3. Проверить гипотезу перебором на больших значениях.
4. Написать решение по формуле.

Третий шаг пропускать нельзя: угаданное на сотне значений регулярно ломается на тысяче.

Что обычно оказывается

Период. Для игры вычитания — когда из кучи разрешено брать элемент фиксированного множества $S$ — последовательность Гранди всегда периодична, потому что значение зависит только от $\max S$ предыдущих. Периоды, посчитанные перебором до 20 000:

множество $S$	Гранди для $x = 0 \ldots 15$	период
$\{1, 2, 3\}$	0123012301230123	4
$\{2, 3\}$	0011200112001120	5
$\{1, 3, 4\}$	0101232010123201	7
$\{1, 4, 5\}$	0101232301012323	8
$\{3, 5, 7\}$	0001112223000111	10
$\{1, 5, 6\}$	0101012323201010	11
$\{2, 5, 7\}$	0011021322031001	22

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

Заметьте, что период не выражается через $\max S$ просто: у $\{3,5,7\}$ он 10, а у $\{2,5,7\}$ — 22. Поэтому его не выводят, а измеряют.

Рекуррентная формула. Игра «разрезать кусок длины $x$ на две части и оставить бо́льшую», то есть переход в любое $y$ с $\lceil x/2 \rceil \le y \le x - 1$, даёт последовательность

$$0,\ 1,\ 0,\ 2,\ 1,\ 3,\ 0,\ 4,\ 2,\ 5,\ 1,\ 6,\ 3,\ 7,\ 0,\ 8,\ \ldots$$

Здесь виден не период, а рекуррентность: значения на чётных местах — просто половина номера, а на нечётных повторяют начало последовательности.

$$G(2k) = k, \qquad G(2k+1) = G(k), \qquad G(1) = 0.$$

Сверено с перебором для всех $x \le 20\,000$ — совпадает.

Как искать период программой

Посчитайте значения до какого-нибудь запаса (скажем, до 20 000) и переберите пары (начало, длина), проверяя совпадение до конца массива.

Единственная ловушка: период надо подтверждать на длинном хвосте. Если разрешить периоду начинаться у самого конца массива, найдётся мусорное совпадение на двух-трёх элементах. При первой попытке посчитать таблицу выше у множества $\{1, 5, 6\}$ так и получилось: слабая проверка выдала «период 2 с позиции 396», а настоящий ответ — период 11 с самого начала.

Требуйте, чтобы найденный период держался хотя бы на четверти массива.

Когда закономерности нет

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

Смежное

• Функция Гранди;
• Ним.