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

Решение:

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

Позицию будем оценивать с точки зрения игрока, который ходит из неё. Обозначим: В1 — из позиции можно выиграть первым же ходом; П1 — любой ход не заканчивает игру и переводит соперника в В1 (то есть ходящий проигрывает следующим ходом соперника); В2 — позиция не В1, но есть ход, переводящий соперника в П1, то есть ходящий выигрывает ровно вторым своим ходом при любой игре соперника.

В1. Игру заканчивает ход $S+1 \ge 202$, $S+4 \ge 202$ или $3S \ge 202$; самое слабое условие — $3S \ge 202$, поэтому В1 — это все $S \ge 68$.

П1. Нужно $S \lt 68$, но чтобы каждый ход попадал в В1. Самое сильное требование даёт ход «добавить один камень»: $S+1 \ge 68$, то есть $S \ge 67$. Значит, единственная позиция П1 — это $S = 67$.

В2. Это позиции, из которых есть ход ровно в $67$: $S = 63$, $S = 66$.

Теперь про Ваню. Ваня выигрывает первым или вторым своим ходом при любой игре Пети, если каждый ход Пети приводит в позицию из В1 или В2 (и не заканчивает игру). Гарантированной победы первым ходом у Вани нет, если хотя бы один ход Пети ведёт не в В1, а в В2. Значит, нужно минимальное $S$, у которого все ходы попадают в $\text{В1} \cup \text{В2}$, но не все — в В1.

При $S = 62$ ходы Пети дают $63$ (В2), $66$ (В2), $186$ (В1) — условие выполнено. Меньших значений нет: наименьшая позиция из $\text{В1} \cup \text{В2}$ — это $63$, а ход «добавить один камень» переводит $S$ в $S+1$, поэтому обязательно $S \ge 62$.

Проверка программой:

N = 202

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

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

def lose1(s):                # П1: любой ход отдаёт победу сопернику
    return all(t < N and win1(t) for t in moves(s))

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

def lose2(s):                # Ваня выигрывает первым или вторым ходом,
    return (all(t < N and (win1(t) or win2(t)) for t in moves(s))
            and not lose1(s))          # но не гарантированно первым

print(min(s for s in range(1, N) if lose2(s)))