Ним в поддавки: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «==Задача== Дан ним($n$ кучек размера $a_{1} \dots a_{n}$, ход - взятие камней из кучки), выигрывает иг...»)
 
 
Строка 3: Строка 3:
 
Дан ним($n$ кучек размера $a_{1} \dots a_{n}$, ход - взятие камней из кучки), выигрывает игрок, который не может сделать ход.
 
Дан ним($n$ кучек размера $a_{1} \dots a_{n}$, ход - взятие камней из кучки), выигрывает игрок, который не может сделать ход.
  
==Подсказка==
+
==Решение==
  
Пусть вам дана выигрышная стратегия в ним, можете ли вы ее как-нибудь применить к ниму в поддавки.
+
Если в игре только одна кучка, то в есть ровно одна проигрышная позиция -- когда мы начинаем с одним камнем. Во всех остальных случаях мы можем сделать ход так, чтобы остался один камень, после чего наш оппонент проиграет.
  
==Решение==
+
Другая позиция, в которой исход игры предрешён и не зависит от воли игроков -- ситуация, когда все кучки имеют размер $1$. В этом случае исход игры зависит от чётности количества кучек, а именно, если кучек нечётное количество, то позиция проигрышная, а если же чётное -- то выигрышная.
 +
 
 +
Вооружившись этими фактами можно доказать, что в ниме в поддавки во всех ситуациях, кроме описанных выше, выигрышность позиции совпадает с выигрышностью позиции в обычном Ниме -- позиция выигрышна тогда и только тогда, когда XOR-сумма размеров кучек не равна нулю. Более того, игроку, который хочет выиграть, надо делать те же ходы, что и в обычном Ниме, но за одним исключением: если после хода игрока на поле останутся только кучки размера $1$, то ему надо своим ходом сделать так, чтобы их количество стало нечётным.
  
Отдельно рассмотрим случай, где все кучки - размера 1, в таком ниме ответ обратен ниму в поддавки, так как единственный возможный ход - взять всю кучку и кто выигрывает зависит только от четности количества кучек.
+
Для того, чтобы доказать выигрышность такой стратегии, надо показать, что у выигрывающего игрока всегда будет возможность сделать описанный ход. Для этого достаточно показать, что при новых правилах игры у проигрывающего, который всё время находится в позиции, когда XOR-сумма равна нулю и есть хотя бы одна кучка размером больше 1, нет возможности за один ход получить позицию, где все размеры кучек равны $1$. Действительно, пусть $a_1 \xor \ldots \xor a_n = 0$ и без ограничения общности $a_1 > 1$. Тогда, в битовой записи $a_1$ есть старший бит соответствующий хотя бы двойке, который при XOR-суммировании должен обратиться в ноль. Но для этого должно быть какое-то $a_i$, у которого этот же бит должен присутствовать, а значит $a_i$ должно быть больше 1.
  
Заметим, что в ниме в поддавки игра заканчивается на том, что остается кучка размера 1, заметим, что существует оптимальная стратегия Нима, где в конце мы получили сколько-то кучек размера 1, тогда вернемся к последнему ходу, который привел нас к тому, что остались только кучки размера 1(так как мы рассмотрели отдельно случай, когда все кучки из одного камушка, то такой ход был). Сделаем теперь ход не до кучки размера 1, а до кучки размера 0, так как мы поменяли четность количества кучек размера 1, то мы и поменяли игрока, который выигрывает, а следовательно мы научились выигрывать в ниме с поддавками, если мы умеем выигрывать в обычном ниме.
+
Таким образом, проигрывающий игрок всегда находится в позиции с нулевой XOR-суммой и хотя бы двумя кучками размера больше $1$, а значит в позицию, когда все кучки имеют размер $1$ он никак прийти не может.
  
{{Автор|Глеб Лобанов|glebodin}}
+
{{Автор|Александр Гришутин|rationalex}}

Текущая версия на 11:29, 14 мая 2022

Задача

Дан ним($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