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

Решение:

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

Ходы: $s\to s+1$ и $s\to 2s$. Выиграть одним ходом можно, если $s+1\ge229$ (то есть $s\ge228$) или если $2s\ge229$ (то есть $s\ge114{,}5$, а поскольку $s$ целое — $s\ge115$). Объединяя, одним ходом выигрывает тот, кто ходит из позиции $s\ge115$.

Нужно значение $S$, для которого одновременно выполняются два условия: Петя не выигрывает за один ход, то есть $S\le114$; и обе позиции после его хода выигрышны за один ход для Вани, то есть $S+1\ge115$ и $2S\ge115$. Из первого неравенства $S\ge114$, из второго $S\ge58$. Вместе с $S\le114$ остаётся единственное значение $S=114$.

Проверка: из позиции 114 Петя может получить только 115 или 228, и в обоих случаях Ваня заканчивает игру ($2\cdot115=230\ge229$ и $228+1=229\ge229$). Сам Петя выиграть сразу не мог: $114+1=115\lt229$ и $2\cdot114=228\lt229$.

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

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

Ответ: 114