Задания 19–21 на ЕГЭ по информатике посвящены теории игр с кучами камней:
- Задание 19 (базовый уровень, 6 минут): Анализ алгоритма игры. Нужно понять, как работает игра и каковы последовательности ходов игроков.
- Задание 20 (повышенный уровень, 8 минут): Поиск выигрышной стратегии. Требуется определить, какой ход гарантирует победу игроку, независимо от действий соперника.
- Задание 21 (высокий уровень, 11 минут): Построение дерева игры и определение стратегии победы. Необходимо рассмотреть все возможные варианты развития игры и выбрать оптимальную стратегию.
Во всех этих задачах игроки работают с одной или двумя кучами камней, выполняя поочерёдно разрешённые действия (например, добавление одного камня или удвоение количества камней в куче). Задача состоит в том, чтобы определить, с каким начальным числом камней один из игроков гарантированно победит при использовании выигрышной стратегии.
Как правило, первым ходит Петя (П), а вторым – Ваня (В). Выигрышная стратегия – это последовательность ходов, которая обеспечивает победу независимо от действий противника.
Решение этих задач очень просто выполнять с помощью кода на Python, который рассмотрим дальше. Разобравшись с ним, можно быстро анализировать все возможные игровые позиции и находить правильные ответы с минимальными усилиями.
Примеры заданий взяты из открытого варианта ЕГЭ, опубликованного на сайте Федерального института педагогических измерений (ссылка на файл).
Решение задания 19 из демоверсии ФИПИ
Задание 19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 59 или больше камней.
В начальный момент в первой куче было пять камней, во второй куче – S камней; 1 ≤ S ≤ 53.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
Итак, рассмотрим игру, в которой участвуют два игрока: Петя и Ваня. Они ходят по очереди следующим образом:
- Петя делает первый ход, затем ходит на третьем, пятом, седьмом и так далее (на нечётных ходах).
- Ваня ходит вторым, четвёртым, шестым и так далее (на чётных ходах).
Для реализации алгоритма решения задачи создадим рекурсивную функцию f(a, b, n = 0), где:
a– количество камней в первой куче;b– количество камней во второй куче;n– номер текущего хода (по умолчанию равен 0).
Если же игра предполагает работу только с одной кучей, функция будет иметь вид:PythonКопировать
def f(a, n = 0):Этот подход позволяет отслеживать состояние игры и определять, чей ход сейчас происходит, используя параметр n:
- Если
nнечётное (n % 2 == 1), ходит Петя; - Если
nчётное (n % 2 == 0), ходит Ваня.
Примеры:
n == 1– первый ход Пети;n == 2– первый ход Вани;n == 1 or n == 3– первый или второй ход Пети;n == 2 or n == 4– первый или второй ход Вани.
Таким образом, проверяя номер хода на чётность или нечётность, можно легко определить, чей сейчас ход.
Перейдём к описанию условий завершения игры. Игра заканчивается, когда суммарное количество камней в обеих кучах становится не менее 59:PythonКопировать
if a + b >= 59:Побеждает тот игрок, который сделал последний ход. Согласно условию, Ваня обладает выигрышной стратегией. Поскольку Ваня ходит на чётных номерах, мы возвращаем True в том случае, если последний (завершающий) ход был совершён на чётном значении n:PythonКопировать
if (a + b) >= 59:
return n % 2 == 0 # Если n чётное, то выигрывает ВаняКроме того, условие гласит, что Ваня выиграл на своём первом ходе. Это означает, что количество ходов, приводящих к победе, не может превышать двух. Поэтому, если номер хода больше 2, возвращаем False:PythonКопировать
if n > 2:
return FalseРассмотрим, какие варианты действий доступны игроку на каждом ходе, и как они изменяют состояние игры:
f(a + 1, b, n + 1)– добавляет в первую кучу (a) 1 камень;f(a, b + 1, n + 1)– добавляет во вторую кучу (b) 1 камень;f(a * 2, b, n + 1)– удваивает количество камней в первой куче (a);f(a, b * 2, n + 1)– удваивает количество камней во второй куче (b).
Кроме этого, каждая из функций увеличивает номер хода на 1.
Определение стратегии игроков
Теперь осталось записать стратегию игроков. В игре их можно выделить две:
1. Стратегия победителя (в данном случае её имеет Ваня). Если игрок имеет выигрышную стратегию, достаточно, чтобы хотя бы один из его возможных ходов привел к победе. В этом случае можно использовать функцию any(), чтобы проверить наличие хотя бы одного успешного хода:PythonКопировать
# any() возвращает True, если хотя бы один из вызовов функции вернул True
return any([f(a + 1, b, n + 1), f(a, b + 1, n + 1), f(a * 2, b, n + 1), f(a, b * 2, n + 1)])2. Стратегия противника (в данном случае её имеет Петя). Противник стремится блокировать все возможные пути к победе. Поэтому необходимо убедиться, что все его возможные ходы не дают сопернику выиграть. Здесь можно применить функцию all(), чтобы проверить, что каждый ход противника не приводит к победе соперника.PythonКопировать
# all() возвращает True, только если все вызовы функций вернули в качестве ответа True
return all([f(a + 1, b, n + 1), f(a, b + 1, n + 1), f(a * 2, b, n + 1), f(a, b * 2, n + 1)])Кроме этого, очень важно отметить, что если в условии задачи указано, что противник совершил неудачный ход, то в этом случае он также ходит через any(). Так как для победы игрока достаточно хотя бы одного неудачного хода противника:PythonКопировать
return any([f(a + 1, b, n + 1), f(a, b + 1, n + 1), f(a * 2, b, n + 1), f(a, b * 2, n + 1)])Поскольку в данной задаче оба игрока ходят через any(), их стратегию можно выразить одним общим выражением:PythonКопировать
# Проверяем, есть ли у противника неудачный ход
return any([f(a + 1, b, n + 1), f(a, b + 1, n + 1), f(a * 2, b, n + 1), f(a, b * 2, n + 1)])Функция готова, теперь переберём значения S. Из условия известно, что в первой куче 5 камней, а во второй – S камней. Найдём минимальное S, при котором выполняется условие f(5, s):PythonКопировать
for s in range(1, 54):
if f(5, s):
print(s)
break # Нужно первое выведенное значениеВ итоге получился следующий код:PythonКопировать
def f(a, b, n = 0):
# Так как Ваня выиграл своим первым ходом, общее число ходов не может превышать 2
if n > 2:
return False
# Проверяем, достигнута ли победная позиция
if (a + b) >= 59:
return n % 2 == 0 # Ваня (второй игрок) должен победит
# Возможные ходы
actions = [
f(a + 1, b, n + 1, m), # Добавить 1 камень в первую кучу
f(a, b + 1, n + 1, m), # Добавить 1 камень во вторую кучу
f(a * 2, b, n + 1, m), # Удвоить количество камней в первой куче
f(a, b * 2, n + 1, m) # Удвоить количество камней во второй куче
]
# Стратегия игроков
return any(actions)
# Перебираем возможные значения S и находим минимальное
for s in range(1, 54):
if f(5, s):
print(s)
break # Выводим первое найденное значение и останавливаем циклЭтот код находит наименьшее значение S, при котором Ваня выигрывает своим первым ходом.
Ответ: 14.
Решение задания 20 из демоверсии ФИПИ
Задание 20
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Чтобы решить задачу, нужно изменить код из задания 19 так, чтобы он удовлетворял новым условиям, где победителем должен оказаться Петя, поскольку у него есть выигрышная стратегия. При этом важно, что Петя ходит на нечётных ходах (1‑й, 3‑й, 5‑й и т.д.).
Ограничение по числу ходов. Если Петя выигрывает своим вторым ходом, игра должна завершаться до начала четвёртого хода. Иначе говоря, если количество совершённых ходов больше 3, победа для Пети уже невозможна, и функция должна вернуть False. Для этого в начале функции добавляем проверку:PythonКопировать
# Если число ходов больше 3, победа уже невозможна, возвращаем False
if n > 3:
return FalseОпределение победы. Игра заканчивается, когда a + b >= 59. В этот момент необходимо вернуть результат, основываясь на следующих правилах:
- Если игра завершается на первом ходе (
n == 1): По условию Петя не может выиграть сразу с первого хода, поэтому функция должна вернутьFalse. - Если игра завершается на любом другом ходе: Победа засчитывается, если последний ход выполнил Петя, а значит, номер хода должен быть нечётным (
n % 2 == 1). Если последний ход сделал Ваня (номер хода чётный), функция вернётFalse.
Пример кода для определения победы:PythonКопировать
# Проверяем, достигнута ли условие победы (сумма a + b >= 59)
if (a + b) >= 59:
# Если игра завершается на первом ходе, Петя не может сразу выиграть
if n == 1:
return False
# Если последний ход сделан Петей (номер хода нечётный), возвращаем True, иначе – False
return n % 2 == 1Стратегия игры. При выборе стратегии учитываем два важных момента:
- Петя имеет выигрышную стратегию: Это означает, что если существует хотя бы один ход, который приводит к победе, Петя может его выбрать. Поэтому для его хода используем функцию
any(), которая возвращаетTrue, если хотя бы один из вариантов успешен. - Ваня выступает в роли противника: Он пытается заблокировать все варианты, по которым Петя мог бы выиграть. Поэтому для победы Пети стратегия должна работать для всех возможных ходов Вани. Здесь применяем функцию
all(), которая возвращаетTrueтолько если все варианты удовлетворяют условию победы для Пети.
Пример реализации стратегии:PythonКопировать
# Если сейчас ход Вани, проверяем, что при всех ответных ходах Вани Петя всё равно выигрывает
if n % 2 == 1:
return all(actions)
# Если ход принадлежит Пете, ему достаточно найти хотя бы один ход, ведущий к победе
return any(actions)Итоговый код для решения задания:PythonКопировать
def f(a, b, n = 0):
# Если число ходов больше 3, то победа уже невозможна, возвращаем False
if n > 3:
return False
# Проверяем, достигнута ли условие победы (сумма a + b >= 59)
if (a + b) >= 59:
# Если игра завершается на первом ходе, Петя не может сразу выиграть
if n == 1:
return False
# Если последний ход сделан Петей (номер хода нечётный), возвращаем True, иначе – False
return n % 2 == 1
# Создаём возможные варианты ходов
actions = [
f(a + 1, b, n + 1, m), # Добавить 1 камень в первую кучу
f(a, b + 1, n + 1, m), # Добавить 1 камень во вторую кучу
f(a * 2, b, n + 1, m), # Удвоить количество камней в первой куче
f(a, b * 2, n + 1, m) # Удвоить количество камней во второй куче
]
# Ход Вани
if n % 2 == 1:
return all(actions)
# Ход Пети
return any(actions)
# Перебираем все возможные значения s от 1 до 53
for s in range(1, 54):
# Проверяем, существует ли выигрышная стратегия для Пети при начальном значении (5, s)
if f(5, s):
print(s)Ответ: 24, 26.
Решение задания 21 из демоверсии ФИПИ
Задание 21
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе укажите наименьшее из них.
Решение таких задач сводится к последовательному переносу условий задачи в код на Python. Мы разбираем условия по порядку и записываем их в виде логики программы.
Согласно условию задачи, победителем должен быть Ваня. Поскольку Ваня ходит по чётным ходам (2-й, 4-й и так далее), его выигрышная стратегия выполняется, если номер последнего хода n – чётный.
На Python это можно записать так:PythonКопировать
# Проверяем, достигнуто ли условие победы (a + b >= 59)
# Если последний ход был за Ваней (n чётное), он выигрывает
if (a + b) >= 59:
return n % 2 == 0Кроме того, в условии говорится, что у Вани имеется выигрышная стратегия, позволяющая ему победить либо своим первым ходом (то есть, когда n = 2), либо вторым (то есть, когда n = 4) вне зависимости от действий Пети. При этом отсутствует стратегия, которая давала бы Ване возможность гарантированно выиграть уже на первом ходе.
Это означает, что необходимо:
- Определить все стратегии, при которых Ваня выигрывает на 2‑м или 4‑м ходе.
- Исключить те стратегии, которые позволили бы ему одержать победу сразу на первом ходе.
Для реализации этого введём дополнительный параметр m в функцию, ограничивающий максимальное число ходов:PythonКопировать
def f(a, b, n, m):
# Если текущий ход превышает допустимое значение m, возвращаем False
if n > m:
return FalseПри этом:
- Чтобы проверить, что Ваня не может выиграть за один ход, ограничиваем игру максимум 2 ходами (проверка выполняется вызовом
not f(5, s, 0, 2)). - Чтобы убедиться, что Ване доступна выигрышная стратегия для победы на первом или втором его ходе, игра должна завершаться не позднее 4‑го хода (проверка – вызовом
f(5, s, 0, 4)).
В цикле теперь необходимо одновременно учитывать эти два условия:
for s in range(1, 54):
"""
Проверяем два условия:
1. Ваня не может выиграть за один ход: not f(5, s, 0, 2)
2. Ваня имеет выигрышную стратегию для победы первым или вторым ходом: f(5, s, 0, 4)
"""
if not f(5, s, 0, 2) and f(5, s, 0, 4):
print(s)Что касается стратегии игроков внутри функции f:
- Ход Вани: Поскольку он имеет выигрушную стратегию, то ему достаточно, чтобы хотя бы один из вариантов хода приводил к победе. Для этого используем функцию
any(). - Ход Пети: Действуя как противник, он подбирает ходы так, чтобы помешать Ване выигрывать. Поэтому для гарантии победы Вани стратегия должна работать для всех вариантов ответного хода Пети – применяем функцию
all().
PythonКопировать
# Ход Пети
if n % 2 == 0:
return all(actions)
# Ход Вани
return any(actions)Итоговый код:PythonКопировать
def f(a, b, n, m):
# Если текущий ход превышает допустимое значение m, возвращаем False
if n > m:
return False
# Если достигнуто условие победы (сумма не меньше 59)
if (a + b) >= 59:
# Ваня выигрывает, если текущий ход чётный
return n % 2 == 0
# Создаём возможные варианты ходов
actions = [
f(a + 1, b, n + 1, m), # Добавить 1 камень в первую кучу
f(a, b + 1, n + 1, m), # Добавить 1 камень во вторую кучу
f(a * 2, b, n + 1, m), # Удвоить количество камней в первой куче
f(a, b * 2, n + 1, m) # Удвоить количество камней во второй куче
]
# Ход Пети
if n % 2 == 0:
return all(actions)
# Ход Вани
return any(actions)
# Перебираем возможные значения S (количество камней во второй куче) от 1 до 53
for s in range(1, 54):
"""
Проверяем два условия:
1. Ваня не может выиграть за один ход (то есть Петя ещё может играть после первого хода).
2. Ваня имеет выигрышную стратегию, позволяющую ему победить первым или вторым ходом,
независимо от действий Пети.
"""
if not f(5, s, 0, 2) and f(5, s, 0, 4):
print(s) # Выводим значения S, при которых у Вани есть выигрышная стратегияОтвет: 23.
Другие варианты условий для заданий 19–21
В некоторых вариантах заданий 19–21 встречаются условия, где необходимо учитывать предыдущий ход соперника и не повторять его для той же кучи. Давайте разберём один из таких вариантов и посмотрим, как он решается.Задание 20
Петя и Ваня решили поиграть. Перед ними находятся две кучи камней. Игроки ходят по очереди, первым ходит Петя. За один ход игрок может выполнить одно из двух действий:
- убрать ровно 4 камня из любой из куч;
- уменьшить количество камней в выбранной куче в 3 раза (с округлением в меньшую сторону).
Однако есть одно ограничение: нельзя повторять ход соперника, если он использовал его с той же кучей.
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда суммарное количество камней в обеих кучах становится 50 или меньше. Побеждает тот, кто сделал последний ход. В начале игры в первой куче лежит 70 камней, а во второй — S камней, где S > 1.
У игрока выигрышная стратегия, если он может победить при любых ходах противника.
Определите количество значений S, при котором у Пети есть выигрышная стратегия, при этом выполняются два условия:
- Петя не может выиграть за один ход;
- Петя выигрывает на втором ходу, независимо от того, как играет Ваня.
Решение:PythonКопировать
from math import floor # Импорт функции floor для округления в меньшую сторону
def f(a, b, n = 0, d =- 1):
"""
Рекурсивная функция для проверки выигрышной стратегии.
Параметры:
a – количество камней в первой куче;
b – количество камней во второй куче;
n – порядковый номер хода;
d – индекс последнего выполненного действия (для исключения повторов).
Функция возвращает True, если Петя выигрывает, иначе False.
"""
# Возможные ходы
actions = [
[a — 4, b, n + 1, 0]
, # убрать 4 камня из первой кучи
[a, b — 4, n + 1, 1]
, # убрать 4 камня из второй кучи
[floor(a / 3), b, n + 1, 2]
, # уменьшить первую кучу в 3 раза
[a, floor(b / 3), n + 1, 3]
# уменьшить вторую кучу в 3 раза ] # Если число ходов превысило 3, выиграть уже невозможно if n > 3: return False # Проверка условия окончания игры (сумма камней 30 или меньше) if (a + b) <= 50: # Возвращаем False, так как по условию задачи Петя не может выиграть в первом ходу if n == 1: return False # Возвращаем True, если последний ход был Петин return n % 2 == 1 # Исключаем повторение предыдущего хода на той же куче if d > -1: actions.pop(d) # Ход Пети if n % 2 == 1: return all(f(x, y, n, d) for x, y, n, d in actions) # Ход Вани return any(f(x, y, n, d) for x, y, n, d in actions) # Перебираем все возможные значения S для второй кучи и ищем выигрышные случаи for s in range(1, 100): if f(70, s): print(s) # Выводим значения S, при которых у первого игрока есть выигрышная стратегия
Ответ: 8.