На уроке рассмотрен разбор 19, 20, 21 задания ЕГЭ по информатике: дается подробное объяснение и решение задания
Содержание:
- Объяснение заданий 19, 20 и 21 ЕГЭ по информатике
- Теория игр. Поиск выигрышной стратегии
- Решение 19, 20, 21 заданий ЕГЭ по информатике
- Игра с двумя кучами камней или табличка
- Задания для тренировки 19, 20, 21 заданий ЕГЭ (взяты из КИМ и сборников прошлых лет)
- Игра с одной кучей камней
- Игра с набором слов
Объяснение заданий 19, 20 и 21 ЕГЭ по информатике
19-е задание: «Анализ алгоритма логической игры»
Уровень сложности
— повышенный,
Требуется использование специализированного программного обеспечения
— нет,
Максимальный балл
— 1,
Примерное время выполнения
— 6 минут.
Проверяемые элементы содержания: Умение анализировать алгоритм логической игры
20-е задание: «Поиск выигрышной стратегии»
Уровень сложности
— повышенный,
Требуется использование специализированного программного обеспечения
— нет,
Максимальный балл
— 1,
Примерное время выполнения
— 6 минут.
Проверяемые элементы содержания: Умение найти выигрышную стратегию игры
21-е задание: «Дерево игры для выигрышной стратегии»
Уровень сложности
— повышенный,
Требуется использование специализированного программного обеспечения
— нет,
Максимальный балл
— 1,
Примерное время выполнения
— 10 минут.
Проверяемые элементы содержания: Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию
До ЕГЭ 2021 года — эти задания были объединены в задание № 26 ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:
«Для пункта 2 или 3 в представленной стратегии рассмотрены не все возможные ходы проигрывающего игрока, которые он может сделать при игре выигрывающего игрока по выигрышной стратегии.
Для пункта 3 представлено дерево игры, содержащее лишние ветви, не относящиеся к выигрышной стратегии.
Дерево, являющееся частью ответа на пункт 3, представлено с использованием ссылок на
фрагменты, являющиеся решениями других пунктов задания.
В задании спрашивается, в частности, кто выиграет, а в ответе не указан в явном виде выигрывающий игрок. На все вопросы, поставленные в задании, должны быть даны чёткие ответы. Ответ на вопрос о выигрышной стратегии в стиле «Может выиграть первый игрок, но если он неправильно пойдёт, то выиграет второй» является ошибочным, поскольку выигрышная стратегия одного игрока не оставляет возможности победы другому игроку»
ФГБНУ «Федеральный институт педагогических измерений»
* Некоторые изображения и примеры страницы взяты из материалов презентации К. Полякова
Теория игр. Поиск выигрышной стратегии
Для решения 19 задания необходимо вспомнить следующие темы и понятия:
- для того чтобы найти выигрышную стратегию в несложных играх, достаточно использовать метод перебора всех возможных вариантов ходов игроков;
- для решения задач 19 задания чаще всего для этого применяется метод построения деревьев;
- если от каждого узла дерева отходят две ветви, т.е. возможные варианты хода, то такое дерево называется двоичным (если из каждой позиции есть три варианта продолжения, дерево будет троичным).
- все позиции в простых играх делятся на выигрышные и проигрышные;
- выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, обязательно выиграет при любых действиях соперника, если не допустит ошибки; при этом говорят, что у данного игрока есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть;
- если игрок, делающий первый ход, находится в проигрышной позиции, то он обязательно проиграет, если ошибку не сделает его оппонент; в этом случае говорят, что у данного игрока нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для оппонента;
- выигрышные и проигрышные позиции характеризуются так:
- позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная;
- позиция, из которой хотя бы один из последующих возможных ходов ведет в проигрышную позицию — выигрышная, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для оппонента) позицию.
- для того чтобы определить, какой из игроков выиграет при стратегически правильной игре, необходимо ответить на вопросы:
- Может ли какой-либо из игроков выиграть, независимо от ходов других игроков?
- Что должен сделать игрок с выигрышной стратегией первым ходом, чтобы он смог выиграть, независимо от действий ходов игроков?
Выигрышная стратегия
Выигрышные и проигрышные позиции
Кто выиграет при стратегически правильной игре?
Рассмотрим пример:
Игра: в кучке лежит 5 спичек; играют два игрока, которые по очереди убирают спички из кучки; условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку
Решение:
- Будем использовать метод построения дерева. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3), эти два варианта отобразим при помощи дерева:
- если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:
- если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:
- если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока;
- итак, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу;
- тогда как второй игрок не может выиграть, независимо от действий первого: потому что, если первый игрок сначала убрал одну спичку, второй всегда проиграет.
проанализируем стратегию игры:
Ответ: при правильной игре (стратегии игры) выиграет первый игрок; для этого ему достаточно своим первым ходом убрать одну спичку.
Решение 19, 20, 21 заданий ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
Игра с двумя кучами камней или табличка
19_8:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 59 или больше камней.
В начальный момент в первой куче было 5 камней, во второй куче – S
камней; 1 ≤ S ≤ 53
.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S
, когда такая ситуация возможна.
Задание 20 ЕГЭ.
Найдите минимальное значение S
, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Задание 21 ЕГЭ.
Найдите два значения S
, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.
✍ Решение:
- Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке — количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 5, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа — 53. Таблица пригодится для решения заданий 20 и 21:
- Для начала найдем все выигрышные позиции для первой строки таблицы, т.е. для первого хода. Обозначим их плюсами (
+
): - Для того, чтобы получить наименьшее значение
S
, в качестве первого хода Пети необходимо увеличивать в два раза вторую кучу. Т.е. для решения задания необходимо найти такое наименьшееS
, при котором Петя походил неверно, и попал своим ходом в выигрышную позицию для своего соперника, т.е. в ячейку с плюсом:
Выигрышные позиции для первой строки ищем по принципу увеличения количества камней S
в 2 два раза: 5 + S*2 >=59
. Получим S>=27
S = 14 1 ход Петя: 14*2 = (5,28) 2 ход Ваня: 28*2 = (5,56), Сумма = 61, Выигрыш!
Ответ: 14
✎ Задание 20:
- Проанализируем таблицу, и для каждой строки найдем выигрышные позиции с одного хода. Т.е. которые позволят игроку, оказавшемуся «на них», выиграть за один ход (получить суммарно 59 и более камней):
- Найдем проигрышные позиции: те, которые ведут только в выигрышные позиции для соперника (ведут только в плюсы)
- В задании требуется найти минимальное
S
, котором выиграет Петя, но выиграет он НЕ первым своим ходом, а вторым. То есть в нашем случае необходимо найтиS
, которое может перевести соперника в проигрышную позицию. То есть в минус. Для первой строки (так как первым будет ходить Петя) таких значений два: - Наименьшее S = 24
При заполнении таблицы выигрышными позициями можно проследить закономерность «узора», а заполнять позиции по аналогии.
Проигрышные позиции: (6,26) (8,25) (10,24) (12,23) (14,22)
- Для решения этого задания найдем выигрышные позиции со второго хода, т.е. которые могут перевести соперника в проигрышную позицию (с минусом):
- Чтобы выиграл Ваня, но выиграл не первым ходом, а вторым, необходимо, чтобы Петя находился в такой позиции, которая ведет его только на выигрышные позиции со второго хода:
Ответ: 23 25
>19_9:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на 1 камень больше, чем убирается).
Например, пусть в одной куче 6, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (5, 9), (3, 9), (6, 8), (6, 5).
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 20. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 20 или меньше камней. В начальный момент в первой куче было 10 камней, во второй куче – S
камней, S > 10.
Найдите значение S
, при котором Ваня выигрывает своим первым ходом при любой игре Пети?
Задание 20 ЕГЭ.
Найдите минимальное и максимальное значение S
, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21 ЕГЭ.
Найдите значение S
, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
✍ Решение (Excel):
✎ Задание 19:
- В столбце
А
отложим значения — количество камней в первой куче. Начнем с ячейкиА2
, в которую внесем начальное количество камней, т.е. 10. Автозаполнением продлим значения вниз до 0: - В строке 1 таблицы (начиная с ячейки
B1
) отложим значения для второй кучи. Поскольку в задании говорится, что победа будет достигнута при S<=20, и достигнуть этого значения более сильной командой можно уменьшив кол-во камней во второй куче в два раза, начиная с числа 40: 40/20. То есть возьмем значение больше 40, примерно 45. Используем автозаполнение до значения 11: - Из двух команд, которые могут выполнять игроки, выберем наиболее сильную, т.е. благодаря которой можно быстрее достичь выигрышного диапазона и попасть в значения S<=20. Это команда уменьшения количества камней в два раза, т.е.
/2
. - Для каждой из ячеек полученной таблицы рассчитаем значение, полученное в результате уменьшения в два раза той кучи камней, в которой большее количество камней (так как это даст меньший результат). Например, для ячейки
С5
, в которой игрок имеет в первой куче 7 камней, а во второй куче 44 камня, мы бы выполнили действие 44/2+7. Т.е. уменьшили вдвое вторую кучу, т.к. в ней больше камней. Еще необходимо обращать внимание на четность и нечетность значений (в Excel это функцияЕНЕЧЁТ
— возвращает ИСТИНУ, если значение нечетно). - Чтобы автоматизировать процесс необходимо использовать формулу, в которой найдем максимальное значение из двух вариантов:
Минимальное из (ЕСЛИ
(ЕНЕЧЁТ(1-я куча)то
(1-я куча+1)/2+2-я куча,иначе
1-я куча/2+2-я куча);ЕСЛИ
(ЕНЕЧЁТ(2-я куча)то
(2-я куча+1)/2+1-я куча,иначе
2-я куча/2+1-я куча)).
B2
:= МИН(ЕСЛИ(ЕНЕЧЁТ($A2);($A2+1)/2+B$1;$A2/2+B$1);ЕСЛИ(ЕНЕЧЁТ(B$1);(B$1+1)/2+$A2;B$1/2+$A2))
$
будем использовать для фиксации столбца А
и строки 1
при копировании формулы.
Ответ: 21
✎ Задание 20:
- Продолжаем работать с той же таблицей, что и в задании 19. Выделим все проигрышные позиции (из которых можно походить только в выигрышные позиции для соперника, т.е. в выделенные ячейки):
- Петя может выиграть свои вторым ходом, если он не может выиграть первым ходом, но может выполнить ход в позицию, проигрышную для соперника (в ячейку, выделенную красным). Такие позиции назовем выигрышные позиции со второго хода. Найдем минимальное и максимальное значение
S
при таком первом ходе Пети:
При S=44 Пете необходимо уменьшить 2-ю кучу вдвое (44/2 = 22), чтобы оказаться в проигрышной позиции для соперника.
Ответ: 22 44
✎ Задание 21:
- Выделим все такие выигрышные позиции со второго хода:
- Далее придерживаемся следующей логики: Ваня сможет выиграть свои первым или вторым ходом, но при этом не гарантированно первым ходом, если у Пети будет возможность выполнить ходы только в позиции выигрышные со второго хода. Найдем такое S:
При S = 24 Петя сможет уменьшить кучи на один камень, и тогда оказывается в выделенной зеленой области — выигрышные позиции со второго хода для Вани, либо уменьшить количество камней вдвое, и тогда Ваня оказывается в выигрышной позиции с первого хода (розовая область).
Ответ: 24
19_7: с экзамена ЕГЭ 2020г. (со слов учащегося):
Два игрока, Петя и Ваня, играют в следующую игру. На табличке написаны два значения. Оба игрока в свой ход могут заменить одно из значений на сумму обеих (по своему выбору). Первый ход делает Петя. Игра считается законченной когда сумма обеих значений равняется не меньше 56. То есть выигрывает игрок, получивший 56 или более в сумме. Начальное значение (10, S).
Найдите максимальное S при котором Петя не может выиграть первым ходом.
Задание 20 ЕГЭ.
У кого из игроков есть выигрышная стратегия при начальном значении (9, 15).
Задание 21 ЕГЭ.
У кого из игроков есть выигрышная стратегия при начальном значении (3,7)? Опишите эту стратегию и изобразите дерево всех возможных партий
при этой стратегии
.
Типовые задания для тренировки
✍ Решение:
- Задание 19.
Максимальное S при котором Петя НЕ может выиграть своим первым ходом S = 22. Петя проиграет, если в сумме получится 55 и меньше. Первое значение = 10, необходимо найти второе значение, при этом максимальное. Схематично отобразим варианты ходов:
(10,22) - ход Пети - (10+22, 22) - итог суммы обеих значений таблички: 32 + 22 = 54 (<56)
Для того, чтобы сделать сумму большей, Петя заменит первое значение на сумму, так как оно меньше второго значения (10<22)
В начальной позиции (9, 15) выигрышная стратегия есть у Вани. Для себя отобразим схематично выигрышную партию Вани:
Зеленым цветом выделены выигрышные ходы.
В начальной позиции (3, 7) выигрышная стратегия есть у Вани. Изобразим дерево всех возможных партий при этой стратегии (раз говорится «при этой стратегии» имеем в виду, выигрышную стратегию Вани):
Дерево для выигрышной стратегии Вани: для Вани отображены только ходы по стратегии, для Пети — все возможные ходы. Зеленым цветом — выигрышный ход, красная обводка — ход по стратегии.
Решение подобного задания в Excel смотрите на видео:
📹 Видео
📹 Видеорешение на RuTube здесь
19_6:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 44.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 44 или больше камней.
В начальный момент в первой куче было 5 камней, во второй куче – S камней; 1 ≤ S ≤ 38.
Задание 19 ЕГЭ.
При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?
Задание 20 ЕГЭ.
Назовите одно любое значение S, при котором Петя может выиграть своим вторым ходом.
Задание 21 ЕГЭ.
Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом.
✍ Решение:
- Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке — количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 5, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа — 38:
- Далее будем рассуждать так: Петя может выиграть первым ходом, выполнив команду *2 (увеличить количество камней в куче в два раза), если вместо S (кол-во камней во второй куче), мы будем изменять значение, начиная от 20, до последнего возможного по условию значения 38:
Задание 19 а):
5 + 20*2 = 45 (>44) * 5 - кол-во камней в первой куче, оно не меняется по условию
+
означает выигрышную позицию с первого хода:Ответ 1 а):
S = [20;38] (На ЕГЭ пояснить ходы, например: (5; 20) -> (Ход Пети)-> (5;40); 40 + 5 = 45)
Задание 19 б):
+
). Отметим такие позиции, учитывая, что это первый ход Пети, и кол-во камней в первой куче должно быть 5. Найденные позиции будут проигрышными позициями (-
):S = 19 (На ЕГЭ пояснить ходы, например: (5; 19) -> (Ходы Пети): (5;21),(5;28);(7;19);(7;28). Везде следующим ходом выиграет Ваня, см. предыдущ. пункт)
Задание 20:
2+
):
S = 16, 17 или 18 (На ЕГЭ пояснить ходы, ссылаясь на объяснения в предыдущих пунктах)
Задание 21:
+
), либо в позицию выигрышную со второго хода или n-го хода (2+
). Это позиция при S = 14:
Ответ 3: S = 14 (На ЕГЭ пояснить ходы, ссылаясь на объяснения в предыдущих пунктах)
📹 YouTube здесь
Видеорешение на RuTube здесь
Задания для тренировки 19, 20, 21 заданий ЕГЭ (взяты из КИМ и сборников прошлых лет)
Игра с одной кучей камней
19_3: Демоверсия ЕГЭ 2018 информатика:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Задание 19 ЕГЭ
а) Укажите такие значения числа S, при которых Петя может выиграть в один ход.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 20 ЕГЭ
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причем:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.
Задание 21 ЕГЭ
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции
Дерево не должно содержать партий, невозможных при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.
✍ Решение:
-
Задание 19.
- а) Петя может выиграть, если S = 15, … 28
15, ..., 28 - выигрышные позиции с первого хода
S = 14 Петя: 14 + 1 = 15 выигрышная позиция (см. п. а). Выигрывает Ваня Петя: 14 * 2 = 28 выигрышная позиция (см. п. а). Выигрывает Ваня 14 - проигрышная позиция
Задание 20.
S = 7 Петя: 7 * 2 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Петя S = 13 Петя: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Петя 7, 13 - выигрышные позиции со второго хода
Задание 21.
S = 12 Петя: 12 + 1 = 13 Ваня: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Ваня вторым ходом!
В таблице изображено дерево возможных партий (и только их) при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчеркнуты. На рисунке это же дерево изображено в графическом виде.
Дерево всех партий, возможных при стратегии Вани:
* красный круг означает выигрыш
19_4: Досрочный егэ по информатике 2018, вариант 1. Задание 19:
Два игрока, Паша и Вася, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в пять раз. Игра завершается в тот момент, когда количество камней в куче становится не менее 69.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 69 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 68.
а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б)Укажите такое значение S, при котором Паша не может выиграть за один ход, но при любом ходе Паши Вася может выиграть своим первым ходом. Опишите выигрышную стратегию Васи.
Задание 20 ЕГЭ.
Укажите 2 таких значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Вася. Для каждого указанного значения S опишите выигрышную стратегию Паши.
Задание 21 ЕГЭ.
Укажите хотя бы одно значение S, при котором у Васи есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, и у Васи нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Васи. Постройте дерево всех партий, возможных при этой выигрышной стратегии Васи (в виде рисунка или таблицы).
Типовые задания для тренировки
✍ Решение:
-
19.
а) S ≥ 14. При количестве камней в куче от 14 и выше Паше необходимо увеличить их количество в пять раз, тем самым получив 70 или более камней.
S ≥ 14 выигрышные позиции
б) S = 13. Паша своим первым ходом может сделать 14, 17 или 65 камней, после этого Вася увеличивает количество в пять раз, получая 70, 85 или 325 камней в куче.
S = 13 Паша 1 ход: 13 + 1 = 14 Паша 1 ход: 13 + 4 = 17 Паша 1 ход: 13 * 5 = 65 Ваня 1 ход: [14, 17, 65] * 5 = S ≥ 14 Ваня выигрывает 13 - проигрышная позиция
20. S = 9, 12. Для данных случаев Паше необходимо прибавить 4 камня к куче из 9 камней, либо 1 камень к куче из 12, и получить кучу из 13 камней.
После чего игра сводится к стратегии, описанной в пункте 1б.
S = 13 Паша 1 ход: 9 + 4 = 13 Паша выигрывает Паша 1 ход: 12 + 1 = 13 Паша выигрывает 9, 12 - выигрышные позиции со второго хода
21. S = 8. Своим первым ходом Паша может сделать количество камней в куче 9, 12 или 40. Если Паша увеличивает кол-во в пять раз, тогда Вася выигрывает своим первым ходом, увеличивая количество камней в пять раз.
Для случая 9 и 12 камней Вася использует стратегию, указанную в п.2.
S = 8 Паша 1 ход: 8 + 1 = 9 Ваня Выигрывает (см. п.2) Паша 1 ход: 8 + 4 = 12 Ваня Выигрывает (см. п.2) Паша 1 ход: 8 * 5 = 40
Аналитическое решение 19 задания смотрите на видео:
📹 YouTube здесь
Видеорешение на RuTube здесь
19_1:
Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 7 камней, за один ход можно получить кучу из 14 или 8 камней. У каждого игрока, чтобы сделать ход, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 28. Если при этом в куче осталось не более 44 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 23 камня, и Паша удвоит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1≤ S ≤ 27.
Задание 19 ЕГЭ
а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 26, 25, 24? Опишите выигрышные стратегии для этих случаев.
Задание 20 ЕГЭ
У кого из игроков есть выигрышная стратегия при S = 13, 12? Опишите соответствующие выигрышные стратегии.
Задание 21 ЕГЭ
У кого из игроков есть выигрышная стратегия при S = 11? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.
✍ Решение:
а) Паша имеет выигрышную стратегию и может выиграть за один ход, если S = 27: тогда ему достаточно добавить один камень, чтобы игра закончилась при 28 камнях в куче; или если S = 14, 15, 16, 17, 18, 19, 20, 21, 22 (44/2 = 22 и 28/2 = 14, т.е. от 14 до 22): тогда необходимо удвоить кучу.
S=27 Паша: 27 + 1 = 28 - Выигрыш! 27 - выигрышная позиция
б) При S = 26 выигрышная стратегия есть у Вали. Паша делает ход первым, у него есть возможность либо удвоить количество камней в куче, и тогда количество превысит 44, — выигрывает Валя; либо увеличить количество на один камень, станет 27 камней: следующая Валя, — она может положить один камень и выиграть.
S=26 Паша: 26 * 2 = 52 Валя выигрывает! или: Паша: 26 + 1 = 27 Валя: 27 + 1 = 28 - Выигрыш! 26 - проигрышная позиция
При S = 25 выигрышная стратегия есть у Паши. Удваивать количество камней нет смысла, т.к. количество превысит 44, значит, Паша добавит один камень, их станет 26, следующая Валя, — она может либо добавить камень (станет 27 камней, следующим ходом выиграет Паша) либо удвоить — и сразу проиграть, т.к. станет более 44 камней.
S=25 Паша: 25 + 1 = 26 Валя: 26 ... проигрышная позиция (см. выше) Паша выигрывает! 25 - выигрышная позиция
При S = 24 выигрышная стратегия есть у Вали. Паша делает ход первым: удваивать кучу нет смысла, т.к. в ней станет более 44, значит, Паша добавит один камень, их станет 25; следующая — Валя: она может только добавить один камень (станет 26 камней, следующим ходом Паша оказывается в проигрышной позиции, см. пункт при S = 26).
S=24 Паша: 24 + 1 = 25 Валя: 25 ... выигрышная позиция (см. выше) Валя выигрывает! 24 - проигрышная позиция
Задание 20 ЕГЭ:
При S = 13 или S = 12 выигрышная стратегия есть у Паши. Паша удваивает количество и в куче остается 26 или 24 камня. Это проигрышная позиция для того, кто ходит (см. п. 1 б), а следующий ход за Валей.
Задание 21 ЕГЭ:
При S = 11 выигрышная стратегия есть у Вали. Паша делает первый ход: в куче остается либо 22, либо 12 камней. Обе эти позиции выигрышные для того, кто ходит. При S = 12 последовательность игры описана в пункте 2, а при S = 22 — в пункте 1а.
Дерево возможных партий:
* Для Вали отображены только ходы по стратегии
** красный круг означает выигрыш
*** фиолетовый круг — конец игры (проигрыш)
Подробное объяснение 19 задания ЕГЭ смотрите на видео (аналитическое решение):
📹 YouTube здесь
Видеорешение на RuTube здесь
Игра с двумя кучами камней или табличка
19_5:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 73.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 73 камня или больше.
Задание 1.
Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2.
Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию.
Задание 3.
Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
✍ Решение:
- Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани.
- Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети.
- Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани.
Видео решения 19 задания с двумя кучами (аналитическое решение):
📹 YouTube здесь
Видеорешение на RuTube здесь
Игра с набором слов
19_2: 2017 год (один из вариантов со слов выпускника):
Петя и Ваня играют в игру: есть набор слов, необходимо последовательно называть буквы этих слов. Побеждает тот игрок, который называет последнюю букву любого слова из набора. Петя ходит первым.
Например, есть набор слов {Волк, Информатика, Страшно}; для заданного набора слов Петя своим первым ходом может назвать букву В, И или С. Если Петя выберет букву В, то победит Ваня (следующие ходы: Петя — В, Ваня — О, Петя — Л, Ваня — К).
Задание 1
А) Даны 2 слова (набора букв) {ИКЛМНИКЛМНХ, НМЛКИНМЛКИ}. Определить выигрышную стратегию.
Б) Даны 2 слова {ТРИТРИТРИ…ТРИ, РИТАРИТАРИТАРИТА…РИТА}. В первом слове 99 букв, во втором 164. Определить выигрышную стратегию.
Задание 2
Необходимо поменять две буквы местами из набора пункта 1А в слове с наименьшей длинной так, чтобы выигрышная стратегия была у другого игрока. Объяснить выигрышную стратегию.
Задание 3
Дан набор слов {Ворона, Волк, Волна, Производная, Прохор, Просо}. У кого из игроков есть выигрышная стратегия? Обосновать ответ и написать дерево всех возможных партий для выигрышной стратегии.
✍ Решение:
- Если поменять местами во втором слове (НМЛКИНМЛКИ) буквы Н и И, то получится следующий набор слов:
{ИКЛМНИКЛМНХ, ИМЛКННМЛКИ}
Для данного набора выигрышная стратегия есть у Вани. Петя в любом случае должен будет выбрать букву И, а Ваня следующим ходом может перевести игру в проигрышную позицию для Пети, т.е. перейти на второе слово, назвав букву М. Такая стратегия приведет Ваню к выигрышу, так как последнюю букву слова — И — запишет именно он.
- Выигрышная стратегия есть у Вани, так как при любом выборе Пети, Ваня может перевести игру в проигрышную позицию для Пети, т.е. «перейти» на слово с четным количеством букв. Такая стратегия позволит Ване написать последнюю букву и тем самым выиграть игру.
А) Для выигрыша Пете достаточно выбрать первую букву слова с нечетным количеством букв, тогда последний ход делает Петя. При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, что своим первым ходом он должен выбрать букву И (слово ИКЛМНИКЛМНХ из 11 букв). Ване придется выбрать букву К. Таким образом, они последовательно будут называть буквы первого слова, пока Петя не выберет последнюю букву Х. На этом игра закончится выигрышем Пети. При данной стратегии возможна только одна партия. Заключением партии будет написано слово ИКЛМНИКЛМНХ.
Б) При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, чтобы выбрать слово с нечетным количеством букв, т.к. при такой стратегии последнюю букву в любом случае записывает Петя. Т.о., Петя должен выбрать букву Т, т.к. в первом слове 99 букв.
Дерево возможных партий:
* Для Вани отображены только ходы по стратегии
** Красный круг означает выигрыш
Подробней с решением задания про слова ознакомьтесь в видеоуроке (аналитическое решение):
📹 YouTube здесь
Видеорешение на RuTube здесь
Решение задач теории игр в MS
Exsel на примере задания ЕГЭ по информатики 19, 20, 21
Задача Два игрока
Петя и Ваня играют в следующую игру- перед ними лежит 2 кучи камней, игроки
ходят по очереди, первым ходит Петя, вторым Ваня. За один ход игрок может
добавить в любую кучу 1 камень или увеличить кол-во камней в 2 р . Игра
заканчивается, когда камней в обеих кучах становится не менее 53. Победителем
считается тот кто последним сделал ход. На начальном этапе игры в одной куче 9
камней, а во второй куче S камней
1 ≤ S≤43
Задача 19
Известно, что Ваня выиграл своим первым ходом
после неудачного ход Пети
Укажите минимальное кол-во камней S при такой ситуации
1.В ячейку в3 ввести 1 куча. В ячейку с3
ввести 2 куча В ячейку с4 ввести S. В ячейку в5 ввести 9. В
ячейку с5 ввести 5.
2. Построить таблицу от ячнйки d4 до g8
3. Ячейки d4 e4 объединить в них напечатать Петя, а в ячейки f4
Ваня, в ячейки g4 итог
ТО общий вид таблицы будет иметь вид
D |
E |
F |
G |
||
3 |
|||||
4 |
ПЕТЯ |
ВАНЯ |
ИТОГ |
||
5 |
|||||
6 |
|||||
7 |
|||||
8 |
|||||
4. Необходимо разобрать все возможные ходя
Пети для этого в ячейку D5 ввести B5+1,
первый возможный слабый ход, в ячейку E5 *с5
5. В ячейку D6 ввести в5,
те кол-во камней без изменения. В ячейку Е6 ввести с5+1, те кол-во камней без
изменения.
6. В ячейку D7 ввести
в5*2, в ячейку е7 ввести с5, в ячейку D8 ввести в5, в
ячейку е8 ввести с5*2,
ТО 1 чсть таблицы заполняется всевозможными
ходами Пети выделить их цветом.
Самая важная часть в таблице в комбинации D8 и е8 – это сильные ходы Пети.
7. В ячейку F5 ввести
МАКС (D5:Е5)*2+МИН(D5:Е5) растягиваем
значение формулы на все область ячеек F.
8. В ячейках столбца итог необходимо выяснить
какой из вариантов даст победу , для этого в ячейку g5
ввести фор-лу ЕСЛИ (F5>=53; ‘’+’’; ‘’-’’) растягиваем знач-е фор-лы на все ячейки от g5 до g8
Если в таблице не появится плюс, то меняется
значение С5.
Задача 20
Найдите 2 значения S при
которых у Пети есть выигрышная стратегия , но должны выполняться два условия
— Петя может выиграть за один ход
— Петя может выиграть за 2-м ходом независимо
отходов Вани.
Найденные значения записать в порядке
возрастания.
1. Таблицу из первой части копируем в область ячеек I3
—N8
2. Добавим в таблицу допол. поля
Там где столбец Ваня , чтоб
их стало два
,
верхнюю строку объединить , а также столбец Безопасность перед столбцом Итог.
ТО общий вид таблицы будет иметь вид:
K |
L |
M |
N |
O |
P |
Q |
|
3 |
|||||||
4 |
ПЕТЯ |
ВАНЯ |
Петя |
Безоп-ть |
Итог |
||
5 |
|||||||
6 |
|||||||
7 |
|||||||
8 |
|||||||
3. В ячейку I3 ввести 1 куча, в ячейку J3 ввести 2
куча,в ячейку J4 — S , I5 ввести 9,
J5 -11 .
4.
Удалить значения из столбцов ходов Пети. В ячейку
к5 ввести I5+1, L5 ввести J5, тогда
в ячейках ходов Вани вводятся формулы всех возможных его ходов В ячейку М5
ввести к5+1 , N5 ввести J5, М6
ввести к5, N6 ввести L5+1, , М7
ввести к5*2, N7 ввести L5, , М8
ввести к5, N8 ввести L5*2
ТО
будут перебраны все возможные варианты ходов Вани, тогда ходы Пети должны быть
все сильные.
Для
этого в столбец О5 вводится фор-ла МАКС (м5: N 5)*2+МИН(м5:
N 5), растягиваем знач-е этой фор-лы на область всех ячеек
в низ.
5. Т.к надо оценить игру Пети в столбце Итог вводят фор-лу ЕСЛИ (О5>=53; ‘’+’’; ‘’-’’) растягиваем знач-е этой
фор-лы на область всех ячеек в низ.
6. Т.к надо , чтоб выиграл Петя проконтролировать чтобы не выиграл Ваня
первым ходом именно для этой цели нужен столбец безопасность. В ячейку Р5
ввести фор-лу
ЕСЛИ
(м5+ N 5 >=53;
‘’+’’; ‘’-’’) растягиваем знач-е этой фор-лы на область всех ячеек в низ.
7.
Построенная таблица — это только один вариант
поведения Пети при игре, поэтому копируем таблицу ниже 4 раза не пропуская ни
одной строки, те вплотную. По следующему принципу:
ё
8. Внесем следующие изменения в скопированную часть
В К10 ввести I5, L 10 ввести J5 +1 (это будет второй возможный
выигрышный ход); в К15 ввести I5*2, L 15 ввести J5(это будет 3 возможный выигрышный ход);в К20- I5, в L 20 — J5*2(это будет 4 возможный выигрышный ход);.
Остальные
столбцы заполнятся автоматически благодаря относительной адресации.
9.Теперь необходимо просмотреть и проанализировать значения ячейки J5. Изменяя в ней значения по возрастанию до тех пор пока плюсы не
появятся в столбце Итога причем плюсы должны быть во всех четырех строках каждого
из 4 вариантов ходов а столбец безопасность должен быть отрицательным во всех 4
строках.
Задача 21
Сколько существует значений S которых одновременно выполняются два условия
— у Вани есть выигрышная стратегия при которой он выиграет 1 или 2 ходом
при любой игре Пети. —
у Вани нет стратегии, которая позволит ему гарантированно выиграть 1
ходом. С учетом полученного в задачи 20
можно уверенно утверждать, что выигрышные ходы Вани (9;16) и (9; 21) это
возможно при ходах Пети (9;15) и (9; 20). Решение этой задачи электронным
способом возможно только посте решения 19 и 20 зад на одной предметной
области. 1. Для решения
этой задачи скопируем таблицу из задания задачи 20 в область ячеек от U до AA в соответствии изображения
Внести изменения в значение столбцов S И T.
2.Очищаем значение столбцов игры Пети U И V.
Добавляем дополнительные столбцы в таблицу у
Пети будет два варианта ходов , поскольку в задании выигрыш может наступит и
на 1 и на 2 ходе.
ТО общий вид таблицы будет иметь вид:
Причем протяженность таблицы будет от столбцов
от U до АС, и от строк от 4 до 23 .
3. В ячейку U 5 ввести S5+1, а в ячейку V5 ввести Т5.
Ваня на подобный ход может ответить 4 разными
вариантами. Для х реализации очищаем все значения столбцов w и x.
В ячейки вводим фор-лы: w5=
U5+1; х2= V5; w10=
U5;х10= V5+1; w15=U5*2;х15=V5; w20= U5;х20= V5*2.
4. Для оценки возможных вариантов ходов Пети
скопировать данные из ячеек М5- N8 в ячейки y5-z8 из таблицы предыдущего задания. Формулы при
копировании изменятся в виду относительной адресации, хотя при копировании это
должно быть проконтролировано. Копируем эти значения и во все остальные ячейки y, z.
5. Второй ход Вани должен быть обязательно сильным, поэтому в ячейку
АА5 вводится фор-ла МАКС (y5: z5)*2+МИН(y5:
z5) ), растягиваем знач-е этой фор-лы на область всех
ячеек в низ.
Далее необходимо внести изменения в столбец Безопасность В ячейку АВ5
ввести фор-лу:
ЕСЛИ (y5+ z5>=53; ‘’+’’; ‘’-’’) , растягиваем знач-е этой
фор-лы на область всех ячеек в низ.
6. Для изменения столбца ИТОГ в ячейку АС5 вводится фор-ла: ЕСЛИ (АА5>=53; ‘’+’’; ‘’-’’) , растягиваем знач-е этой
фор-лы на область всех ячеек в низ.
7. Нельзя не учесть вариант при котором Ваня выигрывает первым ходом
для этого в ячейку х7 вводится фор-ла: ЕСЛИ (w5+ x5>=53; ‘’+’’; ‘’-’’) копировать
эту фор-лу в ячейки х12, х17, х22.
На основе предыдущего задания был сделан вывод что оптимальные s
либо 20, либо 15, поэтому рекомендуется проверку начать именно с
этих значений.
В ячейку s9 ввести 15, а в s10
ввести 20.
8.Полученная таблица отражает только 1 ход, а
их более, поэтому копируем эту таблицу ниже 4 раза в сплошную, тогда таблица
получится протяженностью до 64 строки. Внесем изменения в скопированную
таблицу: U25= s5+1; V25=Т5+1; U45= s5*2; V45=Т5; U65= s5; V65=Т5*2.
Для анализа заполненной таблицы введем в т5
значение 15 . Первым делом просматриваются ячейки х7, х12, х17, х22, если там
появится + , что Ваня выигрывает первым ходом и второй уже не нужен. Затем там
где в ячейках х плюсы не найдены просматривается столбец ИТОГ, там должны
встретится плюсы в 4-х подряд идущих строках , а безопасность должна идти с -.
Проделывается тоже самое для значения т5=20.
Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 2023!
Сегодня разберём задачи из 19, 20 и 21 задания ЕГЭ по информатике. Для этих задач существует спасительный шаблон на Python, который позволяет получить на них правильные ответы и затратить минимум сил и времени.
Приступим к первой серии задач из демоверсии ЕГЭ по информатике 2021 года.
Задание 19 (Демо 2021)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат
две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один
ход игрок может добавить в одну из куч (по своему выбору) один камень
или увеличить количество камней в куче в два раза. Например, пусть
в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем
обозначать (10, 5). Тогда за один ход можно получить любую из четырёх
позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы,
у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах
становится не менее 77. Победителем считается игрок, сделавший
последний ход, т.е. первым получивший такую позицию, при которой
в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче –
S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может
выиграть при любых ходах противника. Описать стратегию игрока – значит
описать, какой ход он должен сделать в любой ситуации, которая ему может
встретиться при различной игре противника. В описание выигрышной
стратегии не следует включать ходы играющего по этой стратегии игрока,
не являющиеся для него безусловно выигрышными, т.е. не являющиеся
выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого
хода Пети. Укажите минимальное значение S, когда такая ситуация
возможна.
Решение:
Решим задачу с помощью шаблона на языке программирования Python. Если хотите ознакомится с аналитическим решением задач на теорию игр, можете посмотреть мои статьи по 19 Заданию, 20 Заданию, 21 Заданию. Но с помощью шаблонов на экзамене решать быстрее и легче.
Введём параметр p, который будет олицетворять позицию игры (ход).
Начальная позиция | Ход Пети | Ход Вани | Ход Пети | Ход Вани | Ход Пети | |
p | 1 | 2 | 3 | 4 | 5 | 6 |
def F(x, y, p): if x + y >= 77 and p==3: return True if x + y < 77 and p==3: return False return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1) for s in range(1, 70): if F(s, 7, 1): print(s)
Заводим функцию F. Она принимает параметры: x — количество камней в одной куче, y — в другой, p-позиция игры.
Дальше описываем победу. Если x+y>=77 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.
Если, позиция уже равна 3, но сумарное количество камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).
Если мы не вышли на первых двух условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.
Т.к. здесь формулировка: «Известно, что Ваня выиграл своим первым ходом после неудачного первого
хода Пети.», то между функциями ставим союз ИЛИ (or).
В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи. Значение p всегда увеличиваем на 1.
Ответ: 18
Задание 20 (Демо 2021)
Для игры, описанной в предыдущем задании, найдите два таких значения S,
при которых у Пети есть выигрышная стратегия, причём одновременно
выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как
будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Решение:
Легко переделать из прошлой задачи.
def F(x, y, p): if x + y >= 77 and p==4: return True if x + y < 77 and p==4: return False if x + y >= 77: return False if p%2==0: return F(x+1, y, p+1) and F(x*2, y, p+1) and F(x, y+1, p+1) and F(x, y*2, p+1) else: return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1) for s in range(1, 70): if F(s, 7, 1): print(s)
Теперь должен выигрывать Петя на своём втором ходе. Поэтому в условиях ставим позицию p=4.
Добавляется третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.
Здесь вопрос отличается от 19 задания. Здесь Петя должен побеждать при любом ходе соперника, а не при одном неудачном ходе Вани, поэтому добавляется ещё условие.
Для чётных p (это ходы Пети), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае.
Для нечётных p (это ходы Вани), возвращаем ходы через or.
Ответ:
Задание 21 (Демо 2021)
Для игры, описанной в задании 19, найдите минимальное значение S, при
котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть
первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно
выиграть первым ходом.
Решение:
Опять используем прошлый шаблон, но немного модернизируем.
def F(x, y, p): if x + y >= 77 and (p==3 or p==5): return True if x + y < 77 and p==5: return False if x + y >= 77: return False if p%2==1: return F(x+1, y, p+1) and F(x*2, y, p+1) and F(x, y+1, p+1) and F(x, y*2, p+1) else: return F(x+1, y, p+1) or F(x*2, y, p+1) or F(x, y+1, p+1) or F(x, y*2, p+1) def F1(x, y, p): if x + y >= 77 and p==3: return True if x + y < 77 and p==3: return False if x + y >= 77: return False if p%2==1: return F1(x+1, y, p+1) and F1(x*2, y, p+1) and F1(x, y+1, p+1) and F1(x, y*2, p+1) else: return F1(x+1, y, p+1) or F1(x*2, y, p+1) or F1(x, y+1, p+1) or F1(x, y*2, p+1) for s in range(1, 70): if F(s, 7, 1): print(s) print() for s in range(1, 70): if F1(s, 7, 1): print(s)
Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).
Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.
В первой функции получилось 30,33, а во второй результатов нет. Получается ответ 30.
Ответ: 30
Следущая вариация задач отличается от первой лишь задачей в 19-ом задании. Рассмотрим демоверсию ЕГЭ по информатике 2022. Так же в этой серии задач будет одна куча, но из-за этого шаблон практически никак не меняется.
Задание 19 (Демо 2022)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит
куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход
игрок может добавить в кучу один камень или увеличить количество камней
в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть
неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится
не менее 29. Победителем считается игрок, сделавший последний ход,
т.е. первым получивший кучу, в которой будет 29 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может
выиграть при любых ходах противника. Описать стратегию игрока – значит
описать, какой ход он должен сделать в любой ситуации, которая ему может
встретиться при различной игре противника. В описание выигрышной
стратегии не следует включать ходы играющего по этой стратегии игрока,
не являющиеся для него безусловно выигрышными, т.е. не являющиеся
выигрышными независимо от игры противника.
Укажите такое значение S, при котором Петя не может выиграть за один ход,
но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение:
Здесь вопрос отличается от прошлой 19-ой задачи. Здесь Петя должен выиграть в любом случае. Мы эту задачу можем воспринимать, как 20-ую из демоверсии 2021. Ведь там тоже игроку нужно обязательно было побеждать. Осталось написать шаблон с соответствующими параметрами.
def F(x, p): if x>=29 and p==3: return True if x<29 and p==3: return False if x>=29: return False if p%2==1: return F(x+1, p+1) and F(x*2, p+1) else: return F(x+1, p+1) or F(x*2, p+1) for s in range(1, 29): if F(s, 1): print(s)
Заводим функцию F. Т.к. у нас одна куча, то она принимает параметры: x — количество камней в куче, p-позиция игры.
Дальше описываем победу. Если x>=29 и позиция равна 3 (1 Ход Вани), то возвращаем True, что означает победу.
Если, позиция уже равна 3, но камней меньше, чем должно быть для победы, то возвращаем False (проигрыш).
Третье условие. Если кто-то выиграл, но на первых двух условиях мы не вышли из функции, то, значит, выиграл не тот, кто нам нужен, следовательно, возвращаем Fasle.
Если мы не вышли на первых трёх условиях, то, значит, продолжаем прокручивать ходы, рекурсивно запускаем функцию F.
Для нечётных p (это ходы Вани), возвращаем разные ходы через and, т.к. он должен побеждать в любом случае. При этом увеличиваем на 1 значение p.
Для чётных p (это ходы Пети), возвращаем ходы через or.
В конце перебираем все возможные значения для s через цикл for, ищём те значения, которые подходят по условию задачи.
Ответ: 14
Задание 20 (Демо 2022)
Для игры, описанной в задании 19, найдите два таких значения S, при
которых у Пети есть выигрышная стратегия, причём одновременно
выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как
будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Решение:
Задача точно такая же, как и в 19 задании, только теперь обязательно должен побежать Петя на своём втором ходу (p=4), при любой игре Вани.
Пишем тот же шаблон, немного отредактировав его.
def F(x, p): if x>=29 and p==4: return True if x<29 and p==4: return False if x>=29: return False if p%2==0: return F(x+1, p+1) and F(x*2, p+1) else: return F(x+1, p+1) or F(x*2, p+1) for s in range(1, 29): if F(s, 1): print(s)
Получается 7 и 13.
Ответ:
Задание 21 (Демо 2022)
Для игры, описанной в задании 19, найдите значение S, при котором
одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть
первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть
первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.
Решение:
Опять используем прошлый шаблон, но немного модернизируем.
def F(x, p): if x>=29 and (p==3 or p==5): return True if x<29 and p==5: return False if x>=29: return False if p%2==1: return F(x+1, p+1) and F(x*2, p+1) else: return F(x+1, p+1) or F(x*2, p+1) def F1(x, p): if x>=29 and p==3: return True if x<29 and p==3: return False if x>=29: return False if p%2==1: return F1(x+1, p+1) and F1(x*2, p+1) else: return F1(x+1, p+1) or F1(x*2, p+1) for s in range(1, 29): if F(s, 1): print(s) print() for s in range(1, 29): if F1(s, 1): print(s)
Здесь Ваня должен выигрывать либо на первом своём ходе (p=3), либо на втором своём ходе (p=5).
Т.к. Ваня не должен гарантированно выиграть своим первым ходом, то мы создаём ещё одну функцию F1, похожую на основную функцию F, которая вычисляет, когда Ваня именно гарантированно выигрывает на своём первом ходе (p=3). И, затем, мы из тех чисел, которые получились в первой функции F, исключаем числа, которые получились во второй функции F1.
В первой функции получилось 12,14, а во второй 14. Получается ответ 12.
Ответ: 12
На сегодня всё. Мы рассмотрели самые распространённые вариации задач из 19-21 задания и подобрали к ним «противоядие». До новых встреч!
В первой 21 задаче в функции F1 только камни x сраниваются с 77. Там надо x + y как в основной функции?
Да, Вы правы, нужно x+y писать. Исправил, спасибо!
Почему начальная позиция p=1? Нельзя ли её сделать р=0?
Дабы избежать у учеников путаницы в голове по нумерации ходов. Или в этом скрывается ошибка?
Извините хотел оперативный ответ от Мастера, т.к. нет времени на эксперименты.
На мой взгляд, можно, поменяв соответствующие параметры тоже. Но не будет ли путаницы, если ваши ученики будут находить решения в интернете, где начинается p c 1.
В первом 19ом задании в функции def мне кажется, что не хватает строки if x + y >= 77: return False
Спасибо за Ваш труд!
Нет, там всё в порядке. В формулировке, когда «после неудачного первого хода Пети», можно писать два условия.
я не понимаю почему вы в первых задачах пишите в конце программы строку » if F1(s, 7, 1):»
Проверяем подходит ли значение s под условие задачи. Семёрка — это количество каменей в первой куче.
Спасибо, за последовательность объяснения. все очень понятно.
почему то в 20 задании находит только одно значение, уже несколько вариантов КИМа так, код написан правильно. В чём причина может быть?
Пришлите ссылку на задание.
Задание 21 из КИМа ЕГЭ 2023 по информатике 17 вариант(к примеру). Можно положить 1 камень или умножить количество на 2, Если больше или равно 144 в сумме двух куч, то победа.В первой куче 3 камня, во второй 1
от 1 до 140(включительно). Условия те же. Также неверные ответы получаются в 19 и 20 заданиях. Код правильный
КИМ это оффициальный сборник вариантов в виде книжки. Могу условия на почту скинуть(хотя вроде расписал всё), тут ограничение символов
Понятно, тогда посмотрю и напишу здесь, что думаю.
Решил 17 вариант (задания 19-21) из сборника 2023 года Крылова, Чуркиной по схеме из этой статьи. Ответы сошлись. Могу вам прислать решения, если вы напишите в группе в вк.
Пройти тестирование по этим заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word
1
Задания Д26 C3 № 4861
Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или 10 камней. Например, имея кучу из 7 камней, за один ход можно получить кучу из 8 или 17 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 31. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 31 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 30.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы.
б) Укажите такое значение S. при котором Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.
2. Укажите два значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Вова. Для указанных значений S опишите выигрышную стратегию Паши.
3. Укажите значение S, при котором у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, однако у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вовы. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.
2
Задания Д26 C3 № 4867
Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или 10 камней. Например, имея кучу из 7 камней, за один ход можно получить кучу из 8 или 17 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 40.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы.
б) Укажите такое значение S. при котором Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.
2. Укажите два значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Вова. Для указанных значений S опишите выигрышную стратегию Паши.
3. Укажите значение S, при котором у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, однако у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вовы. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.
3
Задания Д26 C3 № 4958
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится более 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 101 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 100.
Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения и выигрывающий ход Пети.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
2. Укажите два значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для указанных значений S опишите выигрышную стратегию Пети.
3. Укажите такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани. Представьте его в виде рисунка или таблицы. Для каждого ребра дерева укажите, кто делает ход, для каждого узла — количество камней в позиции.
4
Задания Д26 C3 № 5069
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится более 200. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 201 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 200.
Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения и выигрывающий ход Пети.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
2. Укажите два значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть первым ходом, но (б) Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.
3. Укажите такое значение S, при котором
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в позиции.
5
Задания Д26 C3 № 5225
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится более 200. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 201 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 200.
Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения и выигрывающий ход Пети.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
2. Укажите два значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть первым ходом, но (б) Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.
3. Укажите такое значение S, при котором
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в позиции.
Пройти тестирование по этим заданиям
МЕТОДИКА РЕШЕНИЯ ЗАДАЧ ЕГЭ ПО ИНФОРМАТИКЕ И ИКТ С ИСПОЛЬЗОВАНИЕМ ПОНЯТИЯ «ВЫИГРЫШНОЙ СТРАТЕГИИ»
Выступление на республиканском семинаре «Об особенностях преподавания информатики в общеобразовательных организациях Республики Крым в 2018/2019 учебном году» 23.08.2018
Сабитова Диляра Арифовна, методист отдела дистанционного образования
ГБОУ ДПО РК КРИППО
-
Понятие выигрышной стратегии. Типы задач
-
Разбор задания № 26 демонстрационной версии ЕГЭ-2018
-
Разбор проекта демонстрационной версии ЕГЭ-2018. Фишки
-
Разбор задачи основного периода ЕГЭ-2018. Две кучи
-
Разбор задачи №26 системы «Эксперт ЕГЭ». Буквы
-
Понятие выигрышной стратегии. Типы задач
Стратегия игрока определяет его действие в любой момент игры и для каждого возможного течения игры.
Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
-
Разбор задания № 26 демонстрационной версии ЕГЭ-2018
Задача №26
Решение (таблица):
-
Вопрос 1а. Последним ходом может быть «+1» или «*2». Выиграть последним ходом «+1» можно, если S = 28. Ходом «*2» можно выиграть из любой позиции при S 14 (сюда входит и 28). Можно составить таблицу, в которой «В1» обозначает выигрыш за один ход:
S |
1 |
2 |
… |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
Поэтому ответ должен быть такой:
«1а. Петя может выиграть за один ход при любом S =15,…28. Он должен увеличить вдвое число камней, при этом в куче всегда получится не менее 30 камней.»
-
Вопрос 1б. Для ответа на этот вопрос нужно найти позицию, из которой все возможные ходы ведут к выигрышу за 1 ход, то есть к позиции, отмеченной в таблице как «В1». Например, это позиция при S = 14: ход «+1» ведёт в выигрышную позицию S = 15, а ход «*2» ведёт в выигрышную позицию S = 28. Поэтому позицию S = 14 отметим в таблице как «х1» (проигрыш за 1 ход):
S |
1 |
2 |
… |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
×1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
Ответ на вопрос 1б должен быть такой:
«1б. При S = 14 Петя не может выиграть в один ход, потому что при его ходе «+1» число камней в куче становится равно 15 (меньше 29), а при ходе «*2» число камней в куче становится равно 28 (также меньше 29). Других возможных ходов у Пети нет. Из любой позиции после одного хода Пети (это может быть 15 или 28), Ваня может выиграть своим первых ходом, удвоив количество камней в куче.»
-
Вопрос 2. Пете, для того, чтобы гарантированно выиграть на втором ходу, нужно из начальной позиции перевести игру в проигрышную позицию, отмеченную знаком «х1». Пока мы нашли одну такую позицию: S = 14. Петя может перевести игру в эту позицию из позиций
S = 13 (ходом «+1») и S = 7 (ходом «*2»)
В таблице отмечаем эти положения как «В2» – гарантированный выигрыш за 2 хода:
S |
1 |
… |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
В2 |
В2 |
×1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
Поэтому ответ должен быть такой:
«2. Из позиций S = 7 и S = 13 Петя не может выиграть в один ход, но Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. При S = 13 ходом «+1» Пете нужно перевести игру в позицию S = 14, которая является проигрышной (см. ответ на вопрос 1б). При S = 7 Петя переводит игру в ту же позицию ходом «*2».»
-
Вопрос 3. Нужно найти такую позицию, из которой оба возможных хода Пети ведут в позиции, отмеченные в таблице как «В1» (выигрыш в 1 ход) и «В2» (выигрыш в 2 хода). Например, это позиция S = 12, из которой можно «попасть» только в S = 13 («В2») и S = 24 («В1»). Отмечаем эту позицию как «х2» – проигрыш в два хода:
S |
1 |
… |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
В2 |
×2 |
В2 |
×1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
В1 |
Поэтому ответ должен быть такой:
«3. В позиции S = 12 у Вани есть выигрышная стратегия, которая позволяет ему выиграть первым или вторым ходом. Если Петя выбирает ход «+1», в куче становится 13 камней и Ваня выигрывает на 2-м ходу (см. ответ на вопрос 2). Если Петя выбирает ход «*2», Ваня выигрывает первым ходом, удвоив число камней в куче.»
-
Остается нарисовать дерево возможных вариантов игры из позиции S = 12. Для этого используем построенную таблицу:
Здесь красным цветом выделены позиции, в которых игра заканчивается.
На каждом шаге мы рассматриваем все возможные ходы Пети и только один лучший ход Вани. Например, в позиции S = 15 Ваня может сделать ход «+1» и получить 16 камней в куче, но тогда он проиграет (Петя следующим ходом удвоит число камней и получит 32 камня). Этот ход мы не рассматриваем, потому что мы хотим доказать, что у Вани есть выигрышная стратегия – ему достаточно хода «*2», после которого он выиграет. В то же время нужно рассмотреть все возможные ответы Пети, чтобы доказать, что у него нет шансов на выигрыш при правильной игре Вани. В этом суть теории игр – добиться лучшего результата в худшем случае, то есть при безошибочной игре соперника.
-
Разбор проекта демонстрационной версии ЕГЭ-2018. Фишки
Задача №26
Два игрока, Петя и Ваня играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочередно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 23, нельзя сделать фишку, на которой написано 32. Первый ход делает Петя, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает. Будем называть партией любую допустимую правилами последовательность ходов игроков, приводящую к завершению игры. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит указать, какую фишку он должен выставить в любой ситуации, которая ему может встретиться при различной игре противника.
Пример. Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23
Пусть первый ход Пети 12. Ваня может поставить 21, 22 или 23. Предположим, он ставит 21. Получим цепочку 12-21. Петя может поставить 11 или 13. Предположим, он ставит 11. Получим цепочку 12-21-11. Ваня может поставить только фишку со значением 13. Получим цепочку 12-21-11-13. Перед Петей в кучке остались только фишки 22 и 23, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Ваня выиграл.
Выполните следующие три задания при исходном наборе фишек {12, 14, 21, 22, 24, 41, 42, 44}.
Задание 1.
а) Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.
б) Пусть Петя первым ходом пошел 42. У кого из игроков есть выигрышная стратегия в этой ситуации? Укажите первый ход, который должен сделать выигрывающий игрок, играющий по этой стратегии. Приведите пример одной из партий, возможных при реализации выигрывающим игроком этой стратегии.
Задание 2
Пусть Петя первым ходом пошел 44. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвертым ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах – цепочку фишек, получившуюся после этого хода.
Задание 3
Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.
Задание 1а.
-
партия заканчивается, когда цепочка закончилась на цифре X и не осталось ни одной фишки, которая бы начиналась с этой цифры;
-
меньше всего фишек заданного набора начинается с цифры 1 (только 12 и 14), поэтому самой короткой партией, вероятно, будет партия, которая заканчивается на цифре 1 (фишкой 21 или 41), при этом фишки 12 и 14 должны быть выставлены;
-
соединить эти фишки в цепочку можно с помощью фишек 21 или 41, таким образом, получается две возможных самых коротких партии:
12 – 21 – 14 – 41 и 14 – 41 – 12 – 21.
В ответе достаточно привести одну из них.
Задание 1б. (Идея решения – А. Сидоров).
-
заметим, что эта игра напоминает «одностороннее домино», в котором фишки можно выставлять только одной стороной и наращивать цепочку можно тоже только с одной стороны;
-
среди фишек есть две особые – 22 и 44 («дубли») они служат для того, чтобы передать ход сопернику; если выставить дубль, оказавшись в проигрышной позиции, то эта проигрышная позиция «переходит» к сопернику
-
пока построим дерево без учёта дублей, то есть для набора фишек
12, 14, 21, 24, 41 и 42
-
по условию Петя выставляет первым ходом фишку 42, дальнейшие варианты развития игры показаны на схеме:
-
итак, мы видим, что если никто из игроков не выставляет дублей, то выигрывает Ваня во всех случаях, причем все партии заканчиваются на цифре 4
-
если Ваня в ходе игры не выставит дубль, то в конце каждой ветки Петя может выставить дубль 44 и выиграть:
-
поэтому теперь посмотрим, где Ваня может изменить игру дублями; Ване нет смысла ставить дубль 44, потому что во всех вариантах партий он уже есть (с выигрышем для Пети), так что выставление дубля 44 просто перемещает его в середину цепочки, не изменяя её длину
-
у Вани в распоряжении есть еще дубль 22; на следующем рисунке выделены ходы, где Ваня может поставить этот дубль:
П
-
использование дубля 22 действительно изменяет игру, так как удлиняет цепочки на 1, при этом выигрывает Ваня:
а) Ваня может своим первым ходом выставить дубль 22, при этом он всегда выиграет
б) Ваня может первым ходом выставить фишку 21, при этом получив ход в позиции, когда текущая цепочка заканчивается на 2, он выставляет дубль 22 и выигрывает
Задание 2.
-
построим дерево игры для случая, когда Петя в самом начале ходит фишкой 44, «забыв» пока про дубль 22:
-
по дереву видим, что при игре без дубля 22 выигрывает Петя своим третьим или четвёртым ходом
-
Ваня может изменить ход игры дублем 22 только в выделенных узлах, поэтому
-
если Ваня походит фишкой 41, Петя должен ответить ходом 14
-
если Ваня походит фишкой 42, Петя должен ответить ходом 21
-
при записи неполного дерева игры, доказывающего выигрыш Пети, нужно учесть, что по условию задачи нужно представить дерево с выигрышем именно в 4 хода, хотя Петя имеет стратегию выигрыша за 3 хода:
Задание 3.
-
в задании 2 выигрывает Петя, поэтому нужно убрать две фишки таким образом, чтобы всегда выигрывал Ваня
-
заметим, что нам нужно доказать, что Ваня выигрывает ВСЕГДА, при любом первом ходе Пети; это значит, что построение одного дерева (при конкретном первом ходе) ничего не доказывает
-
заметим, что последней цифрой цепочки для данного набора фишек всегда будет 1, 2 или 4, поэтому можно построить такой граф возможных переходов (например, ребро перехода 1 2 соответствует фишке 12, а петля у узла 2 – фишке 22):
по каждому ребру этого графа можно пройти только один раз (каждая фишка выставляется один раз)
-
по этому графу видно, что если убрать две петли, остается граф с одинаковой ситуацией для каждой из вершин: есть два контура, проходящие в разных направлениях через все узлы
-
итак, если убрать два дубля, то всегда будут выставлены 4 или все 6 фишек, поскольку 4 и 6 – чётные числа, то всегда выиграет Ваня, потому что он делает все ходы с чётными номерами; например, при первом ходе Пети 12 возможны партии:
-
– 21 – 14 – 41 или 12 – 24 – 41 – 14 – 42 – 21.
-
Разбор задачи основного периода ЕГЭ-2018. Две кучи
Задание №26 (2018 г, основной период)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 63. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 63 камня или больше.
В начальный момент в первой куче было пять камней, во второй куче – S камней; 1 ≤ S ≤ 57.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Выполните следующие задания.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может выиграть за один ход.
б) Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 2
Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы).
В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать ходы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.
Решение:
-
Задание 1. В первой куче – 5, во второй — 1…57.
Если во второй куче было S камней, то после первого хода Пети количество камней в двух кучах может стать равным
6+S (после добавления 1 камня в любую кучу)
10+S (после удвоения первой кучи)
5+2S (после удвоения второй кучи)
Выписываем условия выигрыша на первом ходу для всех трёх вариантов
6 + S 63 S 57
10 + S 63 S 53
5 + 2S 63 S 29
Отсюда следует, что при S 29 Петя выиграет первым же ходом, удвоив число камней во второй куче.
S=29,…57
-
S=29. Если Петя сделал неудачный ход, значит он имел выигрышную стратегию, при которой необходимо было увеличить вторую кучу вдвое. Пусть он при этом положил в первую или во вторую кучу 1 камень и привел Ваню к выигрышу. Значит у Вани была позиция (5, 30) или (6, 29). Ваня удваивает вторую кучу и выигрывает, получив позицию (5, 60) или (6, 58).
Задание 2.
S=28.
В позиции (5,28) своим первым ходом Петя должен добавить 1 камень в первую кучу, приведя противника к проигрышной ситуации (6, 28). Вторым ходом Петя удваивает количество камней во второй куче и выигрывает.
(5, 28) |
П1 |
В1 |
П2 |
(5+1=6, 28) |
(7, 28) |
(7, 56) |
|
(6, 30) |
(6, 60) |
||
(12, 28) |
(12, 56) |
||
(6, 56) |
(6, 112) |
Задание 3.
Начальная позиция (5, 27) |
П1 |
В1 |
П1 |
В2 |
(5+1=6, 27) |
(6, 27+1=28) |
(7, 28) |
(7, 56) |
|
(6, 30) |
(6, 60) |
|||
(12, 28) |
(12, 56) |
|||
(6, 56) |
(6, 112) |
|||
(5, 27+1=28) |
(5+1=6, 28) |
(7, 28) |
(7, 56) |
|
(6, 30) |
(6, 60) |
|||
(12, 28) |
(12, 56) |
|||
(6, 56) |
||||
(5*2=10,27) |
(10,27*2=54) |
|||
(5, 27*2=54) |
(5*2=10, 54) |
Построим дерево возможных партий. Важно, что для проигрывающего (Пети) нужно обязательно рассмотреть все возможные ходы (чтобы доказать, что его ничто не может спасти), а для выигрывающего достаточно указать на каждом шаге один выигрывающий ход:
Задача №26 (Буквы)
Два игрока, Петя и Ваня играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Петя. Выигрывает тот, кто первый составит слово из заданного набора.
Пример. Пусть заданы слова {МАК, МЫЛО, РАМА, РАК}. На первом ходу Петя может написать букву М или Р. Пусть он написал букву М. В ответ Ваня может написать А или Ы. В первом случае получается МА, и Петя, дописав букву К, получает слово МАК из заданного набора и выигрывает. Во втором случае получается МЫ, Петя вынужден дописать Л и Ваня выиграет вторым ходом, дописав О и получив слово МЫЛО.
Задание 1.
а) Определите, у кого из игроков есть выигрышная стратегия для набора слов {ВАРЕНЬЕ, КОРОВА}. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.
б) Определите, у кого из игроков есть выигрышная стратегия для набора слов {НУБНУБ…НУБ, PUMAPUMA…PUMA}. В первом слове 55 раз повторяется слово НУБ, а во втором – 32 раза повторяется слово PUMA. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.
Задание 2
В наборе слов, приведённом в задании 1а, поменяйте местами две буквы в любом слове так, чтобы выигрышная стратегия была у другого игрока. Опишите эту стратегию. Определите, сколько различных партий может быть сыграно при этой стратегии и какое слово будет получено в каждом случае.
Задание 3
Дан набор слов {МОРОКА, МОРС, МОРОЗ, ПЛАХА, ПЛАТЬЕ, ПЛОМБА}. У кого из игроков есть выигрышная стратегия? Приведите в виде рисунка или таблицы дерево всех партий, возможных при этой стратегии.
-
Сначала предположим, что в наборе одно слово. Если игроки дописывают каждый раз по одной букве то очевидно, что первый из них (Петя) допишет все нечётные буквы, а второй (Ваня) – все чётные. Таким образом, если в слове нечётное число букв, выиграет Петя, а если чётное – Ваня.
-
Если слов несколько, то стратегия Пети состоит в том, чтобы все время выбирать такое продолжение, при котором в итоге будет получено слово с нечётным количеством букв, а Ваня наоборот должен пытаться перескочить на слово с чётным количеством букв.
-
Задание 1а. В слове ВАРЕНЬЕ – 7 букв (нечётное количество, выиграет Петя), а в слове КОРОВА – 6 букв (чётное количество, выиграет Ваня). Петя ходит первый и может написать букву В. Поскольку слово КОРОВА начинается с другой буквы, Ваня будет вынужден «идти» по слову ВАРЕНЬЕ и проиграет. Этот вариант – единственный, то есть возможна только одна партия, при которой Петя следует своей стратегии, она заканчивается словом ВАРЕНЬЕ.
Задание 1а.
-
Для набора слов {ВАРЕНЬЕ, КОРОВА} выигрышная стратегия есть у Пети.
-
Выигрышная стратегия Пети состоит в том, чтобы написать первую букву В. Далее остается только одно допустимое слово – ВАРЕНЬЕ, и Петя выиграет, так как в этом слове 7 букв и он допишет последнюю букву, имеющую нечётный номер.
-
При выбранной стратегии возможна только одна партия.
-
В результате этой партии получится слово ВАРЕНЬЕ.
-
Задание 1б. В первом слове набора 3*55 = 165 букв, нечётное количество. Поэтому если игра «пойдёт» по первому слову, то выиграет Петя. Во втором слове 4*32 = 128 букв, чётное количество. Поэтому если игра пойдёт по второму слову, выиграет Ваня. Слова начинаются с разных букв, поэтому Петя может выбрать, по какому слову пойдёт игра. Если он напишет букву Н, он выиграет.
Задание 1б.
-
Для заданного набора слов выигрышная стратегия есть у Пети.
-
Выигрышная стратегия Пети состоит в том, чтобы написать первую букву Н. Далее остается только одно допустимое слово – НУБНУБ…НУБ, и Петя выиграет, так как в этом слове нечётное количество букв (165) и он допишет последнюю букву, имеющую нечётный номер.
-
При выбранной стратегии возможна только одна партия.
-
В результате этой партии получится слово НУБНУБ…НУБ.
-
Задание 2. В наборе слов {ВАРЕНЬЕ, КОРОВА} первое слово имеет нечётное количество букв, а второе – чётное. Чтобы Ваня мог выиграть, он должен получить возможность «перескочить» на второе слово. Для этого при любом ходе Пети у Вани должен остаться выбор. Это возможно только в том случае, когда оба слова начинаются с одной и той же буквы. Поскольку разрешается переставлять буквы только в одном слове, мы не можем сделать, чтобы оба слова начинались с буквы К – в первом слове её нет. Но можно сделать так, чтобы оба слова начинались с буквы В, переставив буквы К и В в слове КОРОВА. Получается набор {ВАРЕНЬЕ, ВОРОКА}, и Ваня выигрывает, своим первым ходом дописав букву О к букве В, которую (обязательно!) напишет Петя.
Задание 2.
-
Для того, чтобы Ваня мог выиграть, во втором слове нужно поменять местами буквы К и В.
-
Так как оба слова начинаются с буквы В, Петя обязательно напишет букву В. Выигрышная стратегия Вани состоит в том, чтобы своим ходом дописать букву О. После этого игра «идёт» по слову ВОРОКА, в нём чётное количество букв и выигрывает Ваня, который допишет последнюю букву.
-
При выбранной стратегии возможна только одна партия.
-
В результате этой партии будет получено слово ВОРОКА.
-
Задание 3. Расположим слова в столбики по начальным буквам, на каждом шаге вниз стараясь сохранить наибольшую общую часть (маркером выделена часть слова, которая совпадает с предыдущим словом в том же столбике):
МОРОКА + ПЛАХА
+ МОРОЗ ПЛАТЬЕ
МОРС ПЛОМБА
Знаком «плюс» отмечены слова, имеющие нечётное количество букв – это выигрышные варианты для Пети.
-
Если Петя первой напишет букву М, для выигрыша ему нужно перейти на слово МОРОЗ, но как только он составит слово МОР, Ваня тут же допишет С и выиграет, получив слово МОРС.
-
Если Петя напишет букву П, Ваня вынужден написать Л (это вторая буква всех оставшихся допустимых слов). Теперь Петя может написать А или О. В обоих случаях Ваня может перевести игру на слова с чётным количество букв (ПЛАТЬЕ, ПЛОМБА) и выиграть. Таким образом, при этом наборе слов выигрышную стратегию имеет Ваня.
Задание 3.
-
Для набора слов {МОРОКА, МОРС, МОРОЗ, ПЛАХА, ПЛАТЬЕ, ПЛОМБА} выигрышная стратегия есть у Вани.
-
Дерево всех возможных партий приводится на рисунке. Для Пети мы рассматриваем все возможные ходы, для Вани – только выигрышный вариант на каждом шаге. Буквами над схемой обозначены игроки (П – ход Пети, В – ход Вани).
Вместо рисунка можно использовать таблицу (зелёным цветом отмечен выигрыш Вани):
Начальная позиция |
П |
В |
П |
В |
П |
В |
– |
М |
МО |
МОР |
МОРС |
||
П |
ПЛ |
ПЛА |
ПЛАТ |
ПЛАТЬ |
ПЛАТЬЕ |
|
ПЛО |
ПЛОМ |
ПЛОМБ |
ПЛОМБА |
-
Разбор задачи №26 системы «Эксперт ЕГЭ». Буквы
Решение.
-
Сначала предположим, что в наборе одно слово. Если игроки дописывают каждый раз по одной букве то очевидно, что первый из них (Петя) допишет все нечётные буквы, а второй (Ваня) – все чётные. Таким образом, если в слове нечётное число букв, выиграет Петя, а если чётное – Ваня.
-
Если слов несколько, то стратегия Пети состоит в том, чтобы все время выбирать такое продолжение, при котором в итоге будет получено слово с нечётным количеством букв, а Ваня наоборот должен пытаться перескочить на слово с чётным количеством букв.
-
Задание 1а. В слове АБВГДАБВГДХ – 11 букв (нечётное количество, выиграет Петя), а в слове ДГВБАДГВБА – 10 букв (чётное количество, выиграет Ваня). Петя ходит первый и может написать букву А. Поскольку второе слово начинается с буквы Д, Ваня будет вынужден «идти» по первому слову и проиграет. Этот вариант – единственный, то есть возможна только одна партия, при которой Петя следует своей стратегии, она заканчивается словом АБВГДАБВГДХ.
Задание 1а.
-
Для набора слов { АБВГДАБВГДХ, ДГВБАДГВБА } выигрышная стратегия есть у Пети.
-
Выигрышная стратегия Пети состоит в том, чтобы написать первую букву А. Далее остается только одно допустимое слово – АБВГДАБВГДХ, и Петя выиграет, так как в этом слове 11 букв и он допишет последнюю букву, имеющую нечётный номер.
-
При выбранной стратегии возможна только одна партия.
-
В результате этой партии получится слово АБВГДАБВГДХ.
-
Задание 1б. В первом слове набора 3*33 = 99 букв, нечётное количество. Поэтому если игра «пойдёт» по первому слову, то выиграет Петя. Во втором слове 4*44 = 176 букв, чётное количество. Поэтому если игра пойдёт по второму слову, выиграет Ваня. Слова начинаются с разных букв, поэтому Петя может выбрать, по какому слову пойдёт игра. Если он напишет букву Т, он выиграет.
Задание 1б.
-
Для заданного набора слов выигрышная стратегия есть у Пети.
-
Выигрышная стратегия Пети состоит в том, чтобы написать первую букву Т. Далее остается только одно допустимое слово – ТРИТРИ … ТРИ, и Петя выиграет, так как в этом слове нечётное количество букв (99) и он допишет последнюю букву, имеющую нечётный номер.
-
При выбранной стратегии возможна только одна партия.
-
В результате этой партии получится слово ТРИТРИ … ТРИ.
-
Задание 2. В наборе слов { АБВГДАБВГДХ, ДГВБАДГВБА } первое слово имеет нечётное количество букв, а второе – чётное. Чтобы Ваня мог выиграть, он должен получить возможность «перескочить» на второе слово. Для этого при любом ходе Пети у Вани должен остаться выбор. Это возможно только в том случае, когда оба слова начинаются с одной и той же буквы. Поскольку переставить буквы нужно в коротком слове, мы должны сделать так, чтобы оба слова начинались с буквы А. Поменяем первую букву Д во втором слове с буквой А, находящейся на 5 месте. Получим слово АГВБДДГВБА с четным количеством букв. Петя вынужден будет написать А, а Ваня вслед за ним пишет вторую букву второго (короткого) слова – Г. В результате Ваня выиграет написав последнюю четную букву А. Получится слово — АГВБДДГВБА . Можно поменять первую букву Д с последней буквой А и тогда получим слово — АГВБАДГВБД. Это слово также приведет к выигрышу Вани.
Задание 2.
-
Для того, чтобы Ваня мог выиграть, во втором слове нужно поменять местами буквы Д и А.
-
Так как оба слова начинаются с буквы А, Петя обязательно напишет букву А. Выигрышная стратегия Вани состоит в том, чтобы своим ходом дописать букву Г. После этого игра «идёт» по слову АГВБДДГВБА, в нём чётное количество букв и выигрывает Ваня, который допишет последнюю букву.
-
При выбранной стратегии возможна только одна партия.
-
В результате этой партии будет получено слово АГВБДДГВБА.
-
Задание 3. Расположим слова в столбики по начальным буквам, на каждом шаге вниз стараясь сохранить наибольшую общую часть (маркером выделена часть слова, которая совпадает с предыдущим словом в том же столбике):
ДРАТВА + КРОНА
ДРОН КРОШКА
+ ДРОЗД + КРОКОДИЛИЩЕ
Знаком «плюс» отмечены слова, имеющие нечётное количество букв – это выигрышные варианты для Пети.
-
Если Петя первой напишет букву Д, для выигрыша ему нужно перейти на слово ДРОЗД , но как только он составит слово ДРО, Ваня тут же допишет Н и выиграет, получив слово ДРОН.
-
Если Петя напишет букву К, Ваня вынужден написать Р (это вторая буква всех оставшихся допустимых слов). Теперь Петя может написать только О. Ваня может написать Ш и перевести игру на слово с чётным количество букв (КРОШКА) и выиграть. Таким образом, при этом наборе слов выигрышную стратегию имеет Ваня.
Задание 3.
-
Для набора слов {ДРАТВА, ДРОН, ДРОЗД, КРОНА, КРОШКА, КРОКОДИЛИЩЕ } выигрышная стратегия есть у Вани.
-
Дерево всех возможных партий приводится на рисунке. Для Пети мы рассматриваем все возможные ходы, для Вани – только выигрышный вариант на каждом шаге. Буквами над схемой обозначены игроки (П – ход Пети, В – ход Вани).
Вместо рисунка можно использовать таблицу (зелёным цветом отмечен выигрыш Вани):
Начальная позиция |
П |
В |
П |
В |
П |
В |
– |
К |
КР |
КРО |
КРОШ |
КРОШК |
КРОШКА |
Д |
ДР |
ДРА |
ДРАТ |
ДРАТВ |
ДРАТВА |
|
ДРО |
ДРОН |
— |
Использованные источники:
-
Демонстрационный вариант ЕГЭ по информатике и ИКТ 2018г (проект). [Электронный ресурс. Режим доступа: http://fipi.ru/]
-
Демонстрационный вариант ЕГЭ по информатике и ИКТ 2018г. [Электронный ресурс. Режим доступа: http://fipi.ru/]
-
К. Ю. Поляков. Материалы для подготовки ЕГЭ. [Электронный ресурс. Режим доступа: http://kpolyakov.spb.ru]
-
Критерии оценивания заданий с развернутым ответом. [Электронный ресурс. Режим доступа: http://85.142.162.117/exp/]
13
На этой странице вы узнаете
- Как выбрать пуленепробиваемую логику решения?
- Как будет выглядеть общая структура необходимых функций?
Чем пингвин-киборг круче пингвина-мужчины? Вторые имеют неограниченное количество камней и придумывают разнообразные азартные игры с ними. А пингвины-киборги довольно умны, чтобы не играть в азартные игры на свои драгоценные камни, и настолько самодостаточны, что играют только с собой.
Идея решения
В статье «Теория игр» мы подробно рассмотрели, как не проигрывать в играх с камнями или заранее знать, что проиграем. Если вы ещё не знакомы с этой темой, советуем сначала заглянуть в ту статью, а потом вернуться сюда.
Итак, мы мега-мозги в теории игр и полны решимости применять узнанное на практике. Пора заставить программу выполнить за нас всю работу.
Что в принципе позволяет нам найти необходимую стратегию? Взаимосвязь проигрышной и выигрышной стратегии. Мы решаем задачи постепенно и каждый раз опираемся на то, что уже точно установили:
1. Найти очевидные выигрышные позиции.
2. Определить самые простые проигрышные позиции.
3. Перейти к более сложным выигрышным или проигрышным позициям.
Неплохо было бы и программе дать знать, как найти и проверить выигрышные и проигрышные позиции. Здесь нам пригодятся функции из статьи «Функция и рекурсия».
- Одна функция будет проверять позиции на выигрыш за один ход.
- Другая будет проверять проигрышные позиции за один ход. Из них будут ходы в выигрышные, что мы определим с помощью первой функции.
- Третья сможет проверить более сложные выигрышные позиции. Они приведут в проигрышные, что мы определим с помощью второй функции.
Идея последовательного решения поможет нам выстроить любую логику и найти любую позицию. Самое приятное: считать все это придется не нам, а программе.
Реализация решения
Для решения задачи нужно придумать саму задачу. Пусть условие будет такое:
- Играют два пингвина — Петр и Виссарион. Петр ходит первым.
- Перед ними лежит одна куча камней. На своем ходу игрок может добавить в кучу 3 камня или увеличить количество камней в куче в 4 раза.
Например, если в куче находится 10 камней, игрок может увеличить это значение до 13 или до 40. - Игра продолжается до тех пор, пока в куче не окажется 203 камня или больше.
- Выигрывает тот, кто сделает последний ход.
В начале игры в куче лежало Х камней (1 <= X <= 202).
Общая структура функций будет достаточно простой:
1. В аргументах функции передадим текущее количество камней в куче.
2. Ключевая часть — проверка позиции. Организуем ее с помощью логических операторов и возможных ходов.
3. Функция может сразу возвращать значение условия — True или False — условие либо выполнилось, либо нет. Этого достаточно.
Проверка выигрыша за 1 ход
Из каких позиций Петр выиграет первым ходом?
Напомню:
Позиция, выигрышная за 1 ход, — та, из которой есть хотя бы один такой ход, который даст нам выигрышное значение.
Проверяем возможные ходы. Хотя бы один из них должен дать выигрышное значение — 203 и больше. Когда нужен “хотя бы один” — используем or.
Важно сформулировать задачу для программы как можно четче. Например, в дальнейшем функции может попасться на проверку значение, большее или равное 203. Нет необходимости рассматривать эту позицию, так как это уже выигрышное значение, выигрывать дальше из него нет никакого смысла. Учтем в условии: ранее достигнутое выигрышное значение не будет выигрышной позицией.
Итак, вид функции будет следующим:
def win1(X):
return (X < 203 and (X + 3 >= 203 or X * 4 >= 203))
Найдем с ее помощью все позиции, выигрышные за 1 ход. Используем цикл for и переберем диапазон значений Х. Найдя подходящее, занесем его в отдельный массив. Тогда мы сразу получим все подходящие значения и без проблем узнаем любую информацию о них: количество, минимальное или максимальное значение и так далее.
def win1(X):
return (X < 203 and (X + 3 >= 203 or X * 4 >= 203))
ans = []
for i in range(1, 203):
if win1(i):
ans.append(i)
print(len(ans))
_____________________________________________________________________
Вывод: 152
Проверка проигрыша за 1 ход
Из каких позиций у Пети нет никаких шансов обыграть Виссариона?
Напомним:
Позиция, проигрышная за 1 ход, — та, любой ход из которой ведет в выигрышную позицию, так выигрыш передается сопернику.
Проверка будет иметь несколько отличий:
- Выигрышную позицию проверим с помощью уже написанной функции win1 — будет ли новая позиция после нашего хода выигрышной.
- Так как каждый ход должен вести в выигрышную позицию, будем использовать and.
- Дополнительная проверка — из текущей позиции нельзя выиграть. Если из текущей позиции можно и выиграть, и проиграть — зачем проигрывать? Шансы на победу нас сейчас не интересуют.
Функция будет иметь следующий вид:
def loss1(X):
return ((not win1(X)) and win1(X + 3) and win1(X * 4))
Поиск подходящих значений будет происходить так же, как и в предыдущей задаче — перебором подходящих значений и их сохранением в массив:
def win1(X):
return (X < 203 and (X + 3 >= 203 or X * 4 >= 203))
def loss1(X):
return ((not win1(X)) and win1(X + 3) and win1(X * 4))
ans = []
for i in range(1, 203):
if loss1(i):
ans.append(i)
print(ans)
_____________________________________________________________________
Вывод: [48, 49, 50]
Проверка выигрыша за 2 хода
Рассмотрим особую позицию.
При каких условиях Петр однозначно обыграет Виссариона, но не с первого своего хода, а только со второго?
Хотя бы один ход из такой позиции должен передать проигрыш нашему сопернику.
Как будем действовать?
- “Хотя бы один ход” — используем or.
- Для проверки используем уже написанную функцию loss1 — будет ли позиция после нашего хода проигрышной.
- Дополнительная проверка по условию задачи — из текущей позиции нельзя выиграть за 1 ход.
Вид самой функции:
def win2(X):
return ((not win1(X)) and (loss1(X + 3) or loss1(X * 4)))
Поиск подходящих значений с ее помощью:
def win1(X):
return (X < 203 and (X + 3 >= 203 or X * 4 >= 203))
def loss1(X):
return ((not win1(X)) and win1(X + 3) and win1(X * 4))
def win2(X):
return ((not win1(X)) and (loss1(X + 3) or loss1(X * 4)))
ans = []
for i in range(1, 203):
if win2(i):
ans.append(i)
print(ans)
_____________________________________________________________________
Вывод: [12, 45, 46, 47]
Изучение теории игр — это замечательная возможность забрать по баллу за три задачи на ЕГЭ, с помощью практически одной и той же программы. Это номера 19, 20 и 21.
К тому же теория игр — важный аспект не только программирования, но и математики в целом. С позиций теории игр можно оценивать как законы спроса и предложения для экономических моделей, так и поведение людей с точки зрения психологии. Что общего между рекламными акциями двух крупных компаний (например, Nike и Adidas) и гонкой вооружений во время Холодной войны? И то и другое описывается концептами теории игр, на основе которых можно делать предсказания о поведении участников каждой из ситуаций. И подобные применения теории игр можно встретить в различных науках.
Фактчек
- Написание функций для проверки позиций на выигрышную/проигрышную — идеальный вариант, так как так мы сможем использовать их повторно в последующих проверках.
- Если проверяем позицию на выигрышную за два хода, нужно получить хотя бы одну проигрышную позицию. В проверке ходов используется or.
- Если проверяем позицию на проигрышную, нужно, чтобы каждая из позиций после хода игрока была выигрышной. В проверке используем and.
- Нельзя забывать про дополнительные условия — какие позиции не должны рассматриваться, какими позиции не должны быть.
Проверь себя
Условие задачи:
- Играют два пингвина — Петр и Виссарион. Петр будет ходить первым.
- Перед ними лежит одна куча камней. На своем ходу игрок может добавить в кучу 8 камней или увеличить количество камней в куче в 3 раза. Например, если в куче находится 10 камней, игрок может увеличить это значение до 18 или до 30.
- Игра продолжается до тех пор, пока в куче не окажется 145 камней или больше. Выигрывает тот, кто сделает последний ход.
- В начальный момент в куче лежит Х камней (1 <= X <= 144).
Задание 1.
Сколько существует значений Х таких, что Петр выиграет первым же своим ходом?
- 96
- 8
- 45
- 15
Задание 2.
Выберите минимальное значение Х такое, что при игре из него Виссарион выиграет первым своим ходом вне зависимости от игры Петра.
- 17
- 41
- 40
- 48
Задание 3.
Выберите максимальное значение Х такое, что Петр сможет выиграть Виссариона при любой его игре на своем втором ходу, но не сможет выиграть первым своим ходом.
- Таких значений не существует
- 14
- 15
- 40
Ответ: 1. — 1; 2. — 2; 3. — 4.
В задание №19_20_21
Тема: Теория игр. Поиск выигрышной стратегии.
Проверяется умение анализировать алгоритм логической игры. Умение найти выигрышную стратегию игры. Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию.
-
Одна куча — варианты решений -
Две кучи — варианты решений -
Три кучи — варианты решений
Немного теории:
☆ Все позиции в простых играх делятся на выигрышные и проигрышные
- выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если не сделает ошибку; при этом говорят, что у него есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть
- если игрок начинает играть в проигрышной позиции, он обязательно проиграет, если ошибку не сделает его соперник; в этом случае говорят, что у него нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника
- выигрышные и проигрышные позиции можно охарактеризовать так:
- позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная;
- позиция, из которой хотя бы один из возможных ходов ведет в проигрышную позицию — выигрышная, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию.
Одна куча:
Задание 19
Два игрока, Петя и Вася, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
- Добавить в кучу один камень или
- Добавить в кучу три камня или
- Увеличить количество камней в куче в четыре раза.
Например, имея кучу из 20 камней, за одни ход можно получить кучу из 21, 23 или 80 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 78. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 78 или больше камней. В начальный момент в куче было S камней: 1 ≤ S ≤ 77.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретится при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Известно, что Вася выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Решение:
Ответ: 5
Задание 20
Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Теперь попробуем определить значение S, при которых у Пети будет выигрышная стратегия, причём Петя не сможет выиграть первым ходом, но сможет выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.
Ответ: 16 18
Задание 21
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
- У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ: 15
Задание 19 (самостоятельно)
Два игрока, Петя и Вася, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
- Добавить в кучу один камень или
- Добавить в кучу два камня или
- Увеличить количество камней в куче в четыре раза.
Например, имея кучу из 20 камней, за одни ход можно получить кучу из 21, 22 или 79 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 85. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 85 или больше камней. В начальный момент в куче было S камней: 1 ≤ S ≤ 84.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретится при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Задание 20 (самостоятельно)
Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21 (самостоятельно)
Для игры, описанной в задании 19, найдите максимальное значение S, при котором одновременно выполняются два условия:
- У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Задание 19_20_22(DEMO) пишем программу Phyton
P-01 (демо-2022). Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит
куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Задание 19.
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21
Найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
n = 29 def gameResult(s): if s>=n:return 0 nYes = [gameResult(s+1), gameResult(s*2)] nNo = [i for i in nYes if i<=0] if nNo:res = -max(nNo) + 1 else:res = -max(nYes) return res # основная программа results = [(s,gameResult(s)) for s in range(1,n)] print( '19:', [s for s, r in results if r == -1] ) print( '20:', [s for s, r in results if r == 2] ) print( '21:', [s for s, r in results if r == -2] )
Задание 19_20_22 (Поляков) пишем программу Phyton
Две кучи — варианты решений
Задание 19 (разбираем задание)
Два игрока, Петя и Вася, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
- Добавить в одну из куч (по своему выбору) один камень или
- Добавить в одну из куч (по своему выбору) удвоенное число камне из другой кучи.
Например, пусть в одной куче 8 камней, а в другой куче 5 камней. Тогда за один ход можем получить четыре позиции: (9, 5); (18, 5); (8, 6); (8, 21).
Для того что бы играть, у игроков есть неограниченное количество камне.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было 9 камней, во второй S камней: 1 ≤ S ≤ 67.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретится при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Известно, что Вася выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Можно решить с помощью рассуждений:
- Если S = 67, то добавив в любую кучу один камень (67+1+9=77), или добавить удвоенную соседнюю кучу в любую из куч (9+(67+2*9)=94 или ((9+2*67)+67=210), Петя становится победителем.
- Если S = 66, добавив удвоенную соседнюю кучу в любую из куч (9+(66+2*9)=93 или ((9+2*66)+66=207), Петя становится победителем.
- Если S = 65, добавив удвоенную соседнюю кучу в любую из куч (9+(65+2*9)=92 или ((9+2*65)+65=204), Петя становится победителем.
- Обратим внимание, если удваиваем 9 камней и добавляем во вторую кучу, уменьшение ровно на 1, поэтому ускорим процесс 92-77=15, 65 -15 =50, идем дальше
- Если S = 50, добавив удвоенную соседнюю кучу в любую из куч (9+(50+2*9)=77 или ((9+2*50)+50=159), Петя становится победителем.
- У нас остается только один вариант, ускорим процес, усли удваиваем вторую кучу, уменьшение ровно на три, поэтому ускорим процесс 159-77=82, 82/3=27,333, 50-27=23
- Если S = 23, добавив удвоенную соседнюю кучу в эту из куч ((9+2*23)+23=78), Петя становится победителем. СТОП!!!
Получили – S>=23 – это ВЫИГРЫШНАЯ ПОЗИЦИЯ,
S<23 будет ПРОИГРЫШНОЙ ПОЗИЦИЕЙ ДЛЯ ЛЮБОГО ИГРОКА.
Известно, что Вася выиграл своим первым ходом, после НЕУДАЧНОГО первого хода Пети.
Неудачный ход – это значит Петя увеличил количество камне увеличив одну из куч удвоенным количеством соседней кучи. Получаем S+2*9 = 23 => S=5
Можно проверить программой:
# 19----------------------------------- def f(x, y, p): if x + y >=77 and p == 3: return True else: if x + y < 77 and p == 3:return False return f(x+1, y, p+1) or f(x, y+1, p+1) or f(x+2*y, y, p+1) or f(x, y+2*x, p+1) # начинаем перебор для 19 задания print('19 ответ -', end=' ') for i in range(1,50+1): if f(9, i, 1): print(i) break
Ответ: 5
Задание 20 (разбираем задание)
Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Ответ: 7 22
Задание 21 (разбираем задание)
Найдите значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ: 21
Три кучи — варианты решений
Задание 19_20_21 (разбираем задание)
(№ 4725) (И. Осипов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат три кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) три камня или увеличить количество камней в куче в два раза. Например, пусть в первой куче 10 камней, во второй 7, а в третьей 4 камня; такую позицию в игре будем обозначать (10, 7, 4). Тогда за один ход можно получить любую из шести позиций: (13, 7, 4), (20, 7, 4), (10, 10, 4), (10, 14, 4), (10, 7, 7), (10, 7, 8). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 71. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что в кучах всего будет 71 или больше камней. В начальный момент в первой куче было семь камней, во второй куче пять камней, в третьей куче – S камней; 1 ≤ S ≤ 58.
Ответьте на следующие вопросы:
Вопрос 1.При некотором значении S Ваня одержал победу свои первым ходом после неудачного хода Пети. Укажите минимальное значение S, при котором это возможно.
Вопрос 2. Найдите минимальное и максимальное значения S, при которых Петя выигрывает вторым ходом при любом ходе Вани.
Вопрос 3. Найдите значение S, при котором одновременно выполняются два условия: а) у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; б) у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
# --19---------------- def f(x,y,z,p): if x + y + z >=71 and p == 3:return True else: if x + y + z < 71 and p == 3:return False return (f(x+3, y, z, p+1) or f(x*2, y, z, p+1) or f(x, y+3, z, p+1) or f(x, y*2, z, p+1) or f(x, y, z+3, p+1) or f(x, y, z*2, p+1)) # ------------------------ print('19 ответ:', end=' ') for i in range(1,58+1): if f(7, 5, i, 1): print(i) break
Ответ: 15
# --20---------------- def f(x,y,z,p): if x + y + z >=71 and p == 4:return True else: if x + y + z < 71 and p == 4:return False else: if x + y + z>=71:return False if p % 2 == 1: return (f(x+3, y, z, p+1) or f(x*2, y, z, p+1) or f(x, y+3, z, p+1) or f(x, y*2, z, p+1) or f(x, y, z+3, p+1) or f(x, y, z*2, p+1)) else: return (f(x+3, y, z, p+1) and f(x*2, y, z, p+1) and f(x, y+3, z, p+1) and f(x, y*2, z, p+1) and f(x, y, z+3, p+1) and f(x, y, z*2, p+1)) # ------------------------ print('20 ответ:', end=' ') for i in range(1,58+1): if f(7, 5, i, 1): print(i, end=' ')
Ответ: 14 27
# --21---------------- print() def f(x,y,z,p): if x + y + z >=71 and (p == 3 or p == 5):return True else: if x + y + z < 71 and p == 5:return False else: if x + y + z>=71:return False if p % 2 == 0: return (f(x+3, y, z, p+1) or f(x*2, y, z, p+1) or f(x, y+3, z, p+1) or f(x, y*2, z, p+1) or f(x, y, z+3, p+1) or f(x, y, z*2, p+1)) else: return (f(x+3, y, z, p+1) and f(x*2, y, z, p+1) and f(x, y+3, z, p+1) and f(x, y*2, z, p+1) and f(x, y, z+3, p+1) and f(x, y, z*2, p+1)) # ------------------------ print('21 ответ:', end=' ') for i in range(1,58+1): if f(7, 5, i, 1): print(i, end=' ') break
Ответ: 24