20.01 Теория игр

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

Скопируем область и вставим ее в , , , . Это будут все возможные ситуации при разных первых ходах Пинки. Подпишем стобец как , как , как .

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

Осталось только перебрать значения в . При видим, что Пинки не может выиграть. При Пинки выигрывает вторым ходом, если первым делит вторую кучу на 2. Ответ .

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

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)