2026. КЕГЭ № 20. Нахождение выигрышной стратегии игры

Тест проверяет умение находить выигрышную стратегию игры. Со­от­вет­ству­ет спе­ци­фи­ка­ции ФИ­ПИ.

Задание 1

Два кондитера, Пончик и Ватрушка, играют в следующую игру. Перед игроками лежит куча конфет. Игроки ходят по очереди, первый ход делает Пончик. За один ход игрок может: – съесть одну конфету; – съесть три конфеты; – съесть три четверти конфет в куче (количество конфет в куче, полученное при делении, округляется до большего). Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 21 или менее конфет. В начальный момент в куче было S конфет, S ≥ 22. Укажите сумму значений S, при которых Ватрушка не может выиграть за один ход, но при любом ходе Ватрушки Пончик может выиграть своим вторым ходом.

Задание 2

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в куче оказывается 129 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 128. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. При решении задачи 19 было найдено значение S = 64 (П1): позиция, с которой Петя не может выиграть за один ход, но Ваня может выиграть первым ходом при любом ходе Пети. Выберите значения S, при которых Петя не может выиграть первым ходом, но выиграет вторым ходом при любых ходах Вани (В2). Решите задачу аналитически.

Задание 3

В стандартной игре с одной кучей камней определены следующие ходы: а) вычесть два камня; б) разделить количество камней в куче на три нацело (оставшееся в куче количество камней округляется вниз до целого). При решении задачи 19 были найдены значения S = {123; 124} (П1): позиции, с которых первый игрок не может выиграть за один ход, но второй игрок может выиграть первым ходом при любом ходе первого игрока. Сколько существует значений S, при которых Петя не может выиграть первым ходом, но выиграет вторым ходом при любых ходах Вани (В2)?

Задание 4

Как называется позиция, при которой второй игрок может выиграть своим третьим ходом при любых ходах первого?

Задание 5

Два дракона, Проглочун и Выжигун, играют в следующую игру. Перед игроками лежит куча алмазов. Игроки ходят по очереди, первый ход делает Проглочун. За один ход игрок может: – забрать из кучи 3 алмаза; – забрать из кучи 5 алмазов; – уменьшить количество алмазов в куче в 4 раза (количество камней в куче, полученное при делении, округляется до меньшего). Если в результате вычитания получается отрицательное число, такой ход возможен, результатом считается ноль. Игра завершается, когда алмазы в куче закончатся. Победителем считается игрок, сделавший последний ход, то есть забравший последний алмаз. Он забирает все алмазы и заодно съедает второго игрока. Таков договор. Укажите максимальное значение S, при котором Выжигун не может выиграть за один ход, но при любом его ходе Проглочун может выиграть своим вторым ходом.

Задание 6

Как найти значения S, при которых первый игрок не может выиграть первым ходом, но выиграет вторым ходом при любых ходах второго (В2)?

Задание 7

Выберите правильные утверждения из теории игр о выигрышных и проигрышных позициях.

Задание 8

Два игрока, Прохор и Валериан, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Прохор. За один ход игрок может добавить в одну из куч (по своему выбору) один камень, добавить три камня или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 174. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 174 или больше камней. В начальный момент в первой куче было 19 камней, во второй куче — S камней; 1 ≤ S ≤ 154. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Найдите минимальное значение S, когда Прохор имеет выигрышную стратегию, причём одновременно выполняются два условия: − Прохор не может выиграть за один ход; − Прохор может выиграть своим вторым ходом независимо от того, как будет ходить Валериан. Для решения задачи напишите программу.

Задание 9

Обезьяны очень любят повторять чужие ходы в игре с двумя кучами камней. За один ход шимпанзе Вова или макака Паша может добавить в любую кучу один камень или добавить в любую кучу столько камней, сколько их в данный момент в другой куче. Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 64, побеждает обезьяна, сделавшая последний ход. В начальный момент в первой куче было 6 камней, а во второй — S камней, 1 ≤ S ≤ 57. Найдите два таких значения S, при которых у Паши есть выигрышная стратегия, причём он не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Вова. Найденные значения запишите в ответе в порядке возрастания.

Задание 10

Пятачок и Винни очень любят мёд и простые числа. Они решили поселить пчелиные семьи в три улья, превратив это в игру. Игроки ходят по очереди, первый ход делает Пятачок. За один ход игрок может подселить в один из ульев 5, 11 или 19 пчёлок. Игра завершается в тот момент, когда в сумме в ульях будет не менее 79 пчёл. Победителем считается игрок, сделавший последний ход. В начальный момент в ульях было (2, S, 2S) пчёл, 1 ≤ S ≤ 25. Найдите максимальное значение S, при котором Пятачок выигрывает вторым ходом при любом ходе Винни Пуха.