Если бы я писала ЕГЭ, то начала бы с заданий на теорию игр: 19, 20, 21 .
Судя по демоверсии ЕГЭ по информатике на 2025г, задания 19-21 будут такие же как и в предыдущих годах, единственно, раньше куча увеличивалась во время игры, а сейчас она уменьшается. Но суть решения от этого не меняется.
Дело в том, что если разобраться с шаблоном, все эти задачи решаются, однотипно. И целых три задания можно решить минут за 5-10.
Итак, вначале надо усвоить метод решения этой задачи на бумаге.
Задания 19, 20, 21 представляют собой анализ игры с одной или двумя кучами камней. Есть куча камней, игроки могут либо брать, либо докладывать камни по определенным правилам, нужно определить изначальное количество каменей, которые приведёт к победе определённого игрока.
Играют, как правило, Петя (П - значит делает первый ход) и Ваня (В - делает второй ход ).
Можно решать эту задачу с помощью дерева вариантов, но мне больше нравится метод холмов и ям. Для этой задачи он прост и нагляден.
Для начала разберёмся с вариантом, когда перед игроками лежит одна куча (с двумя решается аналогично, только вместо одной оси, нужно будет использовать две).
Назовём холмом такую позицию игрока, из которой он может победить при любых ходах противника, а ямой, наоборот, такую позицию (количество камней), из которой любой ход приведёт противника на холм .
Рассмотрим задания из демоверсии 2025г.
Представим количество камней в куче в виде числовой оси. Отметим на ней победу 19 камней.
Взглянем на правила: игрок может убрать или 2, или 5 камней, или уменьшить кучу в три раза.
Оценим потенциальные победные позиции 19+2=21, 19+5 =24, 19*3=57. Учтем, что победные 19 камней даст и позиция из 58 камней и 59 камней (нужно целое число, округляем в меньшую сторону). Выбираем наибольшее число, т.к. очевидно, что если в куче будет меньше 59 камней, игрок, находясь в здравом уме должен выбрать уменьшение кучи в три раза и выиграть (получить 19 или меньше).
Значит вся область до 59 включительно будет холмом.
А вот если в куче 60 камней, то игрок не может добиться победы и любым своим ходом приведёт противника на холм, аналогично и для 61. Если же в куче 62 камня , то это холм, потому что игрок может убрать два камня и в куче останется 60 – противник окажется в яме , 63-2=61, аналогично. Уменьшение кучи в три раза не рассматриваем, т.к. (59*3=177) до числа 177 такое действие приведет противника на первый победный холм.
64: (64-2=62 и 64-5=58) – это яма т.к. приводит противника на холм .
65: (65-5=60)- холм и т.д..
Стратегия игры понятна – нужно сажать противника в яму, а самому придерживаться холмов. Рассуждая подобным образом, можно проанализировать весь числовой ряд.
Для ЕГЭ достаточно получить две первые ямы.
Итак,отвечаем на вопрос девятнадцатого задания: Петя не может своим первым ходом выиграть (значит камней в куче больше 59). А вот Ваня выигрывает своим первым ходом. А это значит, что Петя сидит в яме и своим ходом выталкивает Ваню на холм, самое маленькое число камней в первой яме – 60.
Смотрим на задание 20. Петя не может выиграть своим первым ходом (камней в куче больше 59), но Петя всё-таки выигрывает вторым ходом, т.е. он на холме 62-63.
И задание 21: Петя в яме номер 2. т.к. Ваня выигрывает либо первым ходом (Петя подсаживает Ваню на победный холм до 59), либо вторым ходом (Петя отправляет Ваню сначала на холм 62-63) . Ответ: 64.