Шешімі: Игра с кучей камней
Құжат тапсырмағаИнструкция к заданиям
Прочитайте текст и выполните тапсырмалар.
Два игрока, Петя и Ваня, играют в игру с кучей камней. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается, когда количество камней становится не менее 133. В начальный момент в куче было $S$ камней, $1 \leq S \leq 132$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Шешім по шагам
3 қадамПетя не должен иметь возможности выиграть первым ходом. Поэтому должны выполняться неравенства $S+1<133$ и $2S<133$, откуда $S\leq 66$.
Чтобы Ваня мог выиграть после любого хода Пети, обе возможные позиции после хода Пети должны позволять Ване завершить игру. При ходе «добавить один камень» необходимо $S+1\geq 67$, поэтому $S\geq 66$.
При $S=66$ Петя может получить $67$ или $132$. Из $67$ Ваня удваивает количество камней: $67\cdot 2=134$. Из $132$ Ваня добавляет один камень: $132+1=133$.
Где здесь ошибаются
Считать, что при $S=66$ Петя выигрывает удвоением: $2\cdot 66=132<133$.
Проверять только один возможный ход Пети.
Забывать, что Ваня может выбрать разные ходы для позиций $67$ и $132$.