Теория игр

1. Введение

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

Нужно определить не просто возможный ход, а гарантированную стратегию: игрок должен добиться победы при любых действиях соперника.

Все три задания удобно решать одной функцией. Между номерами меняются три вещи:

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

2. Теория и разбор условия

Условие игры

Перед игроками лежит одна куча камней. Первый ход делает Петя.

За один ход игрок может:

добавить в кучу 1 камень;
увеличить количество камней в два раза.

Игра заканчивается, когда в куче становится не менее 177 камней. Побеждает игрок, сделавший последний ход.

Начальное значение S находится в пределах от 1 до 176.

Чтобы проверить победу за один ход, применяем обе команды. Если хотя бы после одной из них камней стало 177 или больше, игрок может закончить игру этим ходом.

Что значит «выигрышная стратегия»

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

Что проверяется

Умение понять условие игры, отличить возможную победу от гарантированной и аккуратно перебрать допустимые начальные значения.

Главный вопрос

Кто должен выиграть, каким по счёту ходом и должна ли победа получаться после любого ответа соперника?

Логика каждого номера

№19. Петя не должен закончить игру первым ходом. Какой бы из двух ходов он ни сделал, после него Ваня должен суметь одним ходом получить 177 камней или больше.
№20. Петя не может выиграть первым ходом. Он должен выбрать такой первый ход, чтобы после любого ответа Вани у него оставалась возможность закончить игру своим вторым ходом.
№21. После любого первого хода Пети Ваня должен гарантированно закончить игру своим первым или вторым ходом. Но позиции, где Ваня всегда выигрывает уже первым ходом, не подходят — это как раз результаты №19.

Сначала логика — потом код.

Во втором пункте достаточно понять порядок ходов и слова «существует ход» или «после любого хода». Переменные и условия Python вводим только дальше.

3. Базовый код и разбор

Как перенести условие в функцию

В функции k — текущее количество камней, а x — номер позиции.

Начинаем с:

f(k, 1)

Первым должен ходить Петя.

После каждого сделанного хода x увеличивается на 1.

Важный момент: функция сначала смотрит, закончилась ли игра, а затем делает новый ход.

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

Ваня выиграл первым ходом → проверяем x == 3.
Петя выиграл вторым ходом → проверяем x == 4.

Как понять or и and

or читаем как «или»: достаточно, чтобы подошёл хотя бы один из разрешённых ходов.
and читаем как «и»: должны подойти все варианты хода соперника.
Нечётные x — ходы Пети: 1, 3, 5, ...
Чётные x — ходы Вани: 2, 4, 6, ...

Задание	Чью стратегию проверяем	Когда победа должна обнаружиться	Где ставим `or`
19	Вани	`x = 3` — после первого хода Вани	`x % 2 == 0`
20	Пети	`x = 4` — после второго хода Пети	`x % 2 == 1`
21	Вани	`x = 3` или `x = 5` — после первого или второго хода Вани	`x % 2 == 0`

Что означают True и False

return True означает: начальное значение подходит под требования задачи.
return False означает: значение не подходит — игра закончилась не на том ходе, нужный игрок не успел победить или гарантии нет.
Сначала проверяем нужный момент победы, затем проверяем, не вышли ли за нужное число ходов, и только потом отбрасываем остальные случаи завершения игры.

Задание 19

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

a = []  # сюда сохраним ответ задания 19

def f(k, x):
    # Ваня сделал первый ход; результат проверяем при x == 3
    if k >= 177 and x == 3:
        return True

    # До нужного момента игра не закончилась
    if k < 177 and x == 3:
        return False

    # Игра закончилась раньше: это не победа Вани первым ходом
    if k >= 177:
        return False

    # Чётный x — ход Вани: ему достаточно одного удачного хода
    if x % 2 == 0:
        return f(k + 1, x + 1) or f(k * 2, x + 1)
    else:
        # Нечётный x — ход Пети: должны подходить оба его хода
        return f(k + 1, x + 1) and f(k * 2, x + 1)


for k in range(1, 177):
    if f(k, 1):
        a.append(k)

