Задания 19–21. Теория игр: выигрышная стратегия

Задания 19, 20 и 21 демонстрационного варианта ЕГЭ-2027 (ФИПИ) – три вопроса к одной игре.

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

• добавить в одну из куч (по своему выбору) 4 камня;
• увеличить количество камней в одной из куч (по своему выбору) в 2 раза.

Например, пусть в одной куче 20 камней, а в другой 30 камней; такую позицию в игре обозначим (20, 30). Тогда за один ход можно получить любую из четырёх позиций: (24, 30), (20, 34), (40, 30), (20, 60).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 133. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую игровую позицию, при которой в двух кучах суммарно 133 камня или больше. В начальный момент в первой куче было 17 камней, во второй куче – S камней; $1 \le S \le 115$.

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

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

Задание 20. Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 21. Найдите наименьшее значение S, при котором одновременно выполняются два условия:

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

1. Позицию и ход описывают две функции. Всё условие сводится к moves(pos) – списку позиций, куда можно сходить из текущей, и over(pos) – кончилась ли игра. Для двух куч позиция это кортеж (a, b), для одной кучи – просто число. Больше из текста условия извлекать нечего.
2. «Выиграть за k ходов» определяется через соперника. Ходящий выигрывает не более чем за $k$ ходов, если у него есть ход, который либо сразу заканчивает игру, либо ставит соперника в позицию, из которой тот проигрывает с запасом $k-1$. Ходящий проигрывает, если КАЖДЫЙ его ход не заканчивает игру и оставляет соперника выигрывающим. Отсюда пара взаимно рекурсивных функций win и lose: «существует ход» и «при любом ходе» – это они и есть.
3. Рекурсия зациклиться не может. На каждом уровне запас $k$ уменьшается, поэтому глубина дерева не больше $2k$, а $k$ в этих заданиях равно 1, 2 или 3. Ходов из позиции немного – четыре в игре с двумя кучами, три в игре с одной, – так что на одно значение S перебирается меньше сотни позиций. Ни мемоизация, ни динамическое программирование здесь не нужны.
4. Из начальной позиции ходит Петя. Поэтому вопрос про Ваню – это всегда lose для позиции Пети, а вопрос про Петю – win. Перепутанный ходящий – главный источник неверного ответа.
5. «Возможна» и «при любом ходе» – разные вопросы. Задание 19 демоверсии спрашивает про ситуацию, которая ВОЗМОЖНА: Петя мог сходить неудачно, и Ване хватило одного хода. Это any по ходам Пети, а не честный lose. Разница почти вдвое: если бы условие спрашивало гарантию – «при любом ходе Пети Ваня выигрывает первым», – ответом было бы 56, а не 29. Ходы Пети из позиции (17, 29) – в таблице ниже: в кучах 46 камней, и до порога Ваня дотягивается только в одной строке из четырёх.

Закончить игру Ваня может только после того, как Петя удвоит вторую кучу: в ней станет 58 камней, Ваня удвоит её ещё раз – 116, и вместе с первой кучей это ровно 133. После трёх остальных ходов Пети его потолок – 79, 83, 97, до 133 он не дотягивается. Поэтому задание 19 и говорит «ситуация возможна», а не «при любом ходе Пети».

Порядок действий: описать ходы в moves → описать конец игры в over → написать функции win и lose → перебрать S и выписать ответы на три вопроса. Как именно win и lose вызывают друг друга, разобрано сразу под программой.

Две функции win и lose. «Выигрывает» не свойство позиции: в позиции (17, 56) выигрывает тот, чья очередь ходить, и проигрывает тот, кто только что сходил. У каждой позиции два ответа, и какой из них нужен, решает не она, а то, чей сейчас ход. Передача хода сопернику – это переход в другую функцию, поэтому рекурсия тут взаимная: win зовёт lose, lose зовёт win.

win(pos, k) говорит про того, чья очередь ходить: «я выиграю не более чем за k своих ходов». Ему хватает одного удачного хода, поэтому цикл выходит по первому же успеху – return True. Это дословный перевод фразы из условия «игрок может выиграть»: может, значит существует ход.

lose(pos, k) говорит про него же обратное: «что бы я ни сделал, соперник закончит не позже своего k-го хода». Здесь одного хода мало, нужны все: любой контрпример – и позиция уже не проигрышная, поэтому цикл выходит по первой же неудаче – return False. Это перевод фразы «при любых ходах противника».

Отсюда и k – запас собственных ходов того, о ком идёт речь. В win игрок тратит ход и передаёт очередь: у соперника позиция nxt, а у него самого остаётся k - 1, поэтому вызывается lose(nxt, k - 1). В lose наоборот: ход переходит сопернику, который ещё ничего не потратил, поэтому win(nxt, k) – с тем же k. Пара строк if over(nxt) перед этим – это конец игры: тот, кто сходил в такую позицию, уже победил, и заглядывать дальше незачем.

Рекурсия конечна не потому, что кучи растут, а потому, что убывает k. Он уменьшается через уровень – в переходе win → lose, – так что глубина не превышает $2k$, а k в этих заданиях равен 1, 2 или 3. Дно – строка if k == 0: return False в win: ходов больше нет, выигрывать нечем. Отдельного дна у lose нет и не нужно: lose(pos, 0) сведётся к win(nxt, 0), то есть к False, и вернёт False – проиграть за ноль ходов соперника действительно нельзя, ему нужен хотя бы один.

