Задания 19-20-21: Теория игр

• Тема: анализ стратегических игр с кучами камней.
• Ответ: целое число (начальное количество камней, позиция и т.д.).

Общая формулировка

Два игрока (Петя и Ваня) по очереди совершают ходы. Первый ходит Петя. На каждом ходу игрок выполняет одно из разрешённых действий (например, добавить 1 камень, добавить 2 камня, удвоить количество камней). Игра заканчивается, когда выполняется условие завершения (например, количество камней >= 25). Выигрывает тот, кто сделал последний ход (привёл к выполнению условия), или, в некоторых задачах, чей соперник не может ходить.

Задания: N19-20-21.Теория игр | N19-20-21.Разминка

Формулировки из условий

В одной связке 19-21 всегда одни и те же правила игры; отличаются только вопрос и ограничения на длину партии или на ход игрока. Ниже hod (как в шаблоне g(s, hod, end) ниже по файлу) - число уже сделанных полуходов к моменту, когда куча стала терминальной (s выполнило условие конца). Первый полуход зачастую делает Петя.

Если в задаче первым ходит Ваня или счёт полуходов в решении начинают с 1 по-другому, номера hod в колонке таблицы нужно сдвинуть на 1, но порядок чередования Петя - Ваня - Петя обычно сохраняется.

Ключевые понятия

Позиция

Текущее состояние игры (например, количество камней в кучах).

Выигрышная позиция (В)

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

Проигрышная позиция (П)

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

Правило определения

• Если из позиции существует ход в проигрышную для соперника позицию -> позиция выигрышная
• Если все ходы ведут в выигрышные для соперника позиции -> позиция проигрышная

Типы заданий

Задание 19: Кто выигрывает?

Вопрос: При каком начальном количестве камней первый (или второй) игрок выигрывает за 1 ход?

Подход: Перебрать начальные позиции и проверить, может ли первый игрок одним ходом завершить игру.

Задание 20: Выигрышная стратегия за 2 хода

Вопрос: При каком начальном количестве камней первый (или второй) игрок выигрывает не более чем за 2 хода?

Подход: Для каждой начальной позиции проверить все комбинации ходов на глубину 2.

Задание 21: Полное дерево игры

Вопрос: При каком начальном количестве камней заданный игрок выигрывает (при оптимальной игре обоих)?

Подход: Построить полное дерево позиций и определить выигрышные/проигрышные позиции снизу вверх.

Наглядные примеры с числами

Пример 1: одна куча

Условия примера:

• одна куча, начально S = 11
• ходы: +1 или x2
• конец игры: S >= 25

Ход Пети 1:

• если Петя делает x2, получаем 22
• тогда Ваня своим первым ходом может сделать x2 и получить 44, игра завершена, Ваня победил

Ход Пети 2:

• если Петя делает +1, получаем 12
• из 12 Ваня одним ходом не может получить >= 25 (13 или 24)

Этот пример показывает фразу из КИМ: «после неудачного хода Пети Ваня выигрывает своим первым ходом». Неудачный первый ход Пети здесь - переход в 22.

Пример 2: две кучи

Условия примера:

• кучи (6, S), возьмём S = 7, начальная позиция (6, 7)
• за ход можно увеличить одну выбранную кучу: +1 или x3
• конец игры: a + b >= 65

Четыре первых хода Пети из (6, 7):

• (7, 7) (добавил 1 в первую)
• (6, 8) (добавил 1 во вторую)
• (18, 7) (утроил первую)
• (6, 21) (утроил вторую)

Разберём два хода:

• из (6, 21) Ваня может утроить вторую кучу: (6, 63), сумма 69, Ваня выигрывает сразу
• из (7, 7) Ваня одним ходом не завершает игру (максимум (21, 7), сумма 28)

Получается, у Пети есть как неудачный, так и более аккуратный первый ход. Это ровно та логика, которую мы кодируем через перебор позиций после первого хода Пети и проверку условия для Вани.

Алгоритм решения (аналитический)

Шаг 1: Выписать условие

