21.01 Теория игр

Аналитическое решение:

Сделаем у области жирные границы, скопируем ее в , , и . В ячейках будет старт, в ячейках столбцов — ходы , в столбцах — ходы , в — , в — . Напишем формулы в столбце (в остальных столбцах они уже написаны). Перебирая значения старта (ячейка ) видим ответ .

Программное решение:

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b <= 34:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1, b))
        moves.append(f(a // 2, b))
    if b > 0:
        moves.append(f(a, b - 1))
        moves.append(f(a, b // 2))
    pinki_win = [i for i in moves if i <= 0]
    if pinki_win:
        return -max(pinki_win) + 1
    else:
        return -max(moves)


for i in range(12, 100):
    if f(22, i) == -2:
        print(i)