21 задание ЕГЭ информатика
Теория игр: дерево игры, стратегия Вани
1 балл ≈ 11 мин уровень В Дерево игры, выигрышная стратегия
Задание 21 – найти значение S, при котором у Вани есть стратегия выиграть первым или вторым ходом при любой игре Пети, и при этом нет стратегии гарантированно выиграть первым ходом. 1 балл.
Логика
- Позиция L2 – все ходы из неё ведут в W1 или W2, причём хотя бы один – в W2 (иначе это L1).
- С функцией f из задания 19: f(s) == −2.
print(min(s for s in range(1, 29) if f(s) == -2))Разобранный пример (ходы +1 или ×2, финиш при s ≥ 29). W1: s ≥ 15. L1: 14. W2: 7 и 13. L2 – все ходы ведут в W1 или W2, хотя бы один в W2: s = 12 → 13 (W2) или 24 (W1). Ваня выиграет: если Петя сделал 24 – сразу (×2), если 13 – Ваня идёт в 14, и Петя проигрывает. Ответ: 12.
Дерево игры для проверки. Нарисуй: корень – S, ветки – все ходы Пети, из каждой – выигрышный ход Вани (один), затем все ходы Пети, затем выигрышный ход Вани. Если все листья – победы Вани, стратегия верна.
Ловушки: взять s, где Ваня всегда выигрывает первым ходом (это L1 – не подходит по второму условию); «минимальное» или «максимальное» значение – читай условие; в некоторых вариантах спрашивают все такие значения.
- L2 = все ходы в W1/W2 и хотя бы один в W2.
- Одна функция f для всех трёх заданий: 19 → −1, 20 → 2, 21 → −2.
- Нарисуй дерево хотя бы для одного найденного значения – это быстрая проверка.
Разобранные задания 21 из открытого банка ФИПИ
Пример 1 · код ФИПИ Fc92eA
Для игры, описанной в задании 19, найдите наименьшее значение S, при котором одновременно выполняются
два условия:
у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Показать ответ и решение
Ответ: 50
Игра: две кучи (13, S), +3 или ×2, конец при сумме ≥ 135.
Все ходы Пети ведут в позиции, выигрышные для Вани за 1 или 2 хода, и хотя бы один – в позицию, где Ваня выигрывает только вторым ходом.
Перебор программой: 50.
Пример 2 · код ФИПИ 021805
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
Показать ответ и решение
Ответ: 18
Игра: две кучи (6, S), +1 или ×3, конец при сумме ≥ 65.
Все ходы Пети ведут в позиции, выигрышные для Вани за 1 или 2 хода, и хотя бы один – в позицию, где Ваня выигрывает только вторым ходом.
Перебор программой: 18.
Пример 3 · код ФИПИ 103027
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Показать ответ и решение
Ответ: 102
Игра: −2, −4, :4, конец при ≤ 23.
Все ходы Пети ведут в позиции, выигрышные для Вани за 1 или 2 хода, и хотя бы один – в позицию, где Ваня выигрывает только вторым ходом.
Перебор программой: 102.
Частые вопросы о задании 21
Сколько баллов даёт задание 21 ЕГЭ по информатике?
Максимум – 1 первичный балл. Норма времени на экзамене – около 11 мин. Уровень сложности – В.
Что проверяет задание 21?
Задание 21 – найти значение S, при котором у Вани есть стратегия выиграть первым или вторым ходом при любой игре Пети, и при этом нет стратегии гарантированно выиграть первым ходом. 1 балл.
Как подготовиться к заданию 21?
Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.