Шешімі: Выигрышная стратегия в игре
Құжат тапсырмағаИнструкция к заданиям по информатикаға
Прочитайте текст и выполните тапсырмалар.
Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу 1 или 4 камня либо увеличить количество камней в куче в 2 раза. Игра завершается, когда количество камней становится не менее 27. Побеждает игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, где $1 \leq S \leq 26$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Шешімін қадамдап көрсету
4 қадамПетя не должен иметь возможности выиграть первым ходом. Поэтому для начального значения $S$ должно выполняться $2S < 27$, а также $S+4 < 27$. Наиболее существенное ограничение даёт удвоение: $S \leq 13$.
$$2S < 27$$Ваня может выиграть одним ходом из позиции $x$, если удвоением получить не менее 27 камней. Это возможно при $x \geq 14$.
$$2x \geq 27 \Rightarrow x \geq 14$$Нужно, чтобы после любого хода Пети количество камней стало не менее 14. При $S=13$ Петя может получить $14$, $17$ или $26$ камней.
$$13+1=14,\quad 13+4=17,\quad 2\cdot13=26$$Из каждой из этих позиций Ваня удваивает количество камней и получает не менее 27 камней.
$$2\cdot14=28,\quad 2\cdot17=34,\quad 2\cdot26=52$$Где здесь ошибаются
Проверяют только один возможный ход Пети, а не все три.
Считают выигрышной позицию, из которой можно выиграть, хотя требуется выигрыш при любом ходе противника.
Забывают, что игра заканчивается сразу после получения не менее 27 камней.