Имеется куча из нескольких камней. Два игрока по очереди берут из неё камни, пропускать ход нельзя. За один ход можно забрать из кучи не менее одного и не более половины камней, имеющихся в ней к моменту совершения хода. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Рассмотрите количество камней, равное $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.