Как это разворачивается. Возьмём S = 28 – первый ответ задания 20 – и посмотрим, что делает win((17, 28), 2). Ходит Петя, в кучах 45 камней, до порога далеко, поэтому ни один ход игру не заканчивает и каждый проверяется через lose(..., 1) – «попадёт ли Ваня в позицию, из которой проигрывает».

• lose((21, 28), 1) → False: Ваня спасается ходом в (25, 28), откуда Петя дотягивается лишь до 81 при пороге 133
• lose((17, 32), 1) → False: и здесь у Вани находится ответ, после которого Петя не добивает
• lose((34, 28), 1) → False: и здесь у Вани находится ответ, после которого Петя не добивает
• lose((17, 56), 1) → True: что бы Ваня ни ответил, у Пети есть добивающий ход:
  • Ваня ходит в (21, 56), Петя – в (21, 112), сумма 133
  • Ваня ходит в (17, 60), Петя – в (17, 120), сумма 137
  • Ваня ходит в (34, 56), Петя – в (34, 112), сумма 146
  • Ваня ходит в (17, 112), Петя – в (21, 112), сумма 133

Три первые ветки вернули False, четвёртая – True, значит и win((17, 28), 2) истинно. А win((17, 28), 1) ложно: одним ходом Петя добирается самое большее до 73, а порог – 133. Это и есть вторая половина условия задания 20: «Петя не может выиграть за один ход».

Важно, в каком порядке это считается: win не строит всё дерево заранее, а идёт по ходам слева направо и останавливается на первом, который вернул True. Поэтому до последней ветки он доходит, только если три первые провалились.

И последнее – откуда в программе берутся сами вопросы. Каждое слово условия превращается в одну деталь вызова:

Ровно поэтому три задания решаются одной программой: меняется не код, а строка с вызовом.

Под функциями стоят три print, и каждый занимает две строки с for, if и скобками. Разбираются они одинаково: перебрать S → отсеять неподходящие → выдать то, что просят. Вот самая простая из трёх, ответ задания 20, записанная обычным циклом:

good = []
for s in range(1, 116):                      # S из условия
    if win((17, s), 2) and not win((17, s), 1):
        good.append(s)                       # подходит
print(good[:2])

Генератор из блока Решение – ровно этот цикл, записанный в одну строку. Читать его тоже удобно кусками, и каждый кусок отвечает своей части условия:

Где min, там квадратных скобок нет. min умеет работать с генератором – ему не нужен готовый список, он идёт по значениям и держит наименьшее. Списком отвечает только задание 20: там просят два числа, а из генератора срез не взять.

Строка задания 19 – единственная с двумя переборами. Вопрос там не про позицию, а про то, что у Пети нашёлся неудачный ход, поэтому внутри фильтра перебираются ещё и ходы Пети:

good = []
for s in range(1, 116):
    for p in moves((17, s)):        # четыре хода Пети
        if not over(p) and win(p, 1):   # игру он не кончил,
            good.append(s)              # а Ваня кончит
            break                       # хватит одного хода
print(min(good))

any(...) в одну строку делает то же, что этот внутренний цикл с break: доходит до первого истинного условия и останавливается. Читается он в том же порядке, в каком написан: «существует ли ход p из moves((17, s)), такой что игра им не кончилась и Ваня выигрывает следующим».

В однокучной задаче эти же три строки короче ровно на одну деталь: позиция там число, поэтому вместо (17, s) всюду стоит s, а range берётся из своего условия. Больше ничего в них не меняется.

Второй пример – задача из нашего банка, тоже про выигрышную стратегию, но куча одна.

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

• убрать из кучи 3 камня;
• убрать из кучи 5 камней;
• уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).

Например, из кучи в 20 камней за один ход можно получить кучу из 17, 15 или 5 камней. Игра завершается, когда количество камней в куче становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 30 или менее камней. В начальный момент в куче было S камней, $S \ge 31$.

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

В коде поменялись ровно две функции.

• позиция стала числом, а не кортежем, и moves вернул список из трёх чисел вместо четырёх пар;
• «камней стало не более 30» – это pos <= END, и знак неравенства противоположен демоверсии: куча убывает, а игра заканчивается на маленьком числе;
• деление с округлением вниз – это pos // 4, а не pos / 4: обычное деление даёт дробь, и позиция перестаёт быть целым числом;
• win и lose не тронуты вообще – их и стоит запомнить наизусть.

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

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

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

1. Перепутали «существует» и «для любого». Квантор задаёт место return: True внутри цикла и False после него – «существует»; наоборот – «для любого». Переставили – вместо win получили lose.
2. Перепутали, кто ходит. Вопрос про второго игрока – это lose для позиции первого. Ошибка сдвигает всё ровно на один ход.
3. Взяли половину условия. Вторая часть – запрет: выигрыш за два хода включает и того, кто выигрывает сразу, и без отрицания в ответ попадают лишние значения.
4. «Выиграл» – не то же, что «имеет выигрышную стратегию». Первое – возможность: соперник мог сходить неудачно. Второе – гарантия при любой его игре.