Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раз (количество камней, полученное при делении, округляется до меньшего);
Например, из кучи в 20 камней за один ход можно получить кучу из 5 или 15 или 17 камней.
Игра завершается, когда количество камней в куче становится не более 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 40 или менее камней. В начальный момент в куче было S камней, S ≥ 41.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
В ответе запишите целое число.
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раз (количество камней, полученное при делении, округляется до меньшего);
Например, из кучи в 20 камней за один ход можно получить кучу из 5 или 15 или 17 камней.
Игра завершается, когда количество камней в куче становится не более 40. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 40 или менее камней. В начальный момент в куче было S камней, S ≥ 41.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
В ответе запишите целое число.
Подсказка 1. Сначала найдите все позиции, из которых можно выиграть одним ходом: это числа, от которых отнимается 3 или 5 до порога либо деление на 4 даёт не больше порога.
Подсказка 2. Порог 40: выигрышными «за один ход» становятся все S ≤ 43, S ≤ 45 и кратные случаи S // 4 ≤ 40, то есть все числа до 163 включительно.
Подсказка 3. Для S = 164 ответы Пети: 161, 159, 41 — все они выигрышны для Вани; для S = 163 … проверьте, что это первая подходящая позиция.
Разбор.
Приём — классификация позиций снизу вверх. Выигрышной «за один ход» является любая позиция, из которой можно получить не более 40: S − 3 ≤ 40 → S ≤ 43; S − 5 ≤ 40 → S ≤ 45; S // 4 ≤ 40 → S ≤ 163. То есть все S ≤ 163 выигрышны для того, кто ходит. Для S = 164 ходы Пети дают 161, 159, 41 — каждое из этих чисел ≤ 163, значит Ваня выигрывает своим первым ходом. Условие «Петя не может выиграть за один ход» для 164 выполняется: 164 − 3 = 161, 164 − 5 = 159, 164 // 4 = 41 — всё больше 40. Ответ: 164.
Ответ.
164