Сколько баллов дают за задание 20 ЕГЭ по информатике?

До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — повышенный.

Сколько времени тратить на задание 20?

Примерное время выполнения по спецификации ФИПИ — 7 минут; на весь экзамен отводится 235 минут.

Где потренироваться на задании 20?

В тренажёре «Ранга» по этому номеру сейчас 30 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Задание 20: Теория игр: стратегия первого игрока за два хода

Теория к заданию № 20 ЕГЭ-2027 по информатике: коротко правило, приём решения по шагам, два разобранных примера из банка «Ранга» и ошибки, на которых теряют балл.

Что проверяет задание 20

Что проверяет: Умение найти выигрышную стратегию игры: значения, при которых Петя не может выиграть первым ходом, но выигрывает вторым ходом при любой игре Вани.
Баллы: до 1 балл из 29 первичных
Уровень: повышенный
Время: около 7 минут (примерное время по спецификации ФИПИ; на весь экзамен — 235 минут)
Формат: краткий ответ; решается и без программы

Правило и теория

Петя выигрывает за 2 хода из позиции P, если: он не выигрывает за 1 ход, и есть его ход в позицию Q, из которой любой ход Вани ведёт в позицию, где Петя выигрывает за 1 ход.
Позиции «выигрыш за 1 ход» и «проигрыш за 1 ход» удобно найти сначала, а затем строить уровни дальше.
Рекурсия: win(p, k) — может ли игрок, делающий ход, выиграть не более чем за k своих ходов.
В ответе обычно два значения в порядке возрастания.

Приём решения по шагам

Найди все позиции, где выигрыш одним ходом.
Найди позиции, из которых любой ход ведёт в «выигрыш одним ходом» соперника, — это проигрышные для ходящего.
Позиции Пети, из которых есть ход в такую проигрышную позицию, — выигрыш за 2 хода; исключи выигрывающие за 1 ход.
Выпиши подходящие значения по возрастанию.

Два разобранных примера из банка «Ранга»

Сначала реши сам — потом раскрой ответ и разбор. Ответы взяты из банка, по которому работает тренажёр, и проверены.

Пример 1

Два игрока, Петя и Ваня, играют в следующую игру. Перед ними две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 51. Победителем считается игрок, сделавший последний ход. В начальный момент в первой куче было 5 камней, во второй куче — S камней; 1 ≤ S ≤ 45. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Найди два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: Петя не может выиграть за один ход; Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. В ответе запиши найденные значения в порядке возрастания через пробел.

Показать ответ и разбор

Ответ: 20 22

Позиции, где Петя выигрывает вторым ходом: из (5; S) есть ход в позицию, где любой ход Вани даёт Пете выигрыш одним ходом. Перебор S программой: подходят 20, 22. Два наименьших — 20 22. Ответ: 20 22.

Карточка банка «Ранга» informatics-20-5 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Пример 2

Петя и Ваня играют в такую игру. Перед ними куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход можно добавить в кучу один камень или увеличить количество камней в куче в 3 раза. Игра заканчивается, когда камней становится не меньше 35. Выигрывает тот игрок, после хода которого в куче оказалось не меньше 35 камней. Найди наименьшее начальное количество камней S, при котором выполняются сразу два условия: своим первым ходом Петя выиграть не может, но при любой игре Вани Петя выигрывает своим вторым ходом. Ответ — целое число.

Показать ответ и разбор

Ответ: 10

Ступень 1. Разбери условие по частям. «Первым ходом выиграть нельзя» значит, что ни S + 1, ни S × 3 не дают 35 камней и больше. «Выигрывает вторым ходом при любой игре Вани» — значит, есть такой первый ход Пети, что после ЛЮБОГО ответа Вани Петя закрывает игру одним ходом. Ступень 2. Перебирай S по возрастанию, с 1. Для каждого S сначала проверь первую часть условия: если игра кончается первым же ходом, такое S не подходит, и дальше смотреть нечего. Ступень 3. Для оставшихся S разверни дерево на два своих хода. Ход Пети годится, когда оба ответа Вани оставляют положение, из которого есть ход сразу за черту 35. Если хоть один ответ Вани ломает это — ход не годится, нужен другой. Ступень 4. Наименьшее подходящее значение — S = 10. Ходы Пети из него ведут в 11, 30, и спасительным оказался ход в 11: оба ответа Вани оставляют Пете ход за черту. Частая потеря балла здесь — взять первое же S, где Петя вообще выигрывает: условие требует победы именно вторым ходом, а не любой. Ступень 5. Тот же отбор тремя независимыми способами (разбор положений с памятью, таблица выигрышных положений с перебором пар ходов и развёртывание дерева игры на два хода без таблиц) даёт S = 10. Ответ: 10.

Карточка банка «Ранга» informatics-20-8 — авторское тренировочное задание в формате ЕГЭ, ключ проверен. Решить похожее в тренажёре

Типичные ошибки

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

Тренироваться: 30 заданий этого номера

Тренажёр «Ранга»: условие, проверка ответа сразу и разбор по шагам. Первое задание — без регистрации, дальше — в кабинете ученика.

Решать задание 20

Кабинет ученика · Разбор задания 20: 10 примеров

Частые вопросы о задании 20

Сколько баллов дают за задание 20 ЕГЭ по информатике?: До 1 балл из 29 первичных баллов (проект спецификации КИМ ЕГЭ-2027 ФИПИ). Уровень сложности — повышенный.
Сколько времени тратить на задание 20?: Примерное время выполнения по спецификации ФИПИ — 7 минут; на весь экзамен отводится 235 минут.
Что проверяет задание 20?: Умение найти выигрышную стратегию игры: значения, при которых Петя не может выиграть первым ходом, но выигрывает вторым ходом при любой игре Вани.
Где потренироваться на задании 20?: В тренажёре «Ранга» по этому номеру сейчас 30 заданий с проверкой ответа и разбором; первое задание открывается без регистрации.

Источник: ФИПИ — демоверсии, спецификации, кодификаторы ЕГЭ, архив материалов 2027 года (проект спецификации и демоверсии КИМ ЕГЭ-2027 ФИПИ по информатике (опубликован как проект; 27 заданий, 29 первичных баллов, экзамен на компьютере)).

Тексты теории — авторские материалы «Ранга». Примеры — авторские тренировочные задания в формате ЕГЭ, не официальные задания ФИПИ. Мы не обещаем конкретных баллов: результат зависит от твоей работы.