20. Выигрышная стратегия: часть 2: Игра завершается в тот момент, когда суммарное количество камней…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите два наименьших значения $S$, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без пробелов.
Первый способ – математическое решение
Петя не должен выигрывать первым ходом, поэтому $13+2S<135$, откуда $S\leq60$.
Первое подходящее значение: $S=30$. Петя удваивает вторую кучу: $(13;30)\rightarrow(13;60)$.
Ваня может получить: $(16;60),\ (13;63),\ (26;60),\ (13;120)$.
Из каждой такой позиции Петя выигрывает следующим ходом:
- $(16;60)\rightarrow(16;120)$, сумма $136$;
- $(13;63)\rightarrow(13;126)$, сумма $139$;
- $(26;60)\rightarrow(26;120)$, сумма $146$;
- $(13;120)\rightarrow(16;120)$, сумма $136$.
Второе подходящее значение: $S=53$. Петя удваивает первую кучу: $(13;53)\rightarrow(26;53)$.
После любого хода Вани Петя также сможет выиграть следующим ходом.
Второй способ – решение с помощью Python
def moves(a, b):
return [(a + 3, b), (a, b + 3),
(a * 2, b), (a, b * 2)]
def win1(a, b):
return a + b < 135 and any(
x + y >= 135 for x, y in moves(a, b)
)
ans = []
for S in range(1, 122):
if not win1(13, S):
if any(
all(
x + y < 135 and win1(x, y)
for x, y in moves(a, b)
)
for a, b in moves(13, S)
):
ans.append(S)
print(ans[:2])
Программа проверяет, что Петя не может выиграть первым ходом, а затем ищет такой его ход, после которого при любом ходе Вани Петя выигрывает следующим ходом.
Программа выведет: $[30,\ 53]$.