Задание 21

В задании 19 два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 129 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 128.

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
 – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
 – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.

Теория

Данное задание на теорию игр - продолжение задания 19 и 20, когда нужно просчитать возможные стратегии хода игры и определить исходное значение (как правило количество камней). Задание решается аналитическим методом довольно быстро на основе результатов предыдущих двух задачи. Проанализируйте возможные варианты ходов и посчитайте все позиции после хода Пети (Первый игрок) и после хода Вани (Второй игрок). Для удобства можно нарисовать дерево игры. Данный вид задач ранее предполагал изображение на бланке ЕГЭ полного дерева игры, сейчас только ответ. Решение с помощью программы тоже возможно.

Решение

В задании 19 при S=64 перед первым ходом Пети, Ваня выигрывает своим ответным первым ходом. Очевидно, что если перед первым ответным ходом Вани в куче станет 64 камня, то Петя выиграет своим вторым ходом. Следовательно, если перед вторым ходом Пети в куче станет 64, то Ваня гарантированно выигрывает своим вторым ходом. Получить 64 камня можно двумя способами: S+1=64 или S*2=64. Значит два  значения S перед первым ходом Вани равны 32 и 63. Удобно изобразить дерево игры! Значение 63 можно получить только из 62, прибавив к нему 1. Это значит, что если в начале S=62, то Петя первым ходом может прибавить 1 и получить 63, тогда Ваня своим первым ответным ходом тоже добавит 1 и получит 64. Если Петя своим первым ходом сделает 62*2=124, то Ваня своим первым ходом сделает 124*2 и выиграет. Значит одно из чисел 62. Проверим число 32. Его можно получить из 31 (прибавив 1) или из 16 (умножив на 2). Но Петя своим первым ходом может выполнить 31*2=62 и выиграть вторым или третьим ходом. Аналогично для числа 16 Петя первым ходом может просто прибавить 1 и 16+1=17 и далее вторым своим ходом тоже добавить 1. Следовательно 31 и 16 не подходят и остается только 62.

Для любителей программировать (t=1 - первый ход Пети, t=2 - первый ход Вани, t=3 - второй ход Пети, а t=4 - второй ход Вани):

def move21(S, t):
    if (S+1>=129 or S*2>=129) and t==4:
        return True
    if (S+1<129 and S*2<129) and t%2==1:
            return move21(min(S+1,S*2),t+1)
    if (S+1<129 and S*2<129) and t==2:
            return move21(min(S+1,S*2),t+1)
for S in range(128, 0, -1):
    if move21(S, 1):
        print(S)

Ответ

62 (Время не более 10 минут)