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

Автор темы koh 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
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.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

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