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

Решение:

Позицию обозначаем (x, y). За один ход общее количество камней растёт либо на 1 (добавили камень), либо на x, либо на y (удвоили соответствующую кучу). Значит одним ходом можно прибавить не больше чем $\max(x,\,y,\,1)$, и игрок заканчивает игру своим ходом тогда и только тогда, когда $x+y+\max(x,\,y,\,1) \ge 59$.

Нам нужен неудачный ход Пети, после которого Ваня заканчивает игру. Иначе говоря, из позиции (5, S) за два хода (сначала Петя, потом Ваня) должно набираться не менее 59 камней. Больше всего даёт двукратное удвоение большей кучи: (5, S) → (5, 2S) → (5, 4S), всего $5+4S$ камней; любая другая пара ходов даёт меньше — например, (5, S+1) → (5, 2S+2) даёт лишь $5+2S+2$, а (5+1, S) → (5+1, 2S) даёт $5+1+2S$.

Условие $5+4S \ge 59$ равносильно $S \ge \frac{59-5}{4} = 13{,}5$, поэтому минимальное подходящее значение $S = 14$.

Проверим его. Сам Петя выиграть не может: удвоив большую кучу, он получит $5+2\cdot14 = 33$ камней, а это меньше 59. Но если он удвоит вторую кучу, возникнет позиция (5, 28); тогда Ваня удваивает её ещё раз, получает (5, 56), то есть 61 камней — не меньше 59, и Ваня выигрывает своим первым ходом.

Проверка перебором:

N = 59
A = 5                            # камней в первой куче

def moves(p):
    x, y = p
    return [(x + 1, y), (2 * x, y), (x, y + 1), (x, 2 * y)]

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

for s in range(1, 54):
    p = (A, s)
    # сам Петя выиграть не может, но неудачным ходом дарит победу Ване
    if not win1(p) and any(win1(q) for q in moves(p)):
        print(s)                  # 14
        break

Ответ: 14