Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в пять раз. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 75 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 68. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 68 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 67. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, то есть не являющиеся выигрышными независимо от игры противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Чтобы разобраться в задаче, давайте внимательно проанализируем возможные ходы и выигрышные стратегии игроков. Для начала стоит отметить, что Петя и Ваня могут менее чем за 68 ходов увеличить количество камней в куче.
В начале игры у нас есть S камней (1 ≤ S ≤ 67). Чтобы победить, игрок должен довести количество камней до 68 или более, и при этом нужно учитывать, что у каждого игрока есть неограниченное количество камней для добавления.
Важно понять, какие позиции являются выигрышными для игрока. Мы можем проанализировать различные значения S и понять, какие позиции являются выигрышными для Пети и Вани.
- Позиции от 68 и более: Это выигрышные позиции для игрока, который делает ход, так как он выигрывает сразу.
- Позиции от 63 до 67: Если у Пети 63 камня, он может добавить 5 (68), что является выигрышным ходом. Это также верно для 64 (68), 65 (69 - тоже выигрыш), 66 (68) и 67 (68). Следовательно, эти позиции выигрышные для Пети.
- Позиции от 58 до 62: Если у Пети 58, он может добавить 4 (62) или 1 (59). 58 не является выигрышной для него, так как Ваня сможет после этого довести до выигрышной позиции для себя. То же самое касается 59 и 60, где Ваня сможет следовать к выигрышным позициям. Однако 61 и 62 - выигрышные позиции для Пети, так как он может добавить 4 или 6 и вывести в 65 или 68 соответственно.
- Позиции от 31 до 57: Здесь ситуация сложнее, но если Пете попасть на 31, он также может оставить Ване на 32 (все ходы остаются недостигнутыми выигрышными позициями), но из 32 он может всегда снова дойти до выигрышной позиции до 38, и далее.
Изучая промежутки, мы можем проводить быстрые диаграммы, на которых игроки продолжают входить в выигрышные позиции.
Теперь учитывая, что Ваня выиграл, после неудачного первого хода Пети, нам нужно найти минимальное значение S. Мы можем проверить значения:
- При S = 62, Петя не может выиграть и Ваня всегда может зайти в выигрышные позиции.
- При S = 66, например, Петя может добавить одну камень и потеряет.
- При S = 67, есть возможность продолжить делать выигрышные ходы.
Итак, минимальное значение S, когда Ваня выигрывает после неудачного первого хода Пети, равно 62.
