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

Решение:

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

Ходы: $s\to s+1$ и $s\to 2s$. Выиграть одним ходом можно, если $s+1\ge301$ (то есть $s\ge300$) или если $2s\ge301$ (то есть $s\ge150{,}5$, а для целого $s$ — $s\ge151$). Итого одним ходом выигрывает тот, кто ходит из позиции $s\ge151$.

Нужно $S$, при котором Петя не выигрывает за один ход ($S\le150$), а обе позиции после его хода выигрышны для Вани: $S+1\ge151$ и $2S\ge151$, то есть $S\ge150$ и $S\ge76$. Единственное подходящее значение — $S=150$.

Проверка: из 150 получаются позиции 151 и 300. Из 151 Ваня удваивает: $302\ge301$; из 300 добавляет камень: $301\ge301$. Сам Петя выиграть сразу не мог: $151\lt301$ и $300\lt301$.

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

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

Ответ: 150