print(a)

Ответ задания 19: 88

Что отвечает за что

f(k, x) получает количество камней k и номер позиции x. Начинаем с x = 1, потому что первым ходит Петя.
Пара условий с x == 3 разрешает победу Вани ровно первым ходом и запрещает затянуть игру дальше.
Условие k >= 177 означает, что игра уже закончилась. Если это произошло не в нужный момент, функция возвращает False.
При x % 2 == 0 ходит Ваня. Он сам выбирает свой ход, поэтому достаточно одного подходящего варианта — ставим or.
На нечётном x ходит Петя. Мы не знаем, что он выберет, поэтому победа Вани должна сохраняться после обеих команд — ставим and.
Два рекурсивных вызова точно повторяют команды из условия: добавить 1 и умножить на 2.
Цикл перебирает все допустимые S от 1 до 176. Вызов f(k, 1) означает начало игры.

Как меняется решение задания 20

Теперь проверяется выигрышная стратегия Пети: он не может выиграть первым ходом, но гарантированно выигрывает своим вторым ходом независимо от игры Вани.

Теперь нужен выигрыш Пети. Петя ходит при нечётных x и сам выбирает ход: достаточно одного удачного варианта. Поэтому пишем x % 2 == 1 и используем or.
На чётных x ходит Ваня. Мы не знаем, какой ход он выберет, поэтому дальнейшая победа Пети должна получаться после обеих команд — используем and.
Второй ход Пети совершается при x = 3, а победа обнаруживается в следующем вызове — при x == 4.
Общий if k >= 177: return False отбрасывает победу Пети первым ходом, потому что она обнаружилась бы при x == 2, а не при x == 4.

# Задание 20

def f(k, x):
    # Петя выиграл вторым ходом; проверяем после него при x == 4
    if k >= 177 and x == 4:
        return True

    if k < 177 and x == 4:
        return False

    # Более раннее завершение игры не подходит
    if k >= 177:
        return False

    # Нечётный x — ход Пети: достаточно одного удачного хода
    if x % 2 == 1:
        return f(k + 1, x + 1) or f(k * 2, x + 1)
    else:
        # Чётный x — ход Вани: победа Пети нужна при любом ответе
        return f(k + 1, x + 1) and f(k * 2, x + 1)


for k in range(1, 177):
    if f(k, 1):
        print(k)  # по условию берём два наименьших

Ответ задания 20: 44 и 87

Как меняется решение задания 21

Здесь снова проверяем стратегию Вани. Он должен гарантированно выиграть первым или вторым ходом, но не должен иметь стратегии гарантированной победы только первым ходом.

Снова нужен выигрыш Вани. Ваня ходит при чётных x и сам выбирает ход: пишем x % 2 == 0 и соединяем его варианты через or.
Победа Вани первым ходом обнаруживается при x == 3, вторым ходом — при x == 5. Поэтому в первом условии пишем (x == 3 or x == 5).
Если при x == 5 камней всё ещё меньше 177, Ваня не уложился в два хода: возвращаем False.
Условие «у Вани нет стратегии выиграть гарантированно первым ходом» уже решено в №19. Поэтому из результатов №21 исключаем все k, сохранённые в списке a.

# Задание 21

def f(k, x):
    # Ваня выиграл первым или вторым ходом
    if k >= 177 and (x == 3 or x == 5):
        return True

    # После второго хода Вани игра всё ещё не закончилась
    if k < 177 and x == 5:
        return False

    # Игра закончилась на неподходящем ходе
    if k >= 177:
        return False

    # Чётный x — ход Вани
    if x % 2 == 0:
        return f(k + 1, x + 1) or f(k * 2, x + 1)
    else:
        # Нечётный x — ход Пети
        return f(k + 1, x + 1) and f(k * 2, x + 1)


otv21 = []

for k in range(1, 177):
    # Исключаем значения из №19: там Ваня выигрывает сразу
    if f(k, 1) and k not in a:
        otv21.append(k)

print(min(otv21))

Ответ задания 21: 86

Короткая памятка по заданиям 20 и 21

