Формулировка задач ЕГЭ
В Едином Государственном Экзамене теория игр представлена в 19-21 задачах. В общем для всех 3 задач условии сказано об игре с 1 или 2 кучами камней. Двум игрокам необходимо добиться того, чтобы после их хода количество камней в кучах было больше или равно заранее обговоренному числу. Для этого они могут добавлять в кучи некоторое количество камней разными способами (Например, можно добавить 1 камень, 3 камня или увеличить количество камней в 2 раза). При игре с 1 кучей у сдающего спрашивается при каком начальном количестве камней возможно данное в задаче условие (Например, победа одного из игроков за определённое количество ходов или гарантированная победа игрока). При игре с 2 кучами остаётся куча, чьё начальное количество камней надо найти, и добавляется ещё 1 куча с известным начальным значением.
Методы решения задач
С одной кучей:
Для наглядности возьмём вариант 19-21 задачи с сайта (https://inf.reshuege.ru/problem?id=27844)
“Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, или добавить в кучу три камня, или увеличить количество камней в куче в два раза.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 13 или 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче превышает 49. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 50 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 49.
Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
19. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
20. Найдите три таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
21. Найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.”
Из условия задачи стоит выделить несколько важных вещей:
- Для победы нужно достичь 50 или более камней.
- Петя ходит первый.
- Игроки могут добавить в кучу 1 камень, 3 камня или увеличить количество камней в куче в два раза.
Метод перебора
Первым приходящим в голову методом решения может показаться простой перебор всех возможных комбинаций с поиском значений, которые подойдут условию задачи. Для доказательства нецелесообразности метода вернёмся к условию, в котором расписан пример возможных ходов при 10 камнях в куче. В графе ниже этот пример расширен. Как можно заметить количество возможных результатов из 10 камней с каждым ходом увеличивается в 3 раза. Если учитывать то, что это лишь 1 число из 49 которые нужно будет разобрать, можно сделать вывод, что и вручную, компьютерным кодом такое решение займёт слишком много времени, что критично в условиях ЕГЭ.
Логический метод
Решение задач можно сильно упростить, логически поразмыслив над условием. Например, в вопросе 19 задачи нас просят найти минимальное значение, из которого может победить Ваня после неудачного хода Пети. Чтобы получить верный результат нужно определить наиболее эффективный ход для обоих игроков. Недолго думая можно понять, что увеличение количества камней в куче в 2 раза – это наиболее эффективный ход. Значит нужно чтобы оба игрока увеличили количество камней в 2 раза. Если нам нужно чтобы в результате получилось число ≥50, то быстрым перебором можно понять, что результат равный 50 нам не подходит так как Петя не может увеличением в 2 раза получить число 25 из которого Ваня бы и получил 50. Тоже относится и к 51. Результат 52 нам подходит. Значит наша цепочка будет выглядеть так: 13→26→52. Наш ответ: 13.
Для нахождения ответов на 20 и 21 задачи нужно обозначить “точку победы”. За “точку победы” мы возьмём минимальное количество камней начав при котором игрок моментально побеждает. В нашем случае этим количеством будет 25 ведь 25∙2=50. Значит для решения 20 нам нужно, чтобы ко второму ходу Пети в куче было 25 камней. В позицию 25 можно попасть из 24 и 22. По условию Ваня ходит в собственную выгоду поэтому мало вероятно, что он сходит из 22 в 25, поэтому этот вариант отбрасываем. В таком случае Петя за свой первый ход нужно попасть в 24. Это возможно из 12, 21 и 23. Наш ответ 122123.
Для решения 21 задачи мы используем ответы из 20. До этого подходящая стратегия проходила в 3 хода, где 12, 21, 23 были начальными позициями. Теперь, когда нам подходит 4 хода эти значения как будто сдвигаются на 2 ход, а позиции, ведущие к 12, 21, 23 становятся искомыми. Рассмотрим сценарий с 12 на 2 ходу. В этом случае нам подходят значения 6, 9, 11, но так как первым ходит Петя мы не знаем, как он поступит, начиная из этих значений. На графе представлены возможные вариации при таком сценарии:
Как можно понять по приложенным графам, при выборе 12 как значения на втором ходу у Пети остаётся множество ходов, не соответствующих условию задачи.
Продолжим поиск и возьмём за значение 2 хода – 21. В 21 можно попасть из 18 и 20. При начале из 18 Петя вновь может выбрать неподходящий условию вариант (Например: 18→19→22→23- в этом сценарии для завершения понадобится больше 4 ходов). Берём за начальное значение 20. В таком случае Петя может сходить в 3 позиции:
- В 21 из которого Ваня, по описанной в решении 20 задачи стратегии, ходит в 24 и побеждает.
- В 23 из которого Ваня также ходит в 24 и побеждает
- В 40 из которого Ваня побеждает первым ходом умножая количество камней в 2 раза (40→80).
Наш ответ 20.
Графический метод
Как можно заметить предыдущий метод сложен для понимания и даже графы, нацеленные на визуальное представление решения, не всегда помогают до конца понять решение. Поэтому существует куда более простой для понимания для решения метод – графический. Для этого нам понадобится Excel или любая другая программа для работы с электронными таблицами.
Для решения графическим путём понадобится построить ряд подряд идущих чисел до “точки победы” и ещё пары чисел для наглядности. В нашем случае точкой победы является 25 (так как игрок делающий ход из неё может сразу победить). Светло-красным цветом выделен ряд 24 (так как любой ход из этой точки приведёт к победе следующего игрока).
Далее, пользуясь логикой, описанной в логическом методе, строим решения 19-21 задач. Может показаться, что с добавлением электронной таблицы решение почти не изменилось, хоть и стало наглядней, но в решении задач с двумя кучами графический метод заиграет другими красками.
С двумя кучами:
Для наглядности возьмём вариант 19-21 задачи с двумя кучами с сайта (https://inf.reshuege.ru/problem?id=27790)
“Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза.
Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 18). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 62. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 62 или больше камней.
В начальный момент в первой куче было 10 камней, во второй куче — S камней, 1 ≤ S ≤ 51.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, то есть не гарантируют выигрыш независимо от игры противника.
19. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
20. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
21. Найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.”
В задачах с двумя сильно меняется логический метод нахождения ответа. Если до этого нам нужно было просчитывать ходы игроков лишь с одной кучей, то теперь, с добавлением второй кучи, количество ходов увеличивается в два раза. Из этого можно сделать вывод о том, что метод перебора и логический метод, если и могут решить подобные задачи, то займут слишком много времени. Поэтому лучше сразу перейти к графическому методу.
Графический метод
Так как теперь в задаче фигурирует 2 кучи нам придётся учитывать ходы с ними обеими. Сперва найдём “точку победы”. Теперь, из-за существования 2 куч, эта точка стала плавающей, поэтому легче будет изобразить “точки победы” в электронных таблицах.
Для решения нам понадобится построить два ряда чисел:
- Горизонтальный. Для этого нам сначала необходимо найти точку победы без учёта второй кучи ≥62-10. Для этого нам подходит точка 26 (26∙2=52). Таким образом строим ряд произвольный ряд подряд идущих чисел до 26.
- Вертикальный. Для этого необходимо построить ряд, начинающийся с 10 до произвольного числа (в ходе решения ряды можно будет продолжить или сократить).
Теперь нужно выделить диапазон “точек победы”. Для этого вернёмся к уже найденной позиции (26;10) и закрасим её в какой-нибудь цвет (в нашем случае зелёный). Если посчитать результаты для позиций (26;11) и (26;12) можно понять, что они, как и все последующие будут точками победы. Закрашиваем весь столбец. Переходим на столбец 25. В нём минимальной точкой победы будет позиция (25;12) и все последующие. Закрашиваем столбец начиная с (25;12). Поступаем так до конца таблицы. Теперь найдём обратную позицию для точки (26;10) - (10;26). Логично, что если одна из них является “победной”, то и вторая тоже. Значит мы можем применить такой же алгоритм, но теперь перемещаясь по строкам, а не по столбцам. В итоге должна получится подобная таблица.
Все закрашенные зелёным точки являются “победными”. Начиная ход из них, игрок может сразу же победить. Подготовительная часть закончена, и мы можем приступить к решению задач.
В 19 задаче нас просят найти минимальное значение, из которого, после неудачного хода Пети, Ваня выиграет своим первым ходом. Как мы уже говорили для нахождения такого минимального числа нужно сперва обозначить самый эффективный ход. Таким ходом является удвоение количества в одной из куч, а точнее удвоение большей кучи. Из таблицы видно, что существует две потенциальные позиции при которых данные условия могут быть выполнены.
Первая позиция – (13;10) из которой Петя переходит в (26;10) и Ваня, увеличивая количество камней в первой куче в 2 раза, побеждает. Вторая позиция - (21;10) в которой Петя удваивает количество камней во второй куче получая позицию (21;20) и Ваня, удваивая вторую кучу, побеждает. Очевидно, что минимальным значением в этом случае будет 13. Наш ответ 13.
В 20 задаче нам нужно найти 2 минимальных значения при которых Петя может выиграть вторым ходом, но не может выиграть 1. Тут мы и воспользуемся нашей таблицей. По условию нам нужно чтобы Петя гарантировано выиграть своим вторым ходом, то есть чтобы Петя оказался в “победной точке” на момент своего второго хода. Для этого нам нужно загнать Ваню в “углы” (на снимке экрана ниже они выделены оранжевым).
Оказавшись в “углу”, игрок не может выиграть и своим ходом переходит в “точку победы”. Значит если за свой первый ход Петя загонит Ваню в “угол”, тогда на свой второй ход Петя гарантировано сможет победить. Теперь нам нужно найти минимальные значения, из которых можно загнать Ваню в “угол”. Такими значениями будут 25 (25;10)→(25;11)→(26;11) и 20 (20;10)→(20;20)→(21;20). Наш ответ 2025.
В 21 задаче нам необходимо найти минимальное значение, при котором Ваня гарантированно побеждает свои вторым ходом. Тут мы можем воспользоваться небольшой лазейкой, которая почти всегда решает 21 задачу (кроме задач с особенным условием или нестандартными правилами игры). Суть её состоит в том, что мы можем взять значения из 20 задачи, и постараться попасть в него наименее эффективным способом. Так как нам необходимо минимальное значение, возьмём 20. Наименее эффективным ходом по условию задаче является прибавление 1 камня в кучу. Таким образом наш ответ 20-1=19. Проверим его. Нам необходимо чтобы Ваня выиграл свои вторым ходом. Из позиции (19;10) Петя своим ходом может перейти в позиции (20;10), (19;11), (38;10), (19;20). Подставив эти точки к таблице можно понять, что позиция (19;11) нам не подходит, так как если Петя сходит в неё, то игру не получится завершить за 4 хода, поэтому отметаем вариант с позицией (19;10). Теперь возьмём второй ответ из 20 задачи. 25-1=24. Из позиции (24;10) Петя может попасть в (25;10), (24;11), (48;10), (24;20). Очевидно, что, умножив любую из куч на 2 Петя подарит Ване победу в первый ход. Если же Петя добавит 1 камень в любую из куч, то в следующем ходу Ваня сможет также добавить 1 камень и загнать Петю в “угол”, откуда, по уже известному сценарию, у Пети уже не будет шансов на победу. Наш ответ 24.
