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

Что проверяет: Теория игр: выигрыш вторым ходом

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

Ответ

127 128

Теория к заданию 20 ЕГЭ по информатике. Теория игр: выигрыш вторым ходом

Продолжение игрового блока: нужно найти значения, при которых первый игрок выигрывает своим вторым ходом.

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

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

Разбор позиции В₂

Выигрыш вторым ходом означает: сам первый игрок сразу не выигрывает, но после любого ответа противника у него есть победный ход.
Формально: позиция не В₁, но существует ход в позицию, все продолжения которой ведут в В₁ для первого игрока.
Сначала выпишите множество позиций В₁ из задания 19: они нужны как опора.
Затем выпишите позиции П₁: из них любой ход попадает в В₁ противника.
Из позиции В₂ есть ход в П₁.
Удобно вести таблицу: значение S, ходы, класс позиции.
Ответов обычно два, поэтому не останавливайтесь, найдя первый.
Проверяйте каждый найденный ответ, проигрывая партию до конца за обоих игроков.

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

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

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

Продолжение игры с порогом 40 камней и ходами «прибавить 1» и «удвоить». Как найти позиции, в которых первый игрок выигрывает вторым ходом?

Из задания 19 известно: позиции с S от 20 до 39 относятся к В₁.
Ищем позиции П₁: такие S, что и S + 1, и 2S попадают в диапазон от 20 до 39.
Условие: S + 1 ≥ 20 и 2S ≤ 39, то есть S ≥ 19 и S ≤ 19,5.
Целое решение одно: S = 19. Это позиция, из которой любой ход отдаёт победу противнику.
Теперь ищем В₂: такие S, из которых есть ход ровно в 19.
Ход «прибавить 1» даёт 19 при S = 18; ход «удвоить» не даёт нечётного 19. Значит, ответ S = 18.

Ответ18

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

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

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