20)
x % 2 == 1
x == 4

21)
x % 2 == 0
(x == 3 or x == 5) — в первом if
x == 5 — во втором if

4. Что может попасться в задании

4.1. Базовая задача: одна куча растёт

Это тип, который полностью разобран в пункте 3: одна куча, команды +1 и ×2, игра заканчивается при достижении порога.

В коде используются проверки:

k >= 177

вызовы:

f(k + 1, ...)
f(k * 2, ...)

а перебор идёт от 1 до 176.

4.2. Одна куча уменьшается

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

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.

За один ход игрок может:

убрать из кучи 3 камня;
убрать 5 камней;
уменьшить количество камней в куче в 3 раза.

Результат деления округляется до большего целого.

Игра завершается, когда в куче становится не более 33 камней. Побеждает игрок, сделавший последний ход.

В начальный момент в куче было S камней, S ≥ 34.

В этом варианте начальное число уже больше конечного порога. Игроки уменьшают кучу, а игра заканчивается, когда камней становится не больше заданного числа.

Логика ходов и значения x не меняются — меняются только знак сравнения, команды и границы перебора.

Условие окончания: было k >= 177, становится k <= 33.
Команды из примера: k - 3, k - 5 и деление на 3 с округлением вверх.
Начальные значения перебираем начиная с 34, потому что при k <= 33 игра уже закончена.
Для деления с округлением вверх подключаем ceil из модуля math.

Не меняем вслепую

Сначала определяем, чью стратегию проверяем, и только после этого выбираем чётность для or.

Значение x в условии победы всегда на единицу больше номера хода, которым игра должна закончиться.

Что требуется в №19

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

Важно различать округление

Вверх — ceil(k / n).
Вниз — k // n.
До ближайшего целого — round(k / n).

Если в условии отдельно сказано, что делать с результатом ровно .5, выполняем именно это правило.

from math import ceil

def f(k, x):
    if k <= 33 and x == 3:
        return True

    if k > 33 and x == 3:
        return False

    if k <= 33:
        return False

    if x % 2 == 0:
        return (f(k - 3, x + 1) or
                f(k - 5, x + 1) or
                f(ceil(k / 3), x + 1))
    else:
        return (f(k - 3, x + 1) and
                f(k - 5, x + 1) and
                f(ceil(k / 3), x + 1))


a = []

for k in range(34, 1000):
    if f(k, 1):
        a.append(k)

print(len(a), a)

Ответ задания 19: 3

4.3. Задача с двумя кучами

Перед игроками лежат две кучи. За ход можно выбрать одну кучу и либо добавить в неё 1 камень, либо увеличить её в два раза.

Игра заканчивается, когда сумма камней в кучах становится не меньше 231.

В первой куче 17 камней, во второй — S, где 1 ≤ S ≤ 213.

Функция получает три значения: f(k, k2, x). k и k2 — размеры двух куч, x — номер позиции.
Конец игры проверяем по сумме: k + k2 >= 231.
Возможны четыре хода: изменить первую кучу на +1 или ×2 либо так же изменить вторую.
Вызов f(k, 17, 1) означает: k — перебираемое значение S, 17 — размер другой кучи.

Не перепутай 213 и 231.

213 — наибольшее допустимое значение S.
231 — сумма, при которой заканчивается игра.

Поэтому во всех проверках конца игры пишем 231, а range заканчиваем на 213.

Особенность задания 19

В условии сказано, что Ваня выиграл после неудачного первого хода Пети.

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

Поэтому в задании 19 и на ходе Вани, и на ходе Пети используется or: сначала существует подходящий неудачный ход Пети, затем существует выигрышный ответ Вани.

В заданиях 20 и 21 формулировки снова требуют гарантии, поэтому в else возвращается обычный and.

# Две кучи — задание 19

