Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в три раза. Для тoгo чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится нe менее 88. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, состоящую из 88 или более камней. В начальный момент в куче было S камней; 1 < S < 87. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите такое значение S, при котором Петя He может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом
Для решения этой задачи давайте разберем условия игры по шагам.
Условия игры:
- Петя и Ваня по очереди добавляют камни в кучу.
- Каждый игрок может сделать один из трех ходов:
- Добавить 1 камень
- Добавить 4 камня
- Увеличить количество камней в трое (умножить на 3)
- Игра заканчивается, когда в куче 88 или более камней.
- Победителем считается игрок, который сделал последний ход.
Цель:
Мы ищем такое начальное значение S (количество камней в куче в начале), при котором Петя не может выиграть за один ход, но Ваня может гарантированно выиграть на своем первом ходе, при ответах на любые действия Пети.
Анализ и стратегия:
Состояние выигрыша и проигрыша:
- Если у игрока есть возможность сделать ход, который приводит к состоянию, в котором противник не сможет победить (или может быть в проигрышной позиции), значит, это состояние выигрышное для текущего игрока.
Выигрышные и проигрышные позиции:
- Мы считаем выигрышной позицией такое количество камней, при котором текущий игрок может обеспечить выигрыш вне зависимости от противника.
- Противоположностью выигрышной позиции будет проигрышная, когда любой ход приводит к выигрышной позиции для противника.
Границы игры:
- Ваня может гарантированно победить, если после взятия камней он оставляет Петю в проигрышной позиции.
- Мы знаем, что количество камней в конце должно быть 88 или больше, вот возможные выигрышные позиции для Вани, начиная от 88 и ниже:
- 88 - выигрышная (Петя не может сделать ход)
- 87 - проигрышная (Петя добавляет 1, Ваня выигрывает 88)
- 86 - проигрышная (Петя добавляет 1, Ваня выигрывает 87, Петя добавляет 4, Ваня выиграет 90)
- 85 - проигрышная
- 84 - выигрышная
Теперь повторим процесс, начиная с 88:
- 87 -> проигрышная для Пети (Петя все равно приведет к выигрышной позиции Вани)
- 86 -> проигрышная для Вани (выигрышная для Пети)
- 85 -> проигрышная для Пети (выигрышная для Вани)
Возможные начальные позиции:
Теперь давайте подытожим:
- Если С = 84, это выигрышная позиция для Пети.
- Если С = 83, это проигрышная для Пети, так как он может только проиграть.
В результате:
- Когда S равно 83, Петя не может выиграть за один ход, и Ваня сможет выиграть на своем первом ходе.
Таким образом, начальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Вани он может выиграть, это S = 83.
