Задание 21

Для игры, описанной в задании 19, найдите наименьшее значение S, при котором одновременно выполняются два условия:

— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение 1. Счётчик ходов n

🔹 Шаг 1. Как формализована игра

Две кучи (s1, s2); ход — +1 или ×3 одной кучи. Конец при s1 + s2 ≥ 171.

🔹 Шаг 2. Функция f(s1, s2, n)

def f(s1, s2, n):
    if s1 + s2 >= 171 or n > 4:
        return n == 4
    h = (
        f(s1 + 1, s2, n + 1),
        f(s1 * 2, s2, n + 1),
        f(s1, s2 + 1, n + 1),
        f(s1, s2 * 2, n + 1)
    )
    return any(h) if n % 2 == 0 else all(h)

print(min([s for s in range(1, 146) if not f(25, s, 2) and f(25, s, 4)]))

📌 f(s1, s2, n) — номер полухода n растёт на 1 после каждого хода; возвращает True, если у текущего игрока есть выигрышная стратегия.

🔹 Шаг 3. Базовый случай

if s1 + s2 >= 171 or n > 4:
    return n == 4

📌 Игра уже завершена на глубине n = 4 — победил нужный игрок.

🔹 Шаг 4. Рекурсия по ходам

h = (
    f(..., n + 1),
    ...
)

📌 Все ходы из позиции передаются в кортеж h; счётчик n увеличивается.

🔹 Шаг 5. any и all

return any(h) if n % 2 == 0 else all(h)

📌 На ходах Пети (n чётное) достаточно одного удачного ответа; на ходах Вани — должны выигрывать все ветви.

✅ Задание 21

📌 Минимальное (или наибольшее по условию) S с f(s, 0). Ответ: 59.