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 представлена функция для построения дерева партий. Восстановите условие победы в условии задачи, для которой была написана эта функция.