Задания 19–21 (одна куча)

13.10.2026

Легенда

Петя и Ваня играют в игру с одной или двумя кучами камней. Первый ход делает Петя. За один ход игрок может изменить количество камней в любой из куч определённым образом (прибавить число, умножить на число). Выигрывает тот, кто первым достигнет или превысит заданное число камней (или уменьшит его до определённого предела).

Пример 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
убрать из кучи 3 камня;
убрать из кучи 7 камней;
уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Игра завершается, когда количество камней в куче становится не более 15. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 15 или менее камней. В начальный момент в куче было S камней, S > 15. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
Петя не может выиграть за один ход;
Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Осмыслим прочитанное:

Петя ходит первым, Ваня — вторым
Возможные ходы:
- -3 камня из кучи
- -7 камней из кучи
- разделить количество камней в куче на 4, округлив в меньшую сторону
Выигрыш при S <= 15 (не более 15 камней в куче)
В начальный момент в куче больше 15 камней

Напишем программу для решения:

def f(s, m):

    # Пропишем условия завершения игры:
    # если куча уже победная (<= 15):
    # m % 2 == 0 означает, что победил "наш" целевой игрок
    # (Петя при нечётном начальном m, или Ваня при чётном начальном m)
    if s <= 15: return m % 2 == 0

    if m == 0: return 0 # условие завершения рекурсии

    # список всех возможных ходов
    # вызываем f от нового количества камней в куче,
    # уменьшаем количество ходов на 1
    moves = [f(s - 3, m - 1), f(s - 7, m - 1), f(s // 4, m - 1)]

    # если следующий ход делает наш игрок, то нам достаточно доказать
    # существование хотя бы одного выигрышного хода для него;
    # в противном случае нужно проверить все возможные ходы противника,
    # поскольку, если он играет *оптимально* по условию, он непременно
    # воспользуется возможностью загнать своего оппонента в неудачную позицию.

    # (m - 1), потому что проверяем СЛЕДУЮЩИЙ ход после текущего шага
    return any(moves) if (m - 1) % 2 == 0 else all(moves)

# Не дана верхняя граница изначально возможного количества камней в куче,
# поэтому ставим наугад 100. Если бы мы не получили ни одного ответа в № 19, меньше
# двух ответов в № 20 и/или ни одного ответа в № 21, следовало бы поднять верхнюю границу перебора.

# Первый шаг игры (ход Пети) не может быть победным,
# и Ваня выигрывает своим первым ходом (вторым за всю игру)
print('19)', [s for s in range(16, 100) if not f(s, 1) and f(s, 2)])
# Петя не выигрывает на первом шаге игры, и Петя выигрывает на третьем шаге игры (свой второй ход)
print('20)', [s for s in range(16, 100) if not f(s, 1) and f(s, 3)])
# Ваня НЕ выигрывает на втором шаге игры гарантированно, и выигрывает на 4-м шаге игры
print('21)', [s for s in range(16, 100) if not f(s, 2) and f(s, 4)])

Мы ввели функцию f(s, m). Что она возвращает и что принимает в качестве аргумента?

f(s, m) отвечает на вопрос: «завершится ли партия победой за m шагов игры (или быстрее)?»
На вопрос, чьей именно победой, отвечает чётность m. Изучим иллюстрацию:

Стоит сказать, что шаг игры ≠ ход. Шаг игры (m) — счётчик действий любого игрока от самого начала игры!

Программа выводит:

19) [64, 65, 66]
20) [67, 68, 69, 71, 72, 73]
21) [70, 74, 75, 76]

Смотрим, что нам надо найти, и пишем в ответе:

64 — минимальное значение
67 68 — два наименьших
70 — минимальное значение

Внимательно посмотрев на иллюстрацию, повторим ещё раз:

not f(s, 1) and f(s, 2) = игра НЕ закончится победой на 1-м шаге И закончится победой на 2-м шаге
not f(s, 1) and f(s, 3) = игра НЕ закончится победой на 1-м шаге И закончится победой на 3-м шаге
not f(s, 2) and f(s, 4) = игра НЕ закончится победой на 2-м шаге (или быстрее) И закончится победой на 4-м шаге

Пример 2

Теперь возьмём задачу с хитростью:

