Яндекс Учебник Петя и Ваня решили поиграть. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: • убрать из кучи два камня •…
Яндекс Учебник Петя и Ваня решили поиграть. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: • убрать из кучи два камня • убрать из кучи четыре камня • уменьшить количество камней в куче в два раза (с округлением в большую сторону) Например, из кучи в 39 камней за один ход можно получить кучу из 37, 35 или 20 камней. Игра завершается, когда количество камней в куче становится не более 35. Победителем считается игрок, который сделал последний ход, то есть в результате его действия в куче стало 35 камней или меньше. До начала игры в куче было S камней, S ≥ 36. У игрока выигрышная стратегия, если он может выиграть при любых ходах противника. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Чтобы решить эту задачу, нужно рассмотреть условия игры и выявить такие значения \( S \), при которых Петя не может выиграть за один ход, но Ваня может выиграть на следующем.
Условия хода
- Петя не может выиграть за один ход, если после его хода в куче остается больше 35 камней.
- Ваня может выиграть своим первым ходом, если после его хода в куче остается 35 или меньше камней.
Возможные ходы
- Убрать 2 камня
- Убрать 4 камня
- Уменьшить количество камней в два раза (с округлением в большую сторону)
Давайте посмотрим, какие состояния кучи \( S \) Петя может оставлять после своего хода. Если \( S \) численно больше некоторого значения, то Ваня своей первой стратегией всегда может выиграть.
Анализ:
- Для Вани, наличие стратегии выиграть после одного хода Пети:
Для любого хода, который сделает Петя, Ваня должен остаться в выигрышной позиции.
Петя может оставить в куче такие состояния:
- \( S - 2 \)
- \( S - 4 \)
- \( \left\lceil \frac{S}{2} \right\rceil \)
Минимальная выигрышная стратегия для Вани:
Чтобы Ваня гарантированно выиграл после одного хода Пети, Петя должен оставить ему такие варианты, чтобы он после своего хода мог оставить в куче 35 или меньше камней.
Рассмотрим пример:
Возьмем \( S = 43 \).
- Если Петя оставляет 41, 39, или 22 (варианты при \( S = 43 \)), то Ваня сможет выполнить выигрышный ход.
- Из 41: Ваня убирает 4 и оставляет 37.
- Из 39: Ваня убирает 4 и оставляет 35 (это завершает игру).
- Из 22: Ваня убирает 4 и оставляет 18 или уменьшает на деление.
Теперь попробуем найти минимальное значение \( S \), при котором Петя не выиграет за один ход, но Ваня выиграет на следующем:
- Проверяем \( S = 39 \):
- Ходы Пети: 37, 35, 20.
- Ваня может выиграть из 35 (игра завершена).
Мы видим, что \( S = 39 \) является наименьшим значением, при котором Петя не может выиграть за один ход, но Ваня выигрывает при любом ходе Пети.
Таким образом, минимальное значение \( S = 39 \), при котором Петя не может выиграть за один ход, но Ваня гарантированно выигрывает на следующем.
