Решение 1. Анализ через f(s, m)

🔹 Шаг 1. Создаем рекурсивную функцию

def f(s, m):

📌 Функция определяет, может ли текущий игрок гарантированно победить, если до окончания анализа осталось m ходов.

🔹 Шаг 2. Проверяем окончание игры

if s <= 30 or m < 0:

📌 Если в куче уже не больше 30 камней или ходы закончились, рекурсия завершается.

🔹 Шаг 3. Возвращаем результат

return m % 2 == 0

📌 Если игра закончилась на нужной глубине, возвращается True, иначе False. Чётность m показывает, чей ход оказался победным.

🔹 Шаг 4. Перебираем все возможные ходы

h = [
    f(s - 3, m - 1),
    f(s - 5, m - 1),
    f(s // 4, m - 1),
]

📌 Из каждой позиции три действия: −3, −5 или s // 4.

🔹 Шаг 5. Выбираем any или all

return any(h) if (m - 1) % 2 == 0 else all(h)

📌 На своём ходу достаточно одного выигрышного варианта (any), на ходе соперника победа должна сохраняться после любого ответа (all).

✅ Задание 19

📌 Найти минимальное S, когда Петя не выигрывает за один ход, но при любом ходе Пети Ваня выигрывает своим первым ходом.

print(19, [s for s in range(31, 1001) if not f(s, 1) and f(s, 2)])

📌 not f(S, 1) — победить первым ходом нельзя; f(S, 2) — Ваня отвечает выигрышно. Минимальное значение: 124.

✅ Задание 20

📌 Найти два минимальных S, когда Петя не выигрывает сразу, но гарантированно выигрывает своим вторым ходом.

print([s for s in range(31, 1001) if not f(s, 1) and f(s, 3)])

📌 not f(S, 1) и f(S, 3). Два первых значения: 127 и 128.

✅ Задание 21

📌 Найти минимальное S, когда Ваня выигрывает первым или вторым ходом, но не имеет гарантированной победы первым ходом.

print([s for s in range(31, 1001) if not f(s, 2) and f(s, 4)])

📌 not f(S, 2) и f(S, 4). Ответ: 132.