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

Что проверяет: Теория игр: выигрышная стратегия

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

Ответ

124

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

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

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

Позиция выигрышная, если из неё есть ход в проигрышную для соперника позицию.
Позиция проигрышная, если любой ход ведёт в выигрышную для соперника позицию.
Анализ ведут от конечных позиций назад: сначала отмечают позиции, из которых игра завершается за один ход.
Ходы в этой игре уменьшают кучу, поэтому граф позиций конечен и его удобно строить таблицей.
Формулировка «не может выиграть за один ход, но проиграет вторым» задаёт конкретный тип позиции.

Язык теории игр

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

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

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

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

В куче S камней. За ход можно добавить 1 камень или увеличить количество вдвое. Выигрывает тот, после чьего хода в куче не менее 40 камней. Найдите наибольшее S, при котором первый игрок выигрывает первым ходом.

Первый игрок выигрывает первым ходом, если хотя бы один из двух ходов сразу даёт не менее 40 камней.
Ход «прибавить 1» даёт S + 1 ≥ 40, то есть S ≥ 39.
Ход «удвоить» даёт 2S ≥ 40, то есть S ≥ 20.
Значит, выигрыш первым ходом возможен при S ≥ 20.
Но при S ≥ 40 игра уже закончена до хода, поэтому наибольшее допустимое S равно 39.
Проверяем: при S = 39 ход «прибавить 1» даёт 40 камней и приносит победу.

Ответ39

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

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

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