Решение: Выигрышная стратегия в игре
Два игрока, Петя и Ваня, играют в игру с кучей камней. Первый ход делает Петя. За один ход можно убрать из кучи 2 или 4 камня либо уменьшить количество камней в 3 раза, округлив результат деления вниз. Игра заканчивается, когда в куче становится не более 17 камней; победителем считается игрок, сделавший последний ход. В начальный момент в куче было $S$ камней, $S \ge 18$. Найдите минимальное значение $S$, при котором Петя не может выиграть за один ход, но после любого первого хода Пети Ваня может выиграть своим первым ходом.
Решение по шагам
4 шагаПетя выигрывает за один ход, если после одного из его ходов количество камней становится не более 17.
$$S-2 \le 17 \quad\text{или}\quad S-4 \le 17 \quad\text{или}\quad \left\lfloor\frac{S}{3}\right\rfloor \le 17$$Для третьего варианта условие выполняется при $S \le 53$. Поэтому при $S=54$ Петя уже не может выиграть за один ход: после его ходов остаётся $52$, $50$ или $18$ камней.
Из позиции $52$ Ваня делит количество камней на 3 и получает $\lfloor 52/3 \rfloor=17$. Из позиции $50$ он получает $\lfloor 50/3 \rfloor=16$, а из позиции $18$ убирает 2 камня и получает 16.
Следовательно, $S=54$ удовлетворяет условию. Все меньшие значения не подходят, так как при $S \le 53$ Петя может выиграть делением кучи на 3 за один ход.
Где здесь ошибаются
Забывают округление результата деления вниз.
Проверяют только один из возможных ходов Пети.
Считают достаточным, чтобы Ваня имел выигрышный ход только после одного варианта хода Пети.