Решение: Стратегия в игре с кучей
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 66. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой находится 66 или больше камней.
В начальный момент в куче было $S$ камней, $1 \leq S \leq 65$. Укажите минимальное значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение по шагам
3 шагаПетя не должен иметь возможности выиграть одним ходом. Для этого после начального количества камней должно быть меньше 33 камней, поскольку при $S\geq 33$ Петя сможет удвоить кучу и получить не менее 66 камней.
$$S<33$$После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. Если после хода Пети в куче не менее 33 камней, Ваня удваивает их количество и получает не менее 66 камней.
$$S+1\geq 33,\quad 2S\geq 33$$Из условия $S+1\geq 33$ получаем $S\geq 32$. Условие $2S\geq 33$ даёт $S\geq 17$. С учётом условия $S<33$ минимальное значение — 32.
$$S=32$$Где здесь ошибаются
Проверяют только ход с удвоением и не учитывают добавление одного камня.
Ошибочно требуют, чтобы после каждого хода Пети сразу было не менее 66 камней.
Забывают, что Петя сам не должен выигрывать первым ходом.