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

Решение:

Сначала опишем позиции, из которых игра заканчивается одним ходом. Из кучи в $n$ камней ($n \le 128$) ходящий выигрывает сразу, если $n + 1 \ge 129$ или $2n \ge 129$, то есть при $n \ge 65$. Значит, при $n$ от 65 до 128 ходящий побеждает немедленно.

Теперь найдём позицию, в которую Пете выгодно попасть после первого хода. Из кучи в 64 камня возможны только 65 и 128 — обе позиции выигрышны для соперника, поэтому 64 проигрышна для того, кто из неё ходит. Более того, 64 — единственная такая позиция: чтобы все ходы вели в диапазон 65–128, нужно $n + 1 \ge 65$, то есть $n \ge 64$, и одновременно $n \le 64$, иначе ходящий выиграл бы сам.

Итак, стратегия Пети — первым ходом получить ровно 64 камня, после чего Ваня вынужденно отдаёт позицию 65 или 128, и Петя добивает вторым ходом (из 65 удвоением до 130, из 128 добавлением камня до 129). Попасть в 64 можно из $S = 63$ (добавить камень) и из $S = 32$ (удвоить). Оба значения не превосходят 64, поэтому первым ходом Петя выиграть не может — второе условие задачи тоже выполнено.

Записываем найденные значения в порядке возрастания: 32 и 63.

def win_now(s):
    return s + 1 >= 129 or 2 * s >= 129

res = []
for s in range(1, 129):
    if win_now(s):                       # Петя выигрывает сразу — не подходит
        continue
    for m in (s + 1, 2 * s):             # ход Пети
        if not win_now(m) and all(win_now(k) for k in (m + 1, 2 * m)):
            res.append(s)
            break
print(res[:2])                           # [32, 63]

Ответ: 32 63