Задание 26. Выигрышная стратегия. ЕГЭ 2020 по информатике

За это задание ты можешь получить 3 балла. На решение дается около 30 минут. Уровень сложности: высокий.
Средний процент выполнения: 48.6%
Ответом к заданию 26 по информатике может быть развернутый ответ (полная запись решения с обоснованием выполненных действий).

Задачи для практики

Задача 1

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (60, 10), (20, 11), (20, 30).

Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 143. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах всего будет 143 или больше камней. В начальный момент в первой куче было 34 камня, во второй куче — S камней; 1 ≤ S ≤ 140.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1. а) Укажите все такие значения числа S, при которых Коля может выиграть за один ход и соответствующие выигрышные ходы. Если при некотором значении S Коля может выиграть несколькими способами, достаточно указать один выигрышный ход.

б) Укажите, сколько существует значений S, при которых Коля не может выиграть за один ход, но при любом ходе Коли Саша может выиграть своим первым ходом. Опишите выигрышную стратегию Саши.

Задание 2. Укажите такое значение S, при котором у Коли есть выигрышная стратегия, причём одновременно выполняются два условия:

—Коля не может выиграть за один ход;

—Коля может выиграть своим вторым ходом независимо от того, как будет ходить Саша.

Для указанного значения S опишите выигрышную стратегию Коли.

Задание 3. Укажите значение S, при котором одновременно выполняются два условия:

— у Саши есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Коли;

—у Саши нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Саши.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Саши (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.

В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.

Решение

Пусть S —исходное количество камней во второй куче.

Задание 1. a) Коля может выиграть первым ходом, если S ∈ {37, 38, . . . , 140}.

Во всех случаях ему нужно утроить количество камней во второй куче. Если количество камней во второй куче меньше 37, то за один ход нельзя получить суммарное число камней в двух кучах более 142.

б) Саша может выиграть первым ходом (как бы ни играл Коля), если исходно во второй куче будет S = 36 камней, то есть начальной будет позиция (34, 36), то после первого хода Коли может получиться одна из четырёх позиций: (35, 36)—всего 71, (34, 37) — всего 71, (102, 36) — всего 138, (34, 108) — всего 142. В каждом из полученных случаев суммарное число камней не превышает 142. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, утроив число камней во второй куче, получит соответственно позиции (35, 108)— всего 143, (34, 111)— всего 145, (102, 108)—всего 210, (35, 324)—всего 359.В каждом случае суммарное число камней не менее 143. Следовательно, Саша выигрывает своим первым ходом.

Задание 2. Возможное значение S = 35. Если начальная позиция (34, 35), то Коля, чтобы выиграть своим вторым ходом, должен получить позицию (34, 36). Для этого ему нужно в кучу с 35 камнями добавить один камень. Считая позицию (34, 36) начальной, мы приходим к рассмотрению ситуации задания 1б.

При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (34, 35), то выиграет Коля своим вторым ходом.

Задание 3. Возможное значение S = 34. Если начальная позиция (34, 34), то после первого хода Коли может получиться одна из четырёх позиций: (34, 35), (35, 34) — всего 69, (102, 34), (34, 102)—всего 136.

Если после хода Коли получены позиции (34, 102), (102, 34), то Саша, утроив число камней в куче с 34 камнями, получит позицию с суммарным числом камней, равным 204, и выиграет своим первым ходом.

Если после хода Коли получены позиции (34, 35), (35, 34), то Саша, увеличив в одной из куч число камней на 1, получит позиции (34, 36) или (36, 34) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Коли
(разобраны все ходы)
1-й ход Саши
(только ход по стратегии)
2-й ход Коли
(разобраны все ходы)
2-й ход Саши
(только ход по стратегии)
(34, 34) (34, 35) (34, 36) (35, 36) (35, 108)
  (34, 37) (34, 111)
(102, 36) (102, 108)
(34, 108) (34, 324)
(35, 34) (36, 34) (36, 35) (108, 35)
(37, 34) (111, 34)
(36, 102) (108, 102)
(108, 34) (324, 34)
(102, 34) (102, 102)    
(34, 102) (102, 102)    
Ответ:
Показать решение

Задача 2

Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (60, 10), (20, 11), (20, 30).

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1. а) Укажите все такие значения числа S, при которых Паша может выиграть за один ход и соответствующие выигрышные ходы. Если при некотором значении S Паша может выиграть несколькими способами, достаточно указать один выигрышный ход.

б) Укажите, сколько существует значений S, при которых Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.

Задание 2. Укажите такое значение S, при котором у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:

—Паша не может выиграть за один ход;

—Паша может выиграть своим вторым ходом независимо от того, как будет ходить Вова.

Для указанного значения S опишите выигрышную стратегию Паши.

Задание 3. Укажите значение S, при котором одновременно выполняются два условия:

— у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши;