(О. Лысенков) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один свой ход Петя может добавить в кучу 3 камня или увеличить количество камней в куче в три раза. Ваня за один свой ход может добавить в кучу 5 камней или увеличить количество камней в куче в три раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается в тот момент, когда количество камней в куче становится не менее 231. Победителем считается игрок, сделавший последний ход, т.е. первым получивший в куче 231 камень или больше. В начальный момент в куче было S камней, 10 ≤ S ≤ 120. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Задание 19.
Укажите минимальное значение S, когда Петя не может выиграть за один ход, но при этом Ваня может выиграть своим первым ходом при любой игре Пети.
Задание 20.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите максимальное значение S, при котором одновременно выполняются два условия:
у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Выделим главное:

Первым ходит Петя, вторым — Ваня
Петя может:
- +3
- *3
Ваня может:
- +5
- *3
Игра завершается, когда в куче не менее 231 камня
В начале игры 10 ≤ S ≤ 120

Напишем программу, учтя все эти условия, по шаблону:

def f(s, m, who):
    # условие завершения игры
    if s >= 231: return m % 2 == 0
    # условие завершения рекурсии
    if m == 0: return 0

    # если ходит Ваня
    if who == 'V':
        # третий аргумент `who` чередуется: если ходил Ваня,
        # следующий ход — у Пети
        moves = [f(s + 5, m - 1, 'P'), f(s * 3, m - 1, 'P')]
    # если ходит Петя
    if who == 'P':
        # если ходил Петя, то следующий ход — у Вани
        moves = [f(s + 3, m - 1, 'V'), f(s * 3, m - 1, 'V')]

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

print('19)', [s for s in range(10, 121) if not f(s, 1, 'P') and f(s, 2, 'V')])
print('20)', [s for s in range(10, 121) if not f(s, 1, 'P') and f(s, 3, 'P')])
print('21)', [s for s in range(10, 121) if not f(s, 2, 'V') and f(s, 4, 'V')])

Запустим, получим ответы:

19) [72, 73, 74, 75, 76]
20) [24, 25, 69, 70, 71, 72, 73]
21) [64, 65, 66, 67, 68]

72
24 25
68

Обманулись? Я тоже. Ответ-то неправильный, должно быть:

74
24 25
68

В чём же дело? Посмотрим внимательно сюда:

print('19)', [s for s in range(10, 121) if not f(s, 1, 'P') and f(s, 2, 'V')])
print('20)', [s for s in range(10, 121) if not f(s, 1, 'P') and f(s, 3, 'P')])
print('21)', [s for s in range(10, 121) if not f(s, 2, 'V') and f(s, 4, 'V')])

За что отвечает параметр who в функции? Он указывает, кто делает ход прямо сейчас. А поскольку в начале игры первый ход всегда делает Петя, при внешнем вызове начальным значением всегда должен быть 'P' — Ваня никогда не начинает игру первым.

def f(s, m, who):
    # условие завершения игры
    if s >= 231: return m % 2 == 0
    # условие завершения рекурсии
    if m == 0: return 0

    # если ходит Ваня
    if who == 'V':
        # третий аргумент `who` чередуется: если ходил Ваня,
        # следующий ход — у Пети
        moves = [f(s + 5, m - 1, 'P'), f(s * 3, m - 1, 'P')]
    # если ходит Петя
    if who == 'P':
        # если ходил Петя, то следующий ход — у Вани
        moves = [f(s + 3, m - 1, 'V'), f(s * 3, m - 1, 'V')]

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

print('19)', [s for s in range(10, 121) if not f(s, 1, 'P') and f(s, 2, 'P')])
print('20)', [s for s in range(10, 121) if not f(s, 1, 'P') and f(s, 3, 'P')])
print('21)', [s for s in range(10, 121) if not f(s, 2, 'P') and f(s, 4, 'P')])

19) [*74*, 75, 76]
20) [*24*, *25*, 69, 70, 71, 72, 73]
21) [66, 67, *68*]

Ответы:

74
24 25
68

Мы рассмотрели две задачи: одну базовую, простую, а другую — чуть посложнее. Если понять саму логику работы программы, этого достаточно, чтобы решать почти любые задания 19–21 на одну кучу камней.

Задания 19–21 (одна куча)

Легенда

Пример 1

Пример 2

Задать вопрос или оставить отзыв