Решение: Выигрышная стратегия в игре
Документ к заданиюИнструкция к заданиям по информатике
Прочитайте текст и выполните задания.
Два игрока, Петя и Ваня, по очереди изменяют количество камней в куче. За один ход можно добавить один камень или увеличить количество камней в два раза. Игра заканчивается, когда в куче становится не менее 49 камней. В начальный момент в куче было $S$ камней, где $1 \leq S \leq 48$. Укажите такое значение $S$, при котором Петя не может выиграть за один ход, но после любого хода Пети Ваня может выиграть своим первым ходом.
Побеждает игрок, который первым получает кучу из 49 или более камней.
Решение по шагам
5 шаговИгрок может выиграть одним ходом из позиции с $n$ камнями, если после добавления одного камня или удвоения количество камней станет не менее 49.
$$n+1 \geq 49 \quad \text{или} \quad 2n \geq 49$$Минимальное целое значение $n$, из которого можно выиграть одним ходом, равно 25.
Петя не должен выигрывать своим первым ходом. Поэтому после любого его хода количество камней должно быть меньше 49: в частности, $S<25$, так как при $S\geq25$ Петя сразу может удвоить кучу.
После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. Петя может получить $S+1$ или $2S$, поэтому необходимо, чтобы обе позиции были не меньше 25.
$$S+1 \geq 25, \quad 2S \geq 25$$Из первого неравенства следует $S\geq24$, а из условия, что Петя не выигрывает первым ходом, следует $S\leq24$. Следовательно, $S=24$.
Где здесь ошибаются
Проверяют только ход с удвоением и не учитывают возможность добавить один камень.
Берут значение $S=25$, при котором Петя сам может выиграть первым ходом.
Не требуют, чтобы Ваня мог выиграть после каждого из двух возможных ходов Пети.