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

Решение:

Из кучи в $S$ камней ход «добавить камень» даёт $S+1$, ход «удвоить» даёт $2S$. Так как $2S \ge S+1$ при любом $S \ge 1$, выиграть одним ходом можно тогда и только тогда, когда $2S \ge 153$, то есть при $S \ge 77$.

Поэтому условие «Петя не может выиграть за один ход» означает $S \le 76$.

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

• после хода «+1» получается $S+1$, нужно $S+1 \ge 77$, то есть $S \ge 76$;
• после хода «×2» получается $2S$, нужно $2S \ge 77$, то есть $S \ge 39$.

Вместе с $S \le 76$ остаётся единственное значение $S = 76$.

Проверка: из кучи в 76 камней Петя получает 77 или 152 камней — до 153 не хватает ни в одном случае. Из 77 камней Ваня удваивает и получает 154 камней, из 152 камней Ваня добавляет один камень и получает 153 камней. И то и другое не меньше 153, значит Ваня выигрывает своим первым ходом при любом ходе Пети.

Тот же ответ даёт перебор:

N = 153

def moves(s):
    return [s + 1, 2 * s]

def win1(s):                      # ходящий выигрывает первым же ходом
    return any(t >= N for t in moves(s))

for s in range(1, N):
    # сам выиграть не может, но любой его ход отдаёт победу сопернику
    if not win1(s) and all(win1(t) for t in moves(s)):
        print(s)                  # 76

Ответ: 76