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

Решение:

Позиция игры описывается одним числом $s$ — количеством камней в куче. Игрок, который ходит из позиции $s$, выигрывает своим ходом, если хотя бы один его ход сразу даёт кучу в 161 камней или больше.

Ходы: $s\to s+1$ и $s\to 2s$. Одним ходом игра заканчивается, если $s+1\ge161$ ($s\ge160$) или $2s\ge161$ ($s\ge80{,}5$, для целого $s$ — $s\ge81$). Итак, выигрывает одним ходом тот, кто ходит из позиции $s\ge81$.

Требуется $S\le80$ (Петя не выигрывает сразу) и одновременно $S+1\ge81$, $2S\ge81$, то есть $S\ge80$ и $S\ge41$. Остаётся $S=80$.

Проверка: из 80 Петя получает 81 или 160. Из 81 Ваня удваивает: $162\ge161$; из 160 добавляет камень: $161\ge161$. Сам Петя выиграть не мог: $81\lt161$ и $160\lt161$.

def win1(s):
    return s + 1 >= 161 or 2 * s >= 161

for S in range(1, 161):
    if not win1(S) and win1(S + 1) and win1(2 * S):
        print(S)

Ответ: 80