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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи 7 камней или уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится менее 117. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 116 или менее камней.

В начальный момент в куче было $S$ камней, $117 ≤ S ≤ 10 000$.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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