def f(k, k2, x):
    if k + k2 >= 231 and x == 3:
        return True

    if k + k2 < 231 and x == 3:
        return False

    if k + k2 >= 231:
        return False

    if x % 2 == 0:
        return (f(k + 1, k2, x + 1) or
                f(k * 2, k2, x + 1) or
                f(k, k2 + 1, x + 1) or
                f(k, k2 * 2, x + 1))
    else:
        # Нужен хотя бы один неудачный ход Пети
        return (f(k + 1, k2, x + 1) or
                f(k * 2, k2, x + 1) or
                f(k, k2 + 1, x + 1) or
                f(k, k2 * 2, x + 1))


for k in range(1, 214):
    if f(k, 17, 1):
        print(k)  # берём минимальное

Ответ задания 19: 54

Задания 20 и 21 с двумя кучами

В №20 проверяем стратегию Пети: на нечётных x ставим or, на чётных — and.

В №21 проверяем стратегию Вани: на чётных x ставим or, на нечётных — and.

Четыре возможных хода и проверка суммы остаются теми же.

Задание 20

# Две кучи — задание 20

def f(k, k2, x):
    if k + k2 >= 231 and x == 4:
        return True

    if k + k2 < 231 and x == 4:
        return False

    if k + k2 >= 231:
        return False

    if x % 2 == 1:
        return (f(k + 1, k2, x + 1) or
                f(k * 2, k2, x + 1) or
                f(k, k2 + 1, x + 1) or
                f(k, k2 * 2, x + 1))
    else:
        return (f(k + 1, k2, x + 1) and
                f(k * 2, k2, x + 1) and
                f(k, k2 + 1, x + 1) and
                f(k, k2 * 2, x + 1))


for k in range(1, 214):
    if f(k, 17, 1):
        print(k)

Ответ задания 20: 98 и 106

Задание 21

# Две кучи — задание 21

def f(k, k2, x):
    if k + k2 >= 231 and (x == 3 or x == 5):
        return True

    if k + k2 < 231 and x == 5:
        return False

    if k + k2 >= 231:
        return False

    if x % 2 == 0:
        return (f(k + 1, k2, x + 1) or
                f(k * 2, k2, x + 1) or
                f(k, k2 + 1, x + 1) or
                f(k, k2 * 2, x + 1))
    else:
        return (f(k + 1, k2, x + 1) and
                f(k * 2, k2, x + 1) and
                f(k, k2 + 1, x + 1) and
                f(k, k2 * 2, x + 1))


for k in range(1, 214):
    if f(k, 17, 1):
        print(k)  # по условию берём минимальное

Ответ задания 21: 97

5. Автокод

Вместо отдельных функций для заданий 19, 20 и 21 можно использовать один короткий универсальный шаблон.

В нём меняются только число рассматриваемых ходов и проверки в последних строках.

def f(k, m):
    if k >= 229:
        return m % 2 == 0

    if m == 0:
        return 0

    h = [f(k + 1, m - 1), f(k * 2, m - 1)]

    return any(h) if m % 2 != 0 else all(h)


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

Что означают k и m

k — текущее количество камней в куче.

m — сколько ходов ещё рассматривает функция. После каждого хода m уменьшается на 1.

Например:

f(s, 2)

рассматривает два хода:

Петя → Ваня

Вызов:

f(s, 3)

рассматривает три хода:

Петя → Ваня → Петя

Проверка окончания игры

if k >= 229:
    return m % 2 == 0

Если камней стало не меньше 229, игра уже закончилась.

Но код должен понять, кто сделал последний ход. Если после победного хода осталось чётное m, функция возвращает True.

Для f(s, 2) после хода Пети остаётся m = 1, поэтому его немедленная победа даёт False.

После хода Вани остаётся m = 0, поэтому победа Вани даёт True.

Ограничение количества ходов

if m == 0:
    return 0

Если разрешённое количество ходов закончилось, а 229 камней так и не набралось, нужная победа не произошла.

Поэтому возвращается False. В Python число 0 здесь работает как False.

Все возможные ходы

h = [f(k + 1, m - 1), f(k * 2, m - 1)]

В список h записываются результаты двух разрешённых продолжений:

добавить 1 камень;
увеличить количество камней в два раза.

Одновременно уменьшаем m, потому что один ход уже сделан.

Зачем нужны any() и all()

