Задание 19: Теория игр: выигрыш за один ход

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

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

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

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

  • Позиция выигрышная, если из неё есть ход в проигрышную; проигрышная — если все ходы ведут в выигрышные.
  • Конечная позиция (игра закончена) — выигрыш того, кто сделал последний ход.
  • «Неудачный ход Пети» — любой ход Пети, после которого Ваня может выиграть сразу (даже если у Пети был лучший ход).
  • Решение кодом: рекурсивная функция f(позиция, ходов_осталось), возвращающая, выигрывает ли нужный игрок за заданное число ходов.
  • Для одной кучи с ходами «+1» и «×2» и порогом S: из позиции x выигрывают за один ход, если 2x ≥ S (удвоение даёт наибольший прирост).

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

  1. Выпиши правила: возможные ходы, условие окончания (сумма ≥ S и т. п.).
  2. Найди позиции, из которых можно выиграть одним ходом.
  3. Найди позиции Пети, из которых есть ход в такие позиции (ход Пети «неудачный»).
  4. Выбери значение по вопросу (минимальное S, минимальное x).

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

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

Пример 1

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

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

Ответ: 2

Ступень 1. Положение игры задаётся одним числом — сколько камней в куче сейчас. Из положения S ходы ведут в S + 1 и в S × 3; если хоть один ход сразу даёт не меньше 19 камней, ходящий выигрывает на месте. Ступень 2. Разбирай положения с конца, от 18 к 1. Положение выигрышное, если из него есть ход в проигрышное положение соперника или сразу за черту. Положение проигрышное, если оба хода ведут только в выигрышные положения соперника. Ступень 3. Вопрос задан про Ваню, а Ваня ходит вторым. Значит, искать надо те S, которые ПРОИГРЫШНЫ для того, кто ходит из них первым: в таком положении у Пети нет ни одного спасительного хода. Ступень 4. Пройди весь диапазон от 4 до 10 — всего 7 значений. Проигрышными для Пети оказались 4, 6 — это 2 значения. Ступень 5. Тот же счёт тремя независимыми способами (разбор положений с памятью, обратная динамика по массиву положений и полное развёртывание дерева игры без памяти) даёт 2. Ответ: 2.

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

Пример 2

В игре две кучки камней. В первой кучке находится x камней, во второй — 7 камней. За один ход игрок может добавить 1 камень в одну из кучек или увеличить количество камней в одной из кучек в 2 раза. Игра заканчивается, когда общее количество камней становится не менее 20. Найди, сколько существует значений x от 1 до 12 (при них игра в начальной позиции ещё не закончена), при которых Петя может выиграть своим первым ходом.

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

Ответ: 7

При добавлении одного камня в любую кучку: x+8≥20, поэтому x≥12. При удвоении первой кучки: 2x+7≥20, поэтому x≥7. При удвоении второй кучки: x+14≥20, поэтому x≥6. Выигрыш первым ходом возможен при x ≥ 6. Кроме того, игра должна быть ещё не закончена: x + 7 < 20, то есть x ≤ 12. Подходят x от 6 до 12: 12−6+1 = 7. Ответ: 7.

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

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

  • Требуют, чтобы Ваня выигрывал при любом ходе Пети, а в № 19 достаточно одного неудачного хода.
  • Неверно задают условие окончания (≥ вместо >).
  • Путают кучи в позициях с двумя кучами.
  • Забывают, что ход может быть сделан в любую из куч.

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

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

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

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

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

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

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

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