Задание 21 ЕГЭ по информатике 2027

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

Та же игра, что в задании 19. Высокий уровень: нужно найти значение, при котором Ваня выигрывает первым или вторым ходом при любой игре Пети, но не может гарантировать победу именно первым ходом; ответ — число, 1 балл.

Ответчисло в поле ответа
Баллы1 балл
Проверяетумение построить дерево игры и найти выигрышную стратегию второго игрока
Сколько времени закладыватьоколо 10 минут по спецификации ФИПИ

Какие бывают подтипы

Пример с полным разбором

Условие. В куче камней, . Петя и Ваня ходят по очереди, первым ходит Петя. За ход можно добавить в кучу один камень или увеличить число камней вдвое. Игра заканчивается, когда в куче становится 30 камней или больше; победил тот, кто сделал последний ход. Найдите наименьшее , при котором у Вани есть стратегия, позволяющая выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая гарантирует победу первым ходом.

  1. Разметка позиций для того, чей сейчас ход (она найдена в разборах заданий 19 и 20): из 15–29 он выигрывает одним ходом; из 14 любой его ход проигрывает; из 7 и 13 он выигрывает своим вторым ходом, оставив сопернику 14.
  2. Ване нужна куча, из которой любой ход Пети ведёт в позицию, выигрышную для Вани: в зону 15–29 или в 7 и 13.
  3. Куча 12: если Петя делает 13, Ваня добавляет камень, оставляет Пете 14 и выигрывает следующим ходом; если Петя делает 24, Ваня сразу удваивает до 48. Все ходы Пети проигрывают.
  4. Гарантии победить первым ходом у Вани нет: после хода Пети на 13 одним ходом до 30 не дотянуться.
  5. Для куч меньше 12 у Пети всегда есть ход, после которого Ваня за два хода не выигрывает: например, из 11 Петя сам ставит Ваню перед кучей 12. Это удобно проверить короткой программой-перебором.

Ответ: 12

Ещё задания с решением

Другие ходы

Условие.

Перед игрой в кучу кладут камней (). Игроки Петя и Ваня ходят по очереди, первым ходит Петя. Каждым ходом можно добавить в кучу один камень или увеличить количество камней в куче вдвое. Игра заканчивается, когда в куче становится 71 камень или больше; победил тот, кто сделал последний ход. При каком наименьшем одновременно верно: Ваня выигрывает первым или вторым ходом, как бы ни играл Петя, но гарантировать победу именно первым ходом Ваня не может?

Решение.

Сначала отметим кучи, из которых ходящий заканчивает партию одним ходом (нужно, чтобы в куче стало не меньше 71 камня). Из 36 ход «×2» даёт 72 — партия окончена, а из 35 ни один ход до конца не доводит. Значит, это все кучи от 36 до 70.

Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом.

Ход Пети в 34: сразу закончить Ваня не может, зато ходит в опорную позицию 35 и побеждает следующим ходом (36 → 72, 70 → 71).

Ход Пети в 66: Ваня сразу заканчивает партию.

На любой ход Пети у Вани есть ответ, а после хода в 34 немедленной победы нет — значит, гарантии победить именно первым ходом нет. Других подходящих значений нет.

Ответ: 33

Две кучи

Условие.

В первой куче 25 жетонов, во второй — жетонов (). Петя и Ваня ходят по очереди, первым ходит Петя. За один ход разрешено добавить в любую из куч один жетон или увеличить количество жетонов в любой из куч втрое. Партия заканчивается, как только в двух кучах суммарно окажется не меньше 145 жетонов; победителем считается тот, кто сделал последний ход. При каком наименьшем одновременно верно: Ваня выигрывает первым или вторым ходом, как бы ни играл Петя, но гарантировать победу именно первым ходом Ваня не может?

Решение.

Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом. Среди позиций, где в первой куче 25, опорных нет — они появляются только после первых ходов, их находим по ходу разбора.

Ход Пети в (26; 39): сразу закончить Ваня не может, зато ходит в опорную позицию (27; 39) и побеждает следующим ходом ((28; 39) → (28; 117), (27; 40) → (27; 120), (81; 39) → (243; 39), (27; 117) → (28; 117)).

Ход Пети в (25; 40): Ваня сразу заканчивает партию.

Ход Пети в (75; 39): Ваня сразу заканчивает партию.

Ход Пети в (25; 117): Ваня сразу заканчивает партию.

На любой ход Пети у Вани есть ответ, а после хода в (26; 39) немедленной победы нет — значит, гарантии победить именно первым ходом нет. Других подходящих значений нет.

Ответ: 39

Другие ходы

Условие.

Перед игрой в кучу кладут шашек (). Игроки Катя и Олег ходят по очереди, первой ходит Катя. Каждым ходом можно взять из кучи три шашки или уменьшить количество шашек в куче вдвое (при нечётном количестве в куче остаётся на одну шашку больше, чем забирают). Побеждает тот, после чьего хода в куче осталось не больше 29 шашек. При каком наибольшем одновременно верно: Олег выигрывает первым или вторым ходом, как бы ни играла Катя, но гарантировать победу именно первым ходом Олег не может?

Решение.

Сначала отметим кучи, из которых ходящий заканчивает партию одним ходом (нужно, чтобы в куче осталось не больше 29 шашек). Из 58 ход «вдвое» даёт 29 — партия окончена, а из 59 ни один ход до конца не доводит. Значит, это все кучи от 30 до 58.

Опорные позиции — те, из которых ходящий проигрывает сразу: партию одним ходом он не заканчивает, а после любого его хода соперник заканчивает её своим ходом.

Ход Кати в 122: сразу закончить Олег не может, зато ходит в опорную позицию 61 и побеждает следующим ходом (58 → 29, 31 → 28).

Ход Кати в 63: сразу закончить Олег не может, зато ходит в опорную позицию 60 и побеждает следующим ходом (57 → 29, 30 → 27).

На любой ход Кати у Олега есть ответ, а после хода в 122 немедленной победы нет — значит, гарантии победить именно первым ходом нет. Подходящих значений 6: 65, 66, 67, 123, 124, 125; наибольшее — 125.

Ответ: 125

Частые ошибки

Что нужно знать для задания 21

Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.

  1. Дерево игры: как его рисуют
  2. Разметка дерева снизу вверх
  3. Что требует задание 21
  4. Программа: два счётчика ходов
  5. Две кучи

Открыть темы в курсе

Ответы на частые вопросы

Сколько баллов за задание 21?
Один, если число совпало с верным. Уровень у задания высокий, но оценивается оно, как и все задания 1–25, одним баллом.
Нужно ли рисовать дерево игры в ответе?
Нет: проверяют только число в поле ответа. Дерево — способ решения на черновике, а записи в черновике не оцениваются.
Что такое дерево игры?
Схема возможных партий: из начальной позиции стрелки ведут к позициям после каждого хода, из них — к позициям после ответа соперника и так далее, пока кто-нибудь не выиграет.