—у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вовы.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.

В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.

Решение

Пусть S —исходное количество камней во второй куче.

Задание 1. a) Паша может выиграть первым ходом, если S ∈ {43, 44, . . . , 160}.

Во всех случаях ему нужно удвоить количество камней во второй куче.

Если количество камней во второй куче меньше 43, то за один ход нельзя получить суммарное число камней в двух кучах более 166.

Задание 1. б) Вова может выиграть первым ходом (как бы ни играл Паша), если исходно во второй куче будет S = 42 камня, то есть начальной будет позиция (40, 42), то после первого хода Паши может получиться одна из четырёх позиций: (41, 42)— всего 83, (120, 42)—всего 162, (40, 43)—всего 83, (40, 126)— всего 166.

В каждом из полученных случаев суммарное число камней меньше, чем 169. Значит, Паша не может выиграть своим первым ходом. Для каждой из полученных позиций Вова, утроив число камней во второй куче, получит соответственно позиции (41, 126)—всего 167, (120, 126)—всего 246, (40, 129)—всего 169, (40, 378) — всего 418. В каждом случае суммарное число камней не менее 167. Следовательно, Вова выигрывает своим первым ходом.

Задание 2. Возможное значение S = 41. Если начальная позиция (40, 41), то Паша, чтобы выиграть своим вторым ходом, должен получить позицию (40, 42). Для этого ему нужно в кучу с 42 камнями добавить один камень. Считая позицию (40, 42) начальной, мы приходим к рассмотрению ситуации задания 1б.

При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (40, 41), то выиграет Паша своим вторым ходом.

Задание 3. Возможное значение S = 40. Если начальная позиция (40, 40), то после первого хода Паши может получиться одна из четырёх позиций: (40, 41), (41, 40) — всего 81, (120, 40), (40, 120)—всего 160.

Если после хода Паши получены позиции (120, 40), (40, 120), то Вова, утроив число камней в куче со 120 камнями, получит позицию с суммарным числом камней, равным 400, и выиграет своим первым ходом.

Если после хода Паши получены позиции (40, 41), (41, 40), то Вова, увеличив в одной из куч число камней на 1, получит позиции (40, 42) или (42, 40) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом.

В таблице изображено дерево возможных партий при описанной стратегии Вовы. Заключительные позиции (в них выигрывает Вова) подчёркнуты.

И. п. Положение после очередных ходов
1-й ход Паши
(разобраны все ходы)
1-й ход Вовы
(только ход по стратегии)
2-й ход Паши
(разобраны все ходы)
2-й ход Вовы
(только ход по стратегии)
(40, 40) (40, 41) (40, 42) (120, 42) (120, 126)
  (41, 42) (41, 126)
(40, 126) (40, 378)
(40, 43) (40, 129)
(41, 40) (42, 41) (42, 120) (126, 120)
(42, 41) (126, 41)
(126, 40) (378, 40)
(43, 40) (129, 40)
(120, 40) (120, 120)    
(40, 120) (120, 120)    
Ответ:
Показать решение

Задача 3

Два игрока, Коля и Саша, играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочередно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 12, нельзя сделать фишку, на которой написано 21.

Первый ход делает Коля, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.

Будем называть партией любую допустимую правилами последовательность ходов игроков, приводящую к завершению игры. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит указать, какую фишку он должен выставить в любой ситуации, которая ему может встретиться при различной игре противника.

Пример партии.

Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.

Пусть первый ход Коли 21.

Саша может поставить 12, 11 или 13. Предположим, он ставит 12.Получим цепочку 21-12.

Коля может поставить 22 или 23. Предположим, он ставит 22. Получим цепочку 21-12-22.

Саша может поставить только фишку со значением 23. Получим цепочку 21-12-22-23.

Перед Колей в кучке остались только фишки 11 и 13, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Саша выиграл.

Выполните следующие три задания при исходном наборе фишек в кучке 11, 12, 13, 21, 22, 31, 33.

Задание 1. Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.

Задание 2. Пусть Коля первым ходом пошёл 33. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим третьим ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.

Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.

Решение

Задание 1. Пример кратчайшей партии: 21-12-22.

Возможны другие варианты ответа:

22-21-12;

31-13-33;

33-31-13.

Пояснение. Партия будет кратчайшей, если каждая фишка партии содержит одну и ту же цифру, которая встречается реже остальных. Ответный ход противника в случае кратчайшей партии должен быть «симметричным», если это возможно. То есть на ход фишкой «xy» ответным ходом должен быть «yx».

Задание 2. Стратегия, позволяющая выиграть своим третьим ходом, есть у Саши.

Ниже представлена таблица выигрышных стратегий Саши.

В таблице показаны все ходы Коли и только выигрышные ходы Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.

