21. Выигрышная стратегия: часть 3: Тогда за один ход можно получить любую из четырёх позиций: (24…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
Для игры, описанной в задании $19$, найдите наименьшее значение $S$, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Первый способ – математическое решение
Минимальное подходящее значение: $S=44$.
После первого хода Пети возможны позиции:
$(21;44)$, $(17;48)$, $(34;44)$, $(17;88)$.
Если получена позиция $(17;88)$, Ваня выигрывает сразу: $(17;88)\rightarrow(17;176)$.
Из позиции $(21;44)$ Ваня получает $(42;44)$, из позиции $(17;48)$ — $(34;48)$, из позиции $(34;44)$ — $(34;48)$. После любого следующего хода Пети Ваня сможет выиграть своим вторым ходом.
Например, из $(42;44)$ Петя может получить: $(46;44)$, $(42;48)$, $(84;44)$, $(42;88)$, и из каждой такой позиции Ваня выигрывает следующим ходом.
При этом после хода Пети $(17;44)\rightarrow(21;44)$ Ваня не может выиграть сразу, поэтому гарантированной победы первым ходом у него нет.
Для $S<44$ условия одновременно не выполняются.
Второй способ – решение с помощью Python
def moves(a, b):
return [(a + 4, b), (a, b + 4),
(a * 2, b), (a, b * 2)]
def win1(a, b):
return a + b < 133 and any(
x + y >= 133 for x, y in moves(a, b)
)
def win2(a, b):
if win1(a, b):
return True
return any(
all(
x + y < 133 and win1(x, y)
for x, y in moves(c, d)
)
for c, d in moves(a, b)
if c + d < 133
)
for S in range(1, 116):
petya = moves(17, S)
if (
all(a + b < 133 and win2(a, b) for a, b in petya)
and not all(win1(a, b) for a, b in petya)
):
print(S)
break
Программа проверяет, что после любого хода Пети Ваня может выиграть первым или вторым ходом, но не может гарантированно выиграть своим первым ходом.
Программа выведет: $44$.