Задания 19, 20 и 21 демоверсии ЕГЭ по информатике 2024 года объединены тематикой теории игр и рекомендуется решать их комплексно, поскольку решение последующих задач часто основывается на результатах предыдущих. На выполнение всех трёх заданий отводится 25 минут (6 минут на 19-е, 8 минут на 20-е и 11 минут на 21-е).
Задание 19 (базовый уровень)
Два игрока, Петя и Ваня, играют в игру. Перед ними лежит куча камней, начальное количество которых обозначим как S. Игроки ходят по очереди, начиная с Пети. За один ход игрок может добавить в кучу один камень или увеличить количество камней в два раза. Игра заканчивается, когда количество камней становится не менее 129. Выигрывает игрок, сделавший последний ход (первым получивший кучу из 129 или более камней).
Необходимо найти минимальное значение S, при котором Петя не может выиграть за один ход, но Ваня гарантированно выиграет своим первым ходом.
Разделим 129 на 2: получаем 64,5. Так как количество камней — целое число, возьмём 64. Если S = 64, то Петя может получить либо 65 (добавив камень), либо 128 (умножив на 2). В обоих случаях Ваня сможет выиграть своим ходом (65 × 2 = 130, 128 + 1 = 129). Следовательно, минимальное значение S = 64.
Задание 20 (повышенный уровень)
Найдите два наименьших значения S, при которых Петя имеет выигрышную стратегию, позволяющую ему выиграть вторым ходом независимо от действий Вани. Петя не должен выигрывать за один ход.
Из решения задания 19 известно, что если после хода Вани останется 64 камня, то Петя гарантированно выиграет. Чтобы получить 64 камня, Ваня мог получить их из 63 (добавив камень) или из 32 (умножив на 2). Таким образом, два наименьших значения S, удовлетворяющих условиям задачи, это 32 и 63.
Задание 21 (высокий уровень)
Найдите минимальное значение S, при котором Ваня может выиграть либо первым, либо вторым ходом при любой игре Пети, но не имеет стратегии, гарантирующей победу на первом ходу.
Если после хода Вани останется 64 камня, то Петя гарантированно выиграет. Рассмотрим возможные способы получения 64 камней: 63 + 1 или 32 × 2. Разберём варианты получения 63 и 32:
- 63 можно получить только из 62, добавив один камень.
- 32 можно получить из 16 (умножив на 2) или из 31 (добавив один камень).
Проверим значения 16 и 31. При S = 16, Ваня не сможет гарантированно выиграть. При S = 31, Ваня также не сможет гарантированно выиграть первым ходом. Проверим значение S = 62. Если S = 62, Петя может умножить количество камней на 2, получив 124. Ваня может сделать ход и получить 125, но Петя сможет выиграть на своём ходе. Если Ваня получит 124, умножив на 2, то Петя выиграет.
Следовательно, минимальное значение S, удовлетворяющее условию задачи, — 62.
Разбор заданий 19-21 демонстрирует необходимость системного подхода к решению задач на теорию игр. Понимание логики предыдущих задач существенно упрощает решение последующих. Ключ к успеху — постепенное построение дерева игры и анализ возможных ходов.