• Начальное количество камней (или диапазон)
• Разрешённые ходы (например: +1, +2, x2)
• Условие завершения (например: S >= 25)
• Кто ходит первым (обычно Петя)

Шаг 2: Построить таблицу позиций

Шаг 3: Определить тип каждой позиции

Двигаемся от конечных позиций к начальным:

• Если хотя бы один ход ведёт в П -> позиция В
• Если все ходы ведут в В -> позиция П

Шаг 4: Ответить на вопрос задачи

• Задание 19: найти S, где первый ход сразу завершает игру
• Задание 20: найти S, где за 2 хода гарантированно выигрыш
• Задание 21: найти S, где при полном дереве игры выигрывает нужный игрок

Алгоритм решения (Python)

1) Одна куча (шаблон)

TARGET = 129

def g1(s, hod, end):
    if s >= TARGET:
        return hod in end
    if hod >= max(end):
        return False
    moves = [
        g1(s + 1, hod + 1, end),
        g1(s * 2, hod + 1, end),
    ]
    return any(moves) if ((hod + 1) % 2) == (end[0] % 2) else all(moves)

print([
    s for s in range(1, TARGET)
    # if g1(s, 0, [2])                         # 19: Ваня выиграл 1-м ходом
    # if g1(s, 0, [3]) and not g1(s, 0, [1])   # 20: Петя 2-м ходом, но не 1-м
    # if g1(s, 0, [2, 4]) and not g1(s, 0, [2])# 21: Ваня 1-м или 2-м, но не гарантированно 1-м
])

2) Две кучи (шаблон)

TARGET = 65

def g2(a, b, hod, end):
    if a + b >= TARGET:
        return hod in end
    if hod >= max(end):
        return False
    moves = [
        g2(a + 1, b, hod + 1, end),
        g2(a, b + 1, hod + 1, end),
        g2(a * 3, b, hod + 1, end),
        g2(a, b * 3, hod + 1, end),
    ]
    return any(moves) if ((hod + 1) % 2) == (end[0] % 2) else all(moves)

print([
    s for s in range(1, 59)
    # if any(a1 + b1 < TARGET and g2(a1, b1, 1, [2]) for a1, b1 in ((7, s), (6, s + 1), (18, s), (6, 3 * s))) and any(a1 + b1 < TARGET and not g2(a1, b1, 1, [2]) for a1, b1 in ((7, s), (6, s + 1), (18, s), (6, 3 * s)))
    # if g2(6, s, 0, [3]) and not g2(6, s, 0, [1])
    # if g2(6, s, 0, [2, 4]) and not g2(6, s, 0, [2])
])

3) Задачи с числами на доске (без рекурсии)

def step(board):
    b = sorted(board)
    return b[:-2] + [b[-2] + b[-1]]

def finish_hod(s, target=100):
    board = list(range(1, s + 1))
    hod = 0
    while max(board) < target:
        board = step(board)
        hod += 1
    return hod

print([
    s for s in range(14, 100)
    # if finish_hod(s) == 2   # Ваня выигрывает своим первым ходом
    # if finish_hod(s) == 3   # Петя выигрывает своим вторым ходом
])

Таблица: формулировка задачи -> код

Типичные ошибки

1. Перепутаны OR и AND - на своём ходу any(), на ходу соперника all()
2. Неправильный номер хода - Петя = нечётные (1, 3, 5...), Ваня = чётные (2, 4, 6...)
3. Забыли про условие завершения - нужно проверять, что позиция ещё не конечная
4. Не учтено, кто сделал последний ход - выигрывает тот, кто привёл к завершению

Полезные советы

1. Начинайте с конечных позиций и двигайтесь назад
2. Рисуйте дерево игры для маленьких примеров
3. Проверяйте на примерах из условия перед сдачей
4. Внимательно читайте, кто выигрывает - иногда спрашивают про Ваню, а не Петю

Составлено: Лилия С. Источники: КИМ ЕГЭ 2026, открытый банк ФИПИ, спецификация ЕГЭ по информатике

Удачи на экзамене!