2026. КЕГЭ № 19. Анализ алгоритмов логической игры

Тес­т про­ве­ря­ем уме­ние ана­ли­зи­ро­вать алго­рит­мы ло­ги­чес­кой игры. Со­от­вет­ству­ет спе­ци­фи­ка­ции ФИ­ПИ.

Задание 1

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

Задание 2

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

Задание 3

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

Задание 4

Два игрока, Питирим и Виссарион, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Питирим. За один ход игрок может добавить в кучу три камня, добавить в кучу четыре камня или увеличить количество камней в куче в два раза. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 1200 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 1199. Укажите количество позиций проигрыша первого игрока его первым ходом. Решите задачу аналитически.

Задание 5

Два игрока, Пелагея и Василиса, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Пелагея. За один ход игрок может добавить в кучу один камень, добавить три камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 100 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 99. Укажите такое значение S, при котором Пелагея не может выиграть за один ход, но при любом ходе Пелагеи Василиса может выиграть своим первым ходом. Решите задачу построением дерева партий.

Задание 6

Два пирата, Попугай и Воробей, играют в следующую игру. Перед игроками лежит набор карт. За один ход игрок берёт одну из карт и кладёт её в стопку поверх предыдущей. Игроки ходят по очереди, первую карту кладёт Попугай. Первая карта может быть любой из доступных. В следующие ходы игроки могут положить только карты того же достоинства или на единицу старше. Игра завершается в тот момент, когда положить новую карту в стопку становится невозможно. Победителем считается игрок, сделавший последний ход, то есть положивший последнюю карту в стопку. Перед пиратами лежат 1 шестёрка, 3 семёрки и 2 восьмёрки. С какой карты Попугай должен начать игру, чтобы гарантированно выиграть? В качестве ответа запишите числовое значение этой карты.

Задание 7

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в три раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах оказывается 45 или больше камней. В начальный момент в первой куче было 4 камня, во второй куче — S камней; 1 ≤ S ≤ 40. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно. Решите задачу аналитически.

Задание 8

Два гнома, Попрыгун и Ворчун, играют в следующую игру. Перед игроками лежит куча туфелек Белоснежки. Игроки ходят по очереди, первый ход делает Попрыгун. За один ход игрок может взять из кучи две туфельки, взять из кучи три туфельки или уменьшить количество туфелек в куче в два раза и взять ещё две туфельки, причём при делении оставшееся количество округляется вниз. Если в результате вычитания получается отрицательное число, такой ход невозможен. Победителем считается игрок, сделавший последний ход, то есть взявший последнюю туфельку. В начальный момент в куче было S туфелек, 2 ≤ S ≤ 16. Укажите количество позиций выигрыша первым ходом в этой игре.

Задание 9

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

Задание 10

Два математика, Пифагор и Виет, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Пифагор, как старший. За один ход игрок может: — добавить в кучу х камней; — добавить в кучу 9 камней; — увеличить количество камней в куче в 2 раза. Игра завершается, когда количество камней в куче становится не менее 125. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 125 или более камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 124. Известно, что 59 — минимальное значение S, при котором Пифагор не может выиграть за один ход, но при любом ходе Пифагора Виет может выиграть своим первым ходом. Выберите верное значение х.