26 задание
Поиск выигрышной стратегии
Предисловие
Следующие задачи будут интересны любителям теории игр. Приятно, что экзаменаторы придумывают все более необычные формы заданий! Перейдем к рассмотрению типовых примеров!
Демонстрационный вариант ЕГЭ 2019 г. ИНФОРМАТИКА и ИКТ, 11 класс.
1. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (30, 7), (10, 8), (10, 21). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 68. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 68 или больше камней.
В начальный момент в первой куче было шесть камней, во второй куче – S камней; 1 ≤ S ≤ 61.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Выполните следующие задания.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может выиграть за один ход.
б) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 2
Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).
В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать ходы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.
Задание 1
а) [21 ; 61]. Если количество камней во второй куче будет меньше 21, то увеличив их количество в три раза, невозможно будет набрать необходимые 62 камня (ведь в первой куче уже лежит 6 камней).
б) Очевидно, что после первого хода должно было получиться как минимум 21, чтобы Петя мог выиграть у Вани. Т.е. в начальный момент времени во второй куче было или 7 камней, или 20. Если бы их было 20, то не было бы «удачного хода», ведь и увеличение числа камней на 1, и утроение их количества не привели бы к победе. Таким образом, изначально должно было быть 7 камней.
Задание 2
Во второй куче должно быть 20 камней. Петя не может выиграть первым ходом (максимально он может получить 66 камней в двух кучах за первый ход). Первым ходом он увеличит на 1 количество камней в первой куче, расклад станет следующим (7, 20). Далее ходит Ваня, он получает четыре возможных расклада: (8, 20) или (21, 20), или (7, 60), или (7, 21). Легко заметить, что третьим ходом Петя выигрывает в любом случае (для первого расклада – увеличить в три раза количество камней во второй куче, для второго – увеличить количество камней в три раза в первой или второй куче, для третьего – увеличить количество камней во второй куче на 1, или в три раза – в первой, для четвертого – увеличить количество камней во второй куче в три раза).
Задание 3
Очевидно, что искомое число лежит в промежутке [1, 19].
Составим дерево решений, если во второй куче лежит 19 камней.
|
№ хода |
Позиция |
|||||||||
|
0 |
(6, 19) |
|||||||||
|
1, П |
(7, 19) |
6, 20 |
(18, 19) |
(6, 57) |
||||||
|
2, В |
(7, 20) |
(7, 20) |
Победа Вани (18, 57) |
Победа Вани (18, 57) |
||||||
|
3, П |
(8, 20) |
(21, 20) |
(7, 21) |
(7,60) |
(8, 20) |
(21, 20) |
(7, 21) |
(7,60) |
|
|
|
4, В |
Победа Вани (8, 60) |
Победа Вани (63, 20) |
Победа Вани (7, 63) |
Победа Вани (8, 60) |
Победа Вани (8, 60) |
Победа Вани (63, 20) |
Победа Вани (7, 63) |
Победа Вани (8, 60) |
|
|
Если Петя утроит количество камней в первой куче, то Ваня победит следующим ходом с позицией (18, 57). Аналогично произойдет, если Петя утроит количество камней во второй куче.
Рассмотрим два оставшихся у Пети хода, которые не приведут к выигрышу Вани следующим ходом. Это позиция (7, 19) и (6, 20). Ване необходимо в свой ход добиться позиции (7, 20). Что он без труда делает. Из этой позиции Петя не может победить в свой второй ход (дерево решений расписано), а Ваня следующим ходом – может. Отметим, что выполняются все требования из задания. Т.е. искомое количество камней во второй куче S = 19.
Демонстрационный вариант ЕГЭ 2018 г. ИНФОРМАТИКА и ИКТ, 11 класс.
2. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника. Выполните следующие задания.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в куче.
Дерево не должно содержать партий, невозможных при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.
Задание 1
а) [15, 28]. Если камней будем меньше 15, то Петя не сможет победить, удвоив и количество.
б) Чтобы после первого хода (при любой стратегии Пети) получилось как минимум 15 камней, в куче изначально должно быть 14 камней. Тогда Петя либо добавляет 1 камень (становится 15), либо увеличивает количество камней в куче в 2 раза (становится 28). При первой стратегии Пети, Ваня может выиграть, увеличив количество камней в 2 раза (до 30), при второй – увеличить количество камней в куче на 1 (до 29) или увеличить в 2 раза (до 56).
Задание 2
S = 7 и S = 13. Первым ходом Петя увеличивает количество камней до 14 (в первом случае – увеличивает количество камней в куче в 2 раза, во втором – кладет в нее один камень). Далее ход Вани. Он может получить либо 15 камней, либо 28. Следующим ходом Петя может победить в любом случае (удвоив количество камней до 30, или, при второй стратегии Вани, добавив один камень до 29 или удвоив количество камней в куче в 2 раза – до 56).
Задание 3
В куче должно быть 12 камней. В первый ход Петя может получить 13 или 24 камня. При выборе второй стратегии, Ваня победит 2 ходом. Поэтому Петя выбирает увеличить количество камней на 1 до 13. Ване в свой ход необходимо получить в куче 14 камней (т. е. увеличить общее количество на 1). Тогда Петя либо увеличивает количество камней до 15, либо – до 28. Ваня выигрывает при любом выборе Пети. Либо умножив количество камней на 2, либо добавив один камень.
|
№ хода |
Количество камней |
||
|
0 |
12 |
||
|
1, П |
13 |
24 |
|
|
2, В |
14 |
Победа Вани, 48 |
|
|
3, П |
15 |
28 |
|
|
4, В |
Победа Вани, 30 |
Победа Вани, 29 |
|
Демонстрационный вариант ЕГЭ 2017 г. ИНФОРМАТИКА и ИКТ, 11 класс.
3. Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 20. Если при этом в куче оказалось не более 30 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 17 камней и Паша удвоит количество камней в куче, то игра закончится, и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 19.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
1. а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 18, 17, 16?
Опишите выигрышные стратегии для этих случаев.
2. У кого из игроков есть выигрышная стратегия при S = 9, 8? Опишите соответствующие выигрышные стратегии.
3. У кого из игроков есть выигрышная стратегия при S = 7? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.
1. a) [10, 14], {19}. Если в куче будет меньше 10, то Паша не сможет выиграть, удвоив количество камней. Если больше 14 – то он проиграет согласно условию. Надо не забыть про 19 – увеличив число камней на 1, Паша выиграет.
1.б) При S = 18 – у Вали. Сначала Паша увеличивает количество камней в куче на 1 (потому что если увеличит в 2 раза, то будет автоматически победа Вали) и получает 19 камней. После этого Валя увеличивает количество камней на 1 до 20 и побеждает.
При S = 17 – у Паши. Сначала он увеличивает количество камней на 1 – до 18 (если удвоит – проиграет). Валя также увеличивает количество камней на 1 (Если удвоит – выиграет Паша). И следующим ходом Паша просто добавляет один камень, это победный ход.
При S = 16 – у Вали. Сначала Паша увеличивает количество камней на 1 (если умножит на 2, то проиграет) до 17. Валя поступает аналогично (18 камней). Паша снова увеличивает количество камней в куче на 1 – до 19. Валя – увеличивает до 20 и выигрывает.
2. При S = 9 – у Паши. Сначала он увеличивает количество камней в куче в 2 раза – до 18. Вале не остается ничего другого, как увеличить количество камней до 19. И Паша вы выигрывает следующим ходом.
При S = 8 – у Паши. Сначала он удваивает количество камней в куче (до 16). Если Валя удвоит – проиграет, потому он добавляет 1 камень. В куче становится 17 камней. Паша – добавляет еще один камень – 18 камней. Валя увеличивает количество до 19, а Паша следующим ходом – до 20 и побеждает.
Вывод
Было интересно решать эти в некотором смысле олимпиадные задачи! Конечно, нагляднее было бы изображать дерево решений, но, к сожалению, графические возможности текстового редактора ограничены. Анонсирую решение задач на координатной плоскости, когда будет необходимо достичь определенного расстояния (из ЕГЭ предыдущих лет).
