2026. КЕГЭ № 21. Построение дерева игры по заданному алгоритму и поиск выигрышной стратегии игры
Тест проверяет умение строить дерево игры по заданному алгоритму. Соответствует спецификации ФИПИ.
Задание 1
В задаче 21 ЕГЭ по информатике, как правило, требуется найти значение П2: выигрыш Вани первым или вторым ходом, но не гарантированно первым. Это позиция, из которой...
Задание 2
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в меньшую кучу любое количество камней от одного до количества камней в этой куче. Изменять количество камней в большей куче не разрешается. Если кучи содержат равное количество камней, добавлять камни можно в любую из них. Игра завершается, когда общее количество камней в кучах становится более 39. Победителем считается игрок, сделавший последний ход, то есть первым получивший 40 или больше камней в двух кучах. В начальный момент в первой куче было 4 камня, а во второй — S камней, 1 ≤ S ≤ 35. Найдите минимальное значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. В ответ запишите только число.
Задание 3
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Найдите значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Если найдено несколько значений S, в ответе запишите минимальное из них.
Задание 4
Теория игр предполагает, что игроки делают ходы безошибочно. Это означает, что при наличии из текущей позиции ходов на две проигрышные позиции и две выигрышные позиции игрок сделает ход...
Задание 5
В условии задачи указано: "Найдите такое значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом." Можно сделать вывод, что...
Задание 6
На рисунке 3 представлена функция для построения дерева партий. Выберите верные утверждения из условия задачи, для которой была написана функция.
Задание 7
На рисунке 1 представлена функция для построения дерева партий. Восстановите условие задачи, для которой была написана эта функция.
Задание 8
Обезьяны очень любят повторять чужие ходы в игре с двумя кучами камней. За один ход шимпанзе Вова или макака Паша может добавить в любую кучу один камень или добавить в любую кучу столько камней, сколько их в данный момент в другой куче. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 64, побеждает обезьяна, сделавшая последний ход. В начальный момент в первой куче было 6 камней, а во второй — S камней, 1 ≤ S ≤ 57. Найдите минимальное значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. В ответ запишите только число.
Задание 9
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 42. В начальный момент в куче было S камней; 1 ≤ S ≤ 41. В результате аналитического решения задачи 19 найдено значение выигрыша Вани первым ходом: 20. В результате решения задачи 20 найдено три значения выигрыша Пети вторым ходом: 10, 17, 19. Постройте дерево партий и найдите минимальное значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Задание 10
На рисунке 2 представлена функция для построения дерева партий. Восстановите условие победы в условии задачи, для которой была написана эта функция.