Условие
Коля и Витя играют в следующую игру. На столе лежит куча из 31 камня. Мальчики
делают ходы поочерёдно, а начинает Коля. Делая ход, играющий делит каждую
кучку, в которой больше одного камня, на две меньшие кучки. Выигрывает тот, кто
после своего хода оставляет кучки по одному камню в каждой. Сможет ли Коля
сделать так, чтобы выиграть при любой игре Вити?
Решение
Ответ: нет.
Достаточно проследить за наибольшей кучкой. Пусть перед ходом игрока
A в
наибольшей кучке лежит 2
n - 1 камней. Тогда после его хода в наибольшей
кучке лежит от 2
n - 1 до 2
n - 2 камней. Поэтому игрок
B всегда
может добиться, чтобы в наибольшей кучке лежало 2
n - 1 - 1 камней. В таком
случае игрок
B выигрывает.
Итак, если число камней в исходной игре имеет вид 2
n - 1, то Витя сможет
выиграть. Если же число камней в исходной игре не равно 2
n - 1, то оно
заключено между 2
n и 2
n+1 - 2 для некоторого
n. В таком случае Коля
первым ходом добивается, чтобы число камней в наибольшей кучке было равно
2
n - 1. После этого он всегда может выиграть.
Источники и прецеденты использования
