Задание №20 — Теория игр

#69575Задание №20ФИПИ

Теория игр

Условие игры

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

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

Правильный ответ

40 79

Пояснение

Решение:

Напомним игру: в куче $S$ камней, своим ходом игрок либо добавляет в кучу один камень, либо удваивает её; выигрывает тот, после чьего хода в куче окажется не менее 161 камней.

Так как $2S \ge S+1$ , игрок выигрывает одним ходом тогда и только тогда, когда $2S \ge 161$ , то есть при $S \ge 81$ .

Найдём проигрышную позицию — такую кучу, из которой ходящий сам выиграть не может, но любой его ход отдаёт победу сопернику. Оба хода должны попадать в зону $\ge 81$ ; слабее ход «+1», он требует $S+1 \ge 81$ , то есть $S \ge 80$ . Вместе с $S \le 80$ (иначе игрок выиграл бы сам) получаем единственную такую кучу: 80 камней. Действительно, из 80 камней получаются 81 и 160 камней — до 161 не хватает; зато из 81 камней соперник удваивает и получает 162, а из 160 камней добавляет камень и получает 161.

Значит Петя должен своим первым ходом получить ровно 80 камней:

ходом «+1»: $S+1 = 80$ , то есть $S = 79$ ;
ходом «×2»: $2S = 80$ , то есть $S = 40$ .

Оба значения меньше 81, так что за один ход Петя действительно не выигрывает, а после его хода в позицию «80 камней» Ваня вынужден отдать победу: как бы он ни сходил, Петя следующим ходом добирает кучу до 161. Меньших подходящих значений нет: из кучи, где меньше 40 камней, позицию «80 камней» одним ходом не получить.

Проверка перебором:

N = 161

def moves(s):
    return [s + 1, 2 * s]

def win1(s):                      # выигрыш первым же ходом
    return any(t >= N for t in moves(s))

def lose1(s):                     # ходящий проигрывает: любой его ход даёт сопернику победу
    return not win1(s) and all(win1(t) for t in moves(s))

def win2(s):                      # первым ходом не выигрывает, вторым — выигрывает
    return not win1(s) and any(lose1(t) for t in moves(s))

print([s for s in range(1, N) if win2(s)][:2])   # [40, 79]

Ответ: 40 79