Условие:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки
ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или
увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно
получить кучу из 16 или 30 камней. Для того чтобы делать ходы, у каждого игрока есть неограничен-
1. Тип 19 Nº 28158
i
ное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 106. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 106 или больше камней.
В начальный момент в куче было S камней; 1 ≤ S ≤ 105.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите
минимальное значение S. когда такая ситуация возможна.