Теория игр в ЕГЭ по информатике (задания 19–21): как решать без путаницы

12 октября 2026 г. · 5 мин чтения · Редакция Skill Unit

Игры считаются сложными, но чаще всего ученики путаются не в вычислениях, а в словах. «Выигрывает вторым ходом» при любой игре соперника? Или хотя бы в одной ветке? Эти формулировки определяют ответ. Разберём логику на простой игре, потом на игре с двумя кучами, как в заданиях 19–21.

Понятия: позиция, ход, выигрышная и проигрышная

Позиция — полное описание того, что на столе, например число камней в куче. Ход переводит одну позицию в другую. Побеждает тот, после чьего хода выполнено условие. В задачах про камни это почти всегда «общее число камней стало не меньше порога». Слова «не меньше» значат ≥: граница включается, и при пороге 40 позиция с 40 камнями уже победная.

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

Простая игра: считаем с конца

Одна куча из s камней. За ход можно добавить 2 камня или утроить число камней. Побеждает тот, после чьего хода в куче не менее 40 камней.

• Любая куча от 14 камней выигрышная: утроение даёт 42 и больше.
• s = 13: ход «плюс 2» даёт 15, из которой соперник утраивает и получает 45. Ход «утроить» даёт 39, из которой соперник добавляет 2 и получает 41. Оба хода отдают победу, значит 13 проигрышная.
• s = 12: ходы ведут в 14 и 36, обе позиции выигрышные для соперника, значит 12 проигрышная.
• s = 11: ход «плюс 2» ведёт в проигрышную для соперника 13, значит 11 выигрышная.

Идём вниз по значениям и записываем вердикт для каждого s. Считать нужно именно с конца: ходы только увеличивают кучу, поэтому значения больше s к этому моменту уже известны.

Игра с двумя кучами и параметром S

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

Позиция теперь пара (a, b), победа проверяется по сумме a + b. Из каждой позиции у игрока четыре хода: плюс 5 к первой, плюс 5 ко второй, утроить первую, утроить вторую. Бумажное дерево глубже двух ходов рисовать не нужно: при глубине два в нём 16 партий, при глубине четыре уже 256.

Задание типа 19: два условия

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

• Условие на Петю. Его самый сильный ход даёт сумму 3S + 3. Она должна быть меньше 40, значит S ≤ 12.
• Условие на Ваню. После каждого хода Пети Ваня должен суметь дойти до порога. После «плюс 5 к первой» позиция (S + 5, 3), лучший ответ — утроить первую: 3S + 18 ≥ 40, откуда S ≥ 8. После «плюс 5 ко второй» позиция (S, 8): утроить первую даёт 3S + 8 ≥ 40, откуда S ≥ 11. После «утроить первую» позиция (3S, 3): утроение первой даёт 9S + 3 ≥ 40, откуда S ≥ 5. После «утроить вторую» позиция (S, 9): 3S + 9 ≥ 40, откуда S ≥ 11.

Итог: нужно одновременно S ≤ 12 и S ≥ 11. Подходят значения 11 и 12: наибольшее 12, наименьшее 11.

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

Когда ходов много: универсальная функция

Неравенствами удобно рассуждать, пока ходов мало. Если глубже на ход или множители разные, надёжнее написать функцию win(p, left): может ли игрок, который ходит из позиции p, гарантированно выиграть не позже чем своим left-м ходом при любой игре соперника. Игрок пробует каждый ход q. Если q сразу даёт победу, возвращаем True. Иначе, если ходы ещё остались, смотрим все ответы соперника: ход q хорош, если ни один ответ не побеждает сразу и после любого ответа игрок снова выигрывает за left − 1 ходов.

Через win записываются все типы условий. Тип 19 для начальной позиции — «ходящий проигрывает в пределах одного хода соперника». Тип 20 в строгой формулировке — для каждого хода q выполнено not win(q, 1) и win(q, 2). Тип 21 шире: он включает значения типа 20, потому что «выигрывает не позже второго хода» допускает ветки, где можно выиграть и первым.

Ловушки

• Граница порога: «не менее 40» — это >= 40, а не > 40.
• Ходы в разные кучи: «добавить в любую кучу» — два хода, а не один.
• Квантор: «при любой игре Пети» — это all(...), а не any(...).
• Диапазон S: начальная позиция не должна быть победной сразу.
• Глубина: win(p, 2) уже включает победу за один ход, поэтому для строгого типа нужно добавлять not win(q, 1).

Что делать дальше

Решите игру Б бумагой, а затем напишите функцию и сравните ответы: у вас должны получиться те же 11 и 12. После этого поменяйте параметры (порог, добавку, множитель) и убедитесь, что программа справляется. В курсе «ЕГЭ по информатике» на Skill Unit теории игр посвящён отдельный урок с готовыми листингами на Python, практикой и проверкой.