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

Что проверяет: Теория игр: стратегия второго игрока

Задание 21 ЕГЭ по информатике проверяет тему «теория игр: стратегия второго игрока». Ниже вы найдёте 1 вариант с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.

Ответ

132

Теория к заданию 21 ЕГЭ по информатике. Теория игр: стратегия второго игрока

Завершение игрового блока: нужно найти позицию, при которой выигрывает второй игрок.

Что нужно знать

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

Стратегия второго игрока

Второй игрок выигрывает, если исходная позиция проигрышна для первого: все его ходы ведут в выигрышные позиции второго.
Разбор ведётся тем же деревом, но классы позиций считаются с точки зрения второго игрока.
Сначала найдите все позиции П₁: из них первый игрок проигрывает при правильной игре противника.
Затем проверьте, попадает ли заданная позиция в этот класс.
Для полного ответа нужно описать стратегию: какой именно ход делает второй игрок в ответ на каждый ход первого.
Дерево игры удобно рисовать не полностью, а только по выигрышным веткам второго игрока.
Эксперт засчитывает ответ, только если показано, что стратегия работает против любого хода первого игрока.
Проверьте, что игра действительно заканчивается за указанное число ходов.

Как решать задание 21

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

Разбор примера

Как оформляется ответ на задание про выигрыш второго игрока.

Строим таблицу позиций от конечного условия назад, помечая каждую как выигрышную или проигрышную для того, кто ходит.
Находим позиции, помеченные как проигрышные для ходящего: именно они дают победу второму игроку.
Проверяем, что заданное в условии значение попало в этот класс.
Описываем стратегию: перечисляем все возможные ходы первого игрока и указываем ответный ход второго.
Показываем, что после ответного хода позиция снова становится проигрышной для первого.
Доводим разбор до конца игры и записываем ответ.

Ответзначение S и описание стратегии

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

Останавливаются на первом подходящем значении, не проверив второе условие.
Смешивают роли игроков при построении дерева.

Задание 21 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.