Ним в поддавки

Материал из Algocode wiki
Версия от 11:29, 14 мая 2022; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

Дан ним($n$ кучек размера $a_{1} \dots a_{n}$, ход - взятие камней из кучки), выигрывает игрок, который не может сделать ход.

Решение

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

Другая позиция, в которой исход игры предрешён и не зависит от воли игроков -- ситуация, когда все кучки имеют размер $1$. В этом случае исход игры зависит от чётности количества кучек, а именно, если кучек нечётное количество, то позиция проигрышная, а если же чётное -- то выигрышная.

Вооружившись этими фактами можно доказать, что в ниме в поддавки во всех ситуациях, кроме описанных выше, выигрышность позиции совпадает с выигрышностью позиции в обычном Ниме -- позиция выигрышна тогда и только тогда, когда XOR-сумма размеров кучек не равна нулю. Более того, игроку, который хочет выиграть, надо делать те же ходы, что и в обычном Ниме, но за одним исключением: если после хода игрока на поле останутся только кучки размера $1$, то ему надо своим ходом сделать так, чтобы их количество стало нечётным.

Для того, чтобы доказать выигрышность такой стратегии, надо показать, что у выигрывающего игрока всегда будет возможность сделать описанный ход. Для этого достаточно показать, что при новых правилах игры у проигрывающего, который всё время находится в позиции, когда XOR-сумма равна нулю и есть хотя бы одна кучка размером больше 1, нет возможности за один ход получить позицию, где все размеры кучек равны $1$. Действительно, пусть $a_1 \xor \ldots \xor a_n = 0$ и без ограничения общности $a_1 > 1$. Тогда, в битовой записи $a_1$ есть старший бит соответствующий хотя бы двойке, который при XOR-суммировании должен обратиться в ноль. Но для этого должно быть какое-то $a_i$, у которого этот же бит должен присутствовать, а значит $a_i$ должно быть больше 1.

Таким образом, проигрывающий игрок всегда находится в позиции с нулевой XOR-суммой и хотя бы двумя кучками размера больше $1$, а значит в позицию, когда все кучки имеют размер $1$ он никак прийти не может.



Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex