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

Решение:

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

Ходы: $s\to s+1$, $s\to s+5$ и $s\to 4s$. Игра заканчивается одним ходом, если $s+1\ge205$ ($s\ge204$), или $s+5\ge205$ ($s\ge200$), или $4s\ge205$ ($s\ge51{,}25$, для целого $s$ — $s\ge52$). Значит, из позиции $s\ge52$ ходящий выигрывает одним ходом.

Нужно $S\le51$ (Петя не выигрывает сразу) и одновременно $S+1\ge52$, $S+5\ge52$, $4S\ge52$, то есть $S\ge51$, $S\ge47$ и $S\ge13$. Остаётся $S=51$.

Проверка: из 51 Петя получает 52, 56 или 204 — все не меньше 52, поэтому Ваня заканчивает игру своим ходом. Сам Петя выиграть сразу не мог: $52\lt205$, $56\lt205$, $204\lt205$.

def win1(s):
    return s + 1 >= 205 or s + 5 >= 205 or 4 * s >= 205

for S in range(1, 205):
    if not win1(S) and win1(S + 1) and win1(S + 5) and win1(4 * S):
        print(S)

Ответ: 51