Решение 1. Счётчик ходов n
🔹 Шаг 1. Как формализована игра
Одна куча s. Ходы: −3, −7, s // 4.
Игра заканчивается при s ≤ 15.
🔹 Шаг 2. Функция f(s, n)
def f(s, n):
if s <= 15 or n > 4:
return n == 2 or n == 4
h = (
f(s - 3, n + 1),
f(s - 7, n + 1),
f(s // 4, n + 1)
)
return any(h) if n % 2 else all(h)
for s in range(16, 100):
if f(s, 0):
print(s)
📌 f(s, n) — номер полухода n растёт на 1 после каждого хода; возвращает True, если у текущего игрока есть выигрышная стратегия.
🔹 Шаг 3. Базовый случай
if s <= 15 or n > 4:
return n == 2 or n == 4
📌 Победа фиксируется при n = 2 или 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). Ответ: 70.