12. Для игры, описанной ниже, два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: добавить один камень в кучу; увеличить количество камней в куче в 2 раза. Например, если в куче 3 камня, за один ход можно получить 4 или 6 камней. У каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 65. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет 65 или более камней. В начальный момент в куче было S камней, S ≤ 64. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Петя не может выиграть за один ход, если после любого из его ходов в куче останется меньше 65 камней. Для начального числа S это требует S + 1 < 65 и 2S < 65, то есть S ≤ 32.

Чтобы Ваня мог выиграть своим первым ходом при любом ходе Пети, после каждого хода Пети число камней должно быть не меньше 33: тогда удвоение даст не менее 66 камней. Наименьшее S, для которого это верно, удовлетворяет S + 1 ≥ 33 и 2S ≥ 33. Получаем S ≥ 32.

Следовательно, минимальное подходящее значение — S = 32. После хода Пети в куче будет либо 33 камня, либо 64 камня; Ваня удваивает число камней и выигрывает.

Ответ: 32.