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

Решение:

Нужно найти наименьшее $S$, для которого выполняются сразу два требования: Петя не выигрывает первым же ходом, а Ваня выигрывает своим первым ходом при любом ходе Пети.

Первое требование. Петя выигрывает сразу, если $S + 1 \ge 129$ или $2S \ge 129$. Значит, «не выиграть за один ход» означает $S + 1 \le 128$ и $2S \le 128$, то есть $S \le 64$.

Второе требование. Из кучи в $n$ камней игрок выигрывает одним ходом, если $n + 1 \ge 129$ или $2n \ge 129$; при $n \le 128$ это равносильно $n \ge 65$ (тогда удвоение сразу даёт не меньше 130). После хода Пети в куче окажется $S + 1$ или $2S$, и оба этих числа должны быть не меньше 65: $S + 1 \ge 65$ даёт $S \ge 64$, а $2S \ge 65$ даёт $S \ge 33$. Более сильное из них — $S \ge 64$.

Оба требования выполняются одновременно только при $S = 64$. Проверка: Петя из 64 может получить 65 или 128 — игра не кончается; из 65 Ваня удваивает и получает 130, из 128 добавляет камень и получает 129. В обоих случаях Ваня побеждает своим первым ходом.

def win_now(s):                     # можно ли выиграть одним ходом из s
    return s + 1 >= 129 or 2 * s >= 129

for s in range(1, 129):
    if not win_now(s) and all(win_now(m) for m in (s + 1, 2 * s)):
        print(s)                    # 64
        break

Ответ: 64