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

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

1. После хода Пети количество камней должно оставаться больше 15, иначе Петя сразу выиграет.
S−3>15,S−7>15,⌊S/4⌋>15

2. Наиболее строгое условие задаёт деление на 4: результат должен быть не меньше 16.
⌊S/4⌋≥16⇒S≥64

3. При S=64 Петя может получить 61, 57 или 16 камней. Из 61 и 57 Ваня делит количество камней на 4 и получает соответственно 15 и 14 камней, а из 16 камней убирает 3 и получает 13 камней.

4. Следовательно, при любом ходе Пети Ваня выигрывает своим первым ходом, а значение S=64 является минимальным.