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

Решение:

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

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

Нужно $S\le26$ (Петя не выигрывает сразу) и одновременно $S+1\ge27$, $S+5\ge27$, $4S\ge27$, то есть $S\ge26$, $S\ge22$ и $S\ge7$. Единственное значение — $S=26$.

Проверка: из 26 Петя получает 27, 31 или 104 — все не меньше 27, поэтому Ваня выигрывает своим первым ходом. Сам Петя выиграть сразу не мог: $27\lt105$, $31\lt105$, $104\lt105$.

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

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

Ответ: 26