Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раз (количество камней, полученное при делении, округляется до меньшего);
Например, из кучи в 20 камней за один ход можно получить кучу из 5 или 15 или 17 камней.
Игра завершается, когда количество камней в куче становится не более 36. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 36 или менее камней. В начальный момент в куче было S камней, S ≥ 37.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
В ответе запишите целое число.
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раз (количество камней, полученное при делении, округляется до меньшего);
Например, из кучи в 20 камней за один ход можно получить кучу из 5 или 15 или 17 камней.
Игра завершается, когда количество камней в куче становится не более 36. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 36 или менее камней. В начальный момент в куче было S камней, S ≥ 37.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
В ответе запишите целое число.
Подсказка 1. Условие «вторым ходом»: Петя делает ход, после которого ЛЮБОЙ ответ Вани позволяет Пете завершить игру своим следующим ходом.
Подсказка 2. Сначала отметьте позиции победы за один ход, затем ищите позиции, из которых есть ход в такие позиции для Вани.
Подсказка 3. Два наименьших S: 151 152; проверьте, что для них Петя не может выиграть сразу.
Разбор.
Приём — классификация позиций. Выигрыш за один ход при пороге 36: S ≤ 39 (−3), S ≤ 41 (−5), S ≤ 147 (деление на 4, округление вниз). Теперь ищем S, из которых есть ход в позицию, где любой ответ Вани (−3, −5 или деление на 4) даёт выигрыш Пети за один ход. Два наименьших таких S: 151 152. Для них условие «не может выиграть за один ход» выполняется.
Ответ: 151 152.
Ответ.
151 152