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

Решение:

Напомним условия игры: перед игроками две кучи камней, за ход можно добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в одной из куч вдвое; игра заканчивается, когда суммарное количество камней в кучах становится не менее $77$. Начальная позиция — $(7,\ S)$, первым ходит Петя.

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

$S = 31$. Сразу Петя выиграть не может ($7 + 2\cdot 31 = 69 \lt 77$). Петя удваивает первую кучу — получается позиция $(14,\ 31)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(15,\ 31)$ — Петя удваивает вторую кучу: $15 + 62 = 77$;
• $(14,\ 32)$ — Петя удваивает вторую кучу: $14 + 64 = 78$;
• $(28,\ 31)$ — Петя удваивает вторую кучу: $28 + 62 = 90$;
• $(14,\ 62)$ — Петя добавляет камень: $14 + 63 = 77$.

$S = 34$. Сразу Петя выиграть не может ($7 + 2\cdot 34 = 75 \lt 77$). Петя добавляет камень в первую кучу — получается позиция $(8,\ 34)$, игра не окончена. Теперь любой ход Вани проигрышный:

• $(9,\ 34)$ — Петя удваивает вторую кучу: $9 + 68 = 77$;
• $(8,\ 35)$ — Петя удваивает вторую кучу: $8 + 70 = 78$;
• $(16,\ 34)$ — Петя удваивает вторую кучу: $16 + 68 = 84$;
• $(8,\ 68)$ — Петя добавляет камень: $8 + 69 = 77$.

Полный перебор удобнее доверить программе:

N = 77

def moves(p):
    a, b = p
    return [(a + 1, b), (a, b + 1), (2 * a, b), (a, 2 * b)]

def over(p):                 # игра закончена
    return p[0] + p[1] >= N

def win1(p):                 # В1: выигрыш своим первым ходом
    return any(over(q) for q in moves(p))

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

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

print(*[s for s in range(1, 70) if win2((7, s))][:2])   # два наименьших