Ним в поддавки
Задача
Дан ним($n$ кучек размера $a_{1} \dots a_{n}$, ход - взятие камней из кучки), выигрывает игрок, который не может сделать ход.
Подсказка
Пусть вам дана выигрышная стратегия в ним, можете ли вы ее как-нибудь применить к ниму в поддавки.
Решение
Отдельно рассмотрим случай, где все кучки - размера 1, в таком ниме ответ обратен ниму в поддавки, так как единственный возможный ход - взять всю кучку и кто выигрывает зависит только от четности количества кучек.
Заметим, что в ниме в поддавки игра заканчивается на том, что остается кучка размера 1, заметим, что существует оптимальная стратегия Нима, где в конце мы получили сколько-то кучек размера 1, тогда вернемся к последнему ходу, который привел нас к тому, что остались только кучки размера 1(так как мы рассмотрели отдельно случай, когда все кучки из одного камушка, то такой ход был). Сделаем теперь ход не до кучки размера 1, а до кучки размера 0, так как мы поменяли четность количества кучек размера 1, то мы и поменяли игрока, который выигрывает, а следовательно мы научились выигрывать в ниме с поддавками, если мы умеем выигрывать в обычном ниме.
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin