Игра «Куча камней»

Автор темы koh 
ОбъявленияПоследний пост
ОбъявлениеМатематик-алгоритмист (Vehicle Routing Problem) – удаленная работа03.06.2020 17:58
ОбъявлениеМатематики, программисты, репетиторов (платформа SapioX)28.01.2021 12:47
ОбъявлениеАктуарий в PPF Life Insurance (Junior)25.03.2021 21:35
03.03.2021 23:29
Игра «Куча камней»
Условие

Имеется куча из нескольких камней.
Два игрока по очереди берут из неё камни, пропускать ход нельзя.
За один ход можно забрать из кучи не менее одного и не более половины камней, имеющихся в ней к моменту совершения хода.
Проигрывает тот, кто не может сделать ход.
Кто выигрывает при правильной игре?


Рассмотрите количество камней, равное $2^N – 1$




Ответ: При количестве камней, равном $2^N – 1$ выигрывает второй, в остальных случаях – первый.
Пусть текущее количество камней $К$ удовлетворяет условию $2^N - 1 < К < 2^{N+1} – 1$.
Тогда первый, взяв не больше половины камней, сможет оставить второму $2^N - 1$ камней.
После ответного хода второго возникнет аналогичная ситуация $2^N - 1 < К < 2^{N+1} – 1$.
Придерживаясь такой стратегии, первый сможет в конечном счете оставить второму один камень, что является поражением для второго.
Если же исходное количество камней равно $2^N – 1$, то такой стратегии сможет придерживаться второй.




Редактировалось 1 раз(а). Последний 04.03.2021 01:32.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти