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

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

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

4 варианта с ответами

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из кучи 3 камня; убрать из кучи 5 камней; уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего). Например, из кучи в 20 камней за один ход можно получить кучу из 17, 15 или 5 камней. Игра завершается, когда количество камней в куче становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 30 или менее камней. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное значение 5, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом

Текст распознан с изображения задания. Формулы, таблицы и рисунки смотрите на картинке ниже.

ЕГЭ по информатике: задание 19, условие
Ответ
124

Петя и Ваня играют в следующую игру. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней в куче на 1, увеличить на 2 или удвоить. Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 65 или больше камней. В начальный момент в куче было S камней, S < 65.

Укажите наименьшее значение S, при котором Петя может выиграть своим первым ходом.

Ответ
33

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

Самый «сильный» ход — умножение, оно растит кучу быстрее прибавления. Перебирая S по возрастанию, находим наименьшее, при котором такой ход уже достигает цели: это 33. Ответ — 33.

Петя и Ваня играют в следующую игру. Перед ними лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней в куче на 1, увеличить на 3 или удвоить. Игра завершается в тот момент, когда количество камней в куче становится не менее 49. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 49 или больше камней. В начальный момент в куче было S камней, S < 49.

Укажите наименьшее значение S, при котором Петя может выиграть своим первым ходом.

Ответ
25

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

Самый «сильный» ход — умножение, оно растит кучу быстрее прибавления. Перебирая S по возрастанию, находим наименьшее, при котором такой ход уже достигает цели: это 25. Ответ — 25.

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

Укажите наименьшее значение S, при котором Петя может выиграть своим первым ходом.

Ответ
26

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

Самый «сильный» ход — умножение, оно растит кучу быстрее прибавления. Перебирая S по возрастанию, находим наименьшее, при котором такой ход уже достигает цели: это 26. Ответ — 26.

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

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

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

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

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

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

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

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

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

Ответ39

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

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