return any(h) if m % 2 != 0 else all(h)

any(h) возвращает True, если подходит хотя бы один вариант.

Это ситуация, когда игрок сам выбирает ход и ему достаточно найти один удачный.

all(h) возвращает True только тогда, когда подходят все варианты.

Это ситуация хода соперника: мы не управляем его выбором, поэтому стратегия должна сохраняться при любом его действии.

Коротко:

any() — достаточно одного удачного хода;
all() — должны подойти все ответы соперника.

Почему выбор зависит от чётности m

В этом шаблоне нечётное m означает ход игрока, для которого сейчас ищется удачное продолжение, поэтому используется any().

Чётное m означает ход соперника, поэтому используется all().

Задание 19

print('19', [s for s in range(1, 228) if f(s, 2)])

f(s, 2) рассматривает:

Петя → Ваня

В начале m = 2, поэтому первый ход Пети проверяется через all(): должны подходить оба его возможных хода.

После хода Пети m = 1, поэтому Ване достаточно одного выигрышного ответа — any().

Так код автоматически реализует формулировку:

после любого хода Пети Ваня может выиграть своим первым ходом.

Задание 20

print('20', [s for s in range(1, 228) if not f(s, 1) if f(s, 3)])

Здесь одновременно проверяются два условия.

not f(s, 1)

Петя не может закончить игру своим первым ходом.

f(s, 3)

Рассматриваются три хода:

Петя → Ваня → Петя

Значит, Петя должен гарантированно закончить игру своим вторым ходом.

Итоговая логика:

Петя не выигрывает первым ходом, но гарантированно выигрывает вторым.

Задание 21

print('21', [s for s in range(1, 228) if not f(s, 2) if f(s, 4)])

f(s, 4) рассматривает четыре хода:

Петя → Ваня → Петя → Ваня

Это позволяет Ване гарантированно выиграть своим первым или вторым ходом.

not f(s, 2)

исключает позиции задания 19, где Ваня гарантированно выигрывает уже первым ходом.

Итоговая логика:

Ваня не обязан выигрывать только первым ходом, но гарантированно выигрывает первым или вторым.

Что обычно меняется в автокоде

Сам каркас функции почти всегда остаётся тем же.

Под конкретное условие меняются:

порог окончания игры — здесь 229;
команды хода — здесь +1 и ×2;
диапазон допустимых значений S;
значения m в строках для заданий 19–21.

def f(k, m):
    if k >= 229:
        return m % 2 == 0

    if m == 0:
        return 0

    h = [f(k + 1, m - 1), f(k * 2, m - 1)]

    return any(h) if m % 2 != 0 else all(h)

Главное для запоминания

any() — существует хотя бы один подходящий ход.

all() — подходят все варианты соперника.

Остальное в основном подстраивается под конкретное условие игры.

Видео разбор

Так-же все основные прототипы с реального экзамена разбираются в видео

1. Введение

2. Теория и разбор условия

Условие игры

Что значит «выигрышная стратегия»

Что проверяется

Главный вопрос

Логика каждого номера

3. Базовый код и разбор

Как перенести условие в функцию

Как понять or и and

Что означают True и False

Задание 19

Что отвечает за что

Как меняется решение задания 20

Как меняется решение задания 21

Короткая памятка по заданиям 20 и 21

4. Что может попасться в задании

4.1. Базовая задача: одна куча растёт

4.2. Одна куча уменьшается

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

Не меняем вслепую

Что требуется в №19

Важно различать округление

4.3. Задача с двумя кучами

Особенность задания 19

Задания 20 и 21 с двумя кучами

Задание 20

Задание 21

5. Автокод

Что означают k и m

Проверка окончания игры

Ограничение количества ходов

Все возможные ходы

Зачем нужны any() и all()

Почему выбор зависит от чётности m

Задание 19

Задание 20

Задание 21

Что обычно меняется в автокоде

Главное для запоминания

Видео разбор

Читайте также

Задание 25 ЕГЭ информатика

Задание 22 ЕГЭ информатика

Задание 3 ЕГЭ информатика