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

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

Есть две кучи с камнями (a, b). За ход — увеличить одну кучу на +4 или ×2.

Игра заканчивается, когда a + b ≥ 165.

🔹 Функция f(s1, s2, n)

def f(s1, s2, n):
    ...

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

🔹 Базовый случай

if s1 + s2 >= 165 or n > 2:
    return n == 2

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

🔹 Рекурсия по ходам

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

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

🔹 any и all

return any(h)

📌 Текущий игрок выбирает любой выигрышный ход — any(h).

✅ Задание 19

📌 Перебор S: первое значение, где f(14, s, 0) истинно (Ваня выигрывает после неудачного хода Пети). Ответ: 38.

🔹 Классификация позиций win/lose

Для заданий 20 и 21 удобно разметить позиции: win1, lose1, win2, lose2, win3, lose3.

🔹 Ходы и конец игры

def moves(h):
    a, b = h
    return (a + 4, b), (a * 2, b), (a, b + 4), (a, b * 2)

def game_over(h):
    return sum(h) >= 165

📌 Две кучи (a, b). Ход: +4 или ×2. Конец при a + b ≥ 165.

🔹 win1 и lose1

def win1(h):
    return not game_over(h) and any(game_over(m) for m in moves(h))

def lose1(h):
    return not win1(h) and all(win1(m) for m in moves(h))

📌 win1 — можно выиграть одним ходом. lose1 — любой ход отдаёт сопернику победу за один ход.

🔹 win2 и lose2

def win2(h):
    return not win1(h) and any(lose1(m) for m in moves(h))

def lose2(h):
    return (
        not win1(h) and not win2(h)
        and all(win1(m) or win2(m) for m in moves(h))
        and any(win2(m) for m in moves(h))
    )

📌 win2 — выигрыш своим вторым ходом. lose2 — соперник выигрывает не позже своего второго хода.

🔹 win3 и lose3

def win3(h):
    return not win1(h) and not win2(h) and any(lose2(m) for m in moves(h))

def lose3(h):
    return (
        not win1(h) and not win2(h) and not win3(h)
        and all(win1(m) or win2(m) or win3(m) for m in moves(h))
        and any(win3(m) for m in moves(h))
    )

📌 win3 — победа своим третьим ходом. lose3 — у соперника есть стратегия выиграть вторым или третьим ходом.

✅ Задание 20

📌 Нужны два наименьших S, где Петя не выигрывает первым и вторым ходом, но выигрывает третьим.

values = [
    s for s in range(1, 151)
    if not win1((14, s)) and not win2((14, s)) and win3((14, s))
]
print(*values[:2])

📌 Ответ: 32 и 59.

✅ Задание 21

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

for s in range(1, 151):
    if (lose2((14, s)) or lose3((14, s))) and not win2((14, s)):
        print(s)
        break

📌 Ответ: 57.