Задание 20

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

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

Теория

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

Решение

В задании 19 при S=64 перед первым ходом Пети, Ваня выигрывает своим ответным первым ходом. Очевидно, что если перед первым ответным ходом Вани в куче станет 64 камня, то Петя выиграет своим вторым ходом. Получить 64 камня можно двумя способами: S+1=64 или S*2=64. Значит два начальных значения S равны 32 и 63. Не забудьте записать их в порядке возрастания!

Для любителей программировать:

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

Ответ

32 и 63 (Время не более 2 минут)