Шешімі: Выигрышная стратегия в игре
Два игрока по очереди изменяют количество камней в куче. За один ход игрок может добавить один камень или увеличить количество камней в куче в два раза. Игра заканчивается, когда в куче становится не менее 69 камней. Найдите минимальное начальное количество камней $S$, при котором Петя не может выиграть первым ходом, но после любого его хода Ваня может выиграть своим первым ходом.
В начальный момент $1 \leq S \leq 68$. Ответ — целое число.
Шешім по шагам
5 қадамИгрок может выиграть одним ходом из позиции $x$, если после добавления одного камня или удвоения количества камней получится не менее 69 камней.
$$x+1 \geq 69 \quad \text{или} \quad 2x \geq 69$$Минимальное целое значение $x$, из которого можно выиграть одним ходом, равно 35: при $x=35$ удвоение даёт 70 камней.
Чтобы Ваня мог выиграть после любого первого хода Пети, оба возможных результата хода Пети должны быть не меньше 35.
$$S+1 \geq 35, \quad 2S \geq 35$$Из первого неравенства получаем $S \geq 34$, а из второго — $S \geq 18$. Поэтому минимальное значение — $S=34$.
Петя не может выиграть первым ходом из позиции $S=34$, поскольку получает 35 или 68 камней, то есть меньше 69. После этого Ваня удваивает количество камней и выигрывает.
Где здесь ошибаются
Проверяют только ход Пети с удвоением, но забывают ход с добавлением бір камня.
Считают, что Ваня должен выиграть одним и тем же ходом в обоих случаях.
Берут значение $S=35$, хотя при $S=34$ Петя также не выигрывает первым ходом.