Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 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. Второе условие означает: после хода Пети Ваня не всегда может добить игру сразу — нужен хотя бы один «не сразу выигранный» ответ Пети.
Подсказка 2. Первое условие: из любой позиции после хода Пети Ваня либо выигрывает немедленно, либо выигрывает своим вторым ходом.
Подсказка 3. Минимальное S: 172; проверьте оба условия для всех ходов Пети из этой позиции.
Разбор.
Приём — классификация позиций по глубине стратегии. Из позиции S ходы Пети дают 169, 167, 43. Для Вани нужно: из каждой из этих позиций выиграть не позднее второго своего хода, и при этом хотя бы из одной позиции выиграть сразу нельзя (иначе выполнялось бы второе условие задачи). Проверка перебором снизу вверх даёт минимальное S = 172.
Ответ: 172.
Ответ.
172