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

Материал из Algocode wiki
Версия от 16:21, 9 февраля 2020; Глеб (обсуждение | вклад) (Новая страница: «==Задача== Дан ним($n$ кучек размера $a_{1} \dots a_{n}$, ход - взятие камней из кучки), выигрывает иг...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

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

Подсказка

Пусть вам дана выигрышная стратегия в ним, можете ли вы ее как-нибудь применить к ниму в поддавки.

Решение

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

Заметим, что в ниме в поддавки игра заканчивается на том, что остается кучка размера 1, заметим, что существует оптимальная стратегия Нима, где в конце мы получили сколько-то кучек размера 1, тогда вернемся к последнему ходу, который привел нас к тому, что остались только кучки размера 1(так как мы рассмотрели отдельно случай, когда все кучки из одного камушка, то такой ход был). Сделаем теперь ход не до кучки размера 1, а до кучки размера 0, так как мы поменяли четность количества кучек размера 1, то мы и поменяли игрока, который выигрывает, а следовательно мы научились выигрывать в ниме с поддавками, если мы умеем выигрывать в обычном ниме.



Автор конспекта: Глеб Лобанов

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