Задание 21 ЕГЭ по информатике · F4D519

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Например, из кучи в 20 камней за один ход можно получить кучу из 17, 15 или 5 камней.
Игра завершается, когда количество камней в куче становится не более 10. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 10 или менее камней. В начальный момент в куче было S камней, S ≥ 11.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

1. Рассматриваем игру из задания 19 и строим дерево возможных ходов для разных значений параметра S.

2. Проверяем первое условие: после любого хода Пети у Вани должна быть стратегия, приводящая к победе не позднее второго хода.

3. Одновременно исключаем значения, при которых Ваня может гарантированно выиграть уже своим первым ходом.

4. Минимальное значение параметра, удовлетворяющее обоим условиям, равно 52.