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

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

Теория игр

Условие игры

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

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

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

70 73

Пояснение

Решение:

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

Самый «сильный» ход — умножение, поэтому выиграть одним ходом можно тогда и только тогда, когда $3S \ge 223$ , то есть при $S \ge 75$ (прибавление камней помогло бы лишь при $S \ge 219$ ).

Найдём проигрышную позицию — кучу, из которой ходящий сам не выигрывает, но любой его ход отдаёт победу сопернику. Слабейший ход «+1» тоже должен попадать в зону $\ge 75$ , поэтому $S \ge 74$ ; вместе с $S \le 74$ это даёт единственную кучу — 74 камней. Проверим её: из 74 камней получаются 75, 78 и 222 камней — все меньше 223, так что сам ходящий не выигрывает; но каждое из этих чисел не меньше 75, поэтому соперник следующим ходом доводит кучу до 223.

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

ходом «+1»: $S = 73$ ;
ходом «+4»: $S = 70$ ;
ход «×3» не подходит: 74 не делится на 3.

Оба значения меньше 75, то есть за один ход Петя не выигрывает; меньших подходящих значений нет.

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

N = 223

def moves(s):
    return [s + 1, s + 4, 3 * 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])   # [70, 73]

Ответ: 70 73