Решение 1. Счётчик ходов n
🔹 Шаг 1. Как формализована игра
Есть две кучи с камнями (a, b). За ход — увеличить одну кучу на +1 или ×2.
Игра заканчивается, когда a + b ≥ 171.
🔹 Шаг 2. Функция f(s1, s2, n)
def f(s1, s2, n):
if s1 + s2 >= 171 or n > 3:
return n == 3
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(*[s for s in range(1, 146) if not f(25, s, 1) and f(25, s, 3)])
📌 f(s1, s2, n) — номер полухода n растёт на 1 после каждого хода; возвращает True, если у текущего игрока есть выигрышная стратегия.
🔹 Шаг 3. Базовый случай
if s1 + s2 >= 171 or n > 3:
return n == 3
📌 Игра уже завершена на глубине n = 3 — победил нужный игрок.
🔹 Шаг 4. Рекурсия по ходам
h = (
f(..., n + 1),
...
)
📌 Все ходы из позиции передаются в кортеж h; счётчик n увеличивается.
🔹 Шаг 5. any и all
return any(h) if n % 2 == 0 else all(h)
📌 На ходах Пети (n чётное) достаточно одного удачного ответа; на ходах Вани — должны выигрывать все ветви.
✅ Задание 20
📌 Все S с f(s, 0); в ответ — два наименьших: 60 72.