Ним и его родственники

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

Значение Гранди кучи из $x$ камней равно $x$: из неё достижимы кучи $0, \dots, x - 1$, и $\mathrm{mex}$ такого множества равен $x$. По теореме о сумме позиция проигрышна ровно тогда, когда

$$x_1 \oplus x_2 \oplus \ldots \oplus x_k = 0.$$

Выигрышный ход

Пусть $S \ne 0$. Берём кучу, у которой установлен старший бит $S$ (такая обязательно есть), и уменьшаем её до $x \oplus S$:

for (int i = 0; i < k; i++)
    if ((pile[i] ^ S) < pile[i]) {
        std::cout << pile[i] << " " << (pile[i] ^ S);   // из чего и во что
        break;
    }

Выигрышных ходов может быть несколько — столько, сколько куч содержат старший бит $S$.

Ограничение на ход

Если из кучи разрешено брать не больше $k$ камней, значение Гранди становится $x \bmod (k + 1)$: достижимы значения предыдущих $k$ остатков, и $\mathrm{mex}$ даёт следующий. Проверено перебором для всех $k \le 8$ и $x \le 400$ — расхождений нет.

Отсюда правило для одной кучи: проигрышны ровно позиции, кратные $k + 1$. Стратегия — каждым ходом дополнять взятое соперником до $k + 1$.

Мизерный ним

Здесь проигрывает тот, кто взял последний камень. Ответ отличается от обычного нима только в вырожденном случае:

• если есть хотя бы одна куча из двух и более камней — как в обычном ниме: выигрывает первый при $\text{XOR} \ne 0$;
• если все кучи по одному камню — выигрывает первый ровно тогда, когда таких куч чётное число.

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

Содержательная причина в том, что пока есть большая куча, ведущий может выбирать, оставить ли чётное число единиц, — и разница между обычной и мизерной игрой откладывается до самого конца.

Лестничный ним

Кучи стоят на ступеньках $1, 2, \dots, n$. Ход — переложить любое число камней со ступеньки $i$ на ступеньку $i - 1$; со ступеньки 1 камни уходят на пол и в игре больше не участвуют.

Ответ: XOR куч на нечётных ступеньках. Камни на чётных ступеньках не считаются вовсе.

Идея: камни на нечётных ступеньках ведут себя как обычный ним, а всё, что соперник кладёт на чётную ступеньку, можно тут же переложить дальше — это ход-ответ, который восстанавливает положение. Формула сверена с перебором на всех наборах до четырёх ступенек с кучами до трёх камней.

Приём узнаётся по формулировке «двигаем к краю, у края объекты исчезают» — например, фишки на полосе, которые толкают влево.

Смежное

• Сумма игр;
• Игра Уайтхоффа — две кучи, но ходить можно и в обеих сразу.