Решение: Каменная куча и стратегия
Документ к заданиюИнструкция к заданиям
Прочитайте текст и выполните задания.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 145. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 145 или больше камней. В начальный момент в куче было $S$ камней, $1 \leq S \leq 144$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение по шагам
4 шагаЧтобы Петя не выиграл первым ходом, после его удвоения количество камней должно быть меньше 145:
$$2S < 145$$Если Петя добавит один камень, Ваня должен суметь выиграть удвоением:
$$2(S+1) \geq 145$$Если Петя удвоит количество камней, Ваня также должен суметь выиграть удвоением. Это условие слабее предыдущего для найденного значения $S$:
$$4S \geq 145$$Из неравенств $2S < 145$ и $2(S+1) \geq 145$ получаем $S \leq 72$ и $S \geq 72$. Следовательно, $S = 72$.
Где здесь ошибаются
Проверяют только ход Пети с удвоением и не рассматривают добавление одного камня.
Считают выигрышным значение $S=73$, хотя при нём Петя может сразу получить 146 камней.
Забывают, что Ваня должен иметь выигрышный ход после любого хода Пети.