Коля
1-й ход
33
33
Саша
1-й ход
31
33-31
Коля
2-й ход
32
11-13-32
13
33-31-13
12
33-31-12
Саша
2-й ход
12
33-31-11-12
-
-
22
33-31-12-22
Коля
3-й ход
21
33-31-11-12-21
22
33-31-11-12-22
-
-
21
33-31-12-22- 21
Саша
3-й ход
13
33-31-11-12-21-13
21
33-31-11-12-22-21
Игра не окончена
- 13
33-31-12-22-21-13

Пояснение. Стратегия Саши заключается в том, что он должен добавить ещё один дубль и не дать Коле поставить третий дубль; в этом случае количество фишек в партии будет чётным, что необходимо для выигрыша Саши.

Задание 3.Можно убрать фишки 22 и 33. В этом случае Коля выиграет третьим ходом. Стратегия Коли — обязательно поставить любым своим ходом фишку 11.

Пример такой партии:

Игрок Коля Саша Коля Саша Коля
Ход 12 21 11 13 31

Пояснение. После того как из исходного набора будут убраны фишки «22», «33», останется нечётное количество фишек, при этом каждая фишка содержит 1 и у каждой фишки есть «симметричная» ей, поэтому первый игрок при правильной стратегии всегда выигрывает.

Ответ:
Показать решение

Задача 4

Два игрока, Коля и Саша, играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочерёдно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 12, нельзя сделать фишку, на которой написано 21.

Первый ход делает Коля, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.

Будем называть партией любую допустимую правилами последовательность ходов игроков, приводящую к завершению игры. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Описать стратегию игрока—значит указать, какую фишку он должен выставить в любой ситуации, которая ему может встретиться при различной игре противника.

Пример партии.

Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.

Пусть первый ход Коли 21.

Саша может поставить 12, 11 или 13. Предположим, он ставит 12.Получим цепочку 21-12.

Коля может поставить 22 или 23. Предположим, он ставит 22. Получим цепочку 21-12-22.

Саша может поставить только фишку со значением 23. Получим цепочку 21-12-22-23.

Перед Колей в кучке остались только фишки 11 и 13, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Саша выиграл.

Выполните следующие три задания при исходном наборе фишек в кучке {11, 12, 13, 21, 23, 31, 32, 33}.

Задание 1. Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.

Задание 2. Пусть Коля первым ходом пошёл 11. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвёртым ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.

Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.

Решение

Задание 1. Пример кратчайшей партии: 21-12-23-32.

Возможен другой вариант ответа: 23-32-21-12.

Пояснение: партия будет кратчайшей, если первый игрок начнёт игру с фишки, первая цифра которой встречается реже первых цифр остальных фишек, и, если это возможно, партия не содержит «дублей» — фишек вида «xx». Ответный ход противника, в случае кратчайшей партии, должен быть «симметричным», если это возможно. То есть на ход фишкой «xy» ответным ходом должен быть «yx», если это возможно.

Задание 2. Стратегия, позволяющая выиграть своим четвёртым ходом, есть у Коли.

Ниже представлена таблица выигрышных стратегий Коли. В таблице показаны все ходы Саши и только выигрышные ходы Коли. Заключительные позиции (в них выигрывает Коля) подчёркнуты.

Коля
1-й ход
11
11
Саша
1-й ход
12
11-12
13
11-13
Коля
2-й ход
21
11-12-21
32
11-13-32
Саша
2-й ход
13
11-12-21-13
23
11-13-32-23
21
11-13-32-21
Коля
3-й ход
32
11-12-21-13-32
31
11-13-32-23-31
12
11-13-32-21-12
Саша
3-й ход
23
11-12-21-13-32- 23
12
11-13-32-23-31- 12
23
11-13-32-21-12- 23
Коля
4-й ход
31
11-12-21-13-32- 23-31
21
11-13-32-23-31- 12-21
31
11-13-32-21-12- 23-31

Пояснение. Стратегия Коли заключается в том, что он должен ставить фишки, которые не заканчиваются на 3, тем самым не давая возможность Саше сделать ход «33». Например, если после ходов 11-13-31-12 Коля поставит фишку 23, то выиграет Саша: 11-13-31-12-23-33-32-21.

Задание 3.Можно убрать фишки 11 и 33. В этом случае независимо от ходов обоих игроков Саша выиграет (или своим вторым, или своим третьим ходом).

Пример такой партии:

Игрок Коля Саша Коля Саша Коля Саша
Ход 23 31 13 32 21 12

Пояснение. После того, как из исходного набора будут убраны фишки «11», «33», останется чётное количество фишек, при этом для каждой фишки есть «симметричная» ей, поэтому второй игрок всегда выигрывает.

Ответ:
Показать решение
Показать еще

Готовим к ЕГЭ на 85+ баллов и побеждаем лень

Каждый месяц 12 онлайн-занятий в дружелюбной атмосфере + 16 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

Подробнее о курсе