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

Решение:

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

Ходы: $s\to s+1$, $s\to s+4$ и $s\to 3s$. Игра заканчивается одним ходом, если $s+1\ge202$ ($s\ge201$), или $s+4\ge202$ ($s\ge198$), или $3s\ge202$ ($s\ge67\tfrac13$, для целого $s$ — $s\ge68$). Самое слабое условие даёт утроение, поэтому одним ходом выигрывает тот, кто ходит из позиции $s\ge68$.

Нужно $S\le67$ (Петя не выигрывает сразу) и одновременно $S+1\ge68$, $S+4\ge68$, $3S\ge68$, то есть $S\ge67$, $S\ge64$ и $S\ge23$. Остаётся $S=67$.

Проверка: из 67 Петя получает 68, 71 или 201 — все эти позиции не меньше 68, поэтому Ваня утроением (или прибавлением камней из 201) заканчивает игру. Сам Петя выиграть сразу не мог: $68\lt202$, $71\lt202$, $201\lt202$.

def win1(s):
    return s + 1 >= 202 or s + 4 >= 202 or 3 * s >= 202

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

Ответ: 67