Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 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 года Крылова, Чуркиной по схеме из этой статьи. Ответы сошлись. Могу вам прислать решения, если вы напишите в группе в вк.
На уроке рассмотрен разбор 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 здесь
Муниципальное
АВТОНОМНОЕ общеобразовательное учреждение муниципального образования город
Краснодар Лицей № 90
имени михаила лермонтова
пРОЕКТ
«ТЕОРИЯ ИГР В ЗАДАНИЯХ
ЕГЭ»
Проект
подготовил: Кондратьев Данила 11 «В»
Руководитель
проекта: Савина Р.Р.
2022-2023 учебный
год
Оглавление
ВВЕДЕНИЕ
Глава
1. История, смысл и типы теории игр
Смысл теории игр
Типы
теории игр
Глава2. Разбор теории игр в ЕГЭ (Задания
19-21)
Заключение
Список литературы
ВВЕДЕНИЕ
Теория
игр — это
раздел математической экономики, изучающий решение конфликтов между игроками и
оптимальность их стратегий. Конфликт может относиться к разным областям
человеческого интереса: чаще всего это экономика, социология, политология, реже
биология, кибернетика и даже военное дело. Конфликтом является любая ситуация,
в которой затронуты интересу двух и более участников, традиционно называемых
игроками. Для каждого игрока существует определенный набор стратегий, которые
он может применить. Пересекаясь, стратегии нескольких игроков создают
определенную ситуацию, в которой каждый игрок получает определенный результат,
называемый выигрышем, положительным или отрицательным. При выборе стратегии
важно учитывать не только получение максимального профита для себя, но также
возможные шаги противника, и их влияние на ситуацию в целом.
Данный подход логичен при
исследовании экономических систем с огромным числом участников, когда
отдельному субъекту невозможно предвидеть решения всех других субъектов. Такая
децентрализованная экономическая система может устойчиво функционировать, когда
рынок находится в состоянии совершенной конкуренции. В действительности
«совершенного рынка» не существует, и мы имеем только взаимодействия между
людьми, регулируемые некоторыми правилами. Теория игр предполагает, что
субъекты при принятии своих решений должны просчитывать возможные решения
других субъектов, поскольку результат зависит от решений всех участников.
Поэтому в теории игр предполагается, что все субъекты не только рациональны, но
и разумны, в том смысле, что они способны находить не только свои оптимальные
решения, но также и оптимальные решения других участников.
Глава 1. История, смысл и типы теории
игр
Основы
теории игр зародились еще в 18 веке, с началом эпохи просвещения и развитием
экономической теории. Первое математически строгое
определение игры было дано венгерским математиком Джоном фон Нейманом, которого
по праву считают одним из величайших математиков 20-го века. Удивительно, но в
своей работе, опубликованной в далеком 1928 году, он сформулировал игру n лиц с
нулевой суммой точно также, как она формулируется сегодня. Впервые математические аспекты и
приложения теории были изложены в классической книге 1944 года Джона фон
Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение». Первые
концепции теории игр анализировали антагонистические игры, когда есть
проигравшие и выигравшие за их счет игроки. Несмотря на то, что теория игр
рассматривала экономические модели, вплоть до 50-х годов 20 века она была всего
лишь математической теорией. После, в результате резкого скачка экономики США
после второй мировой войны, и, как следствие, большего финансирования науки,
начинаются попытки практического применения теории игр в экономике, биологии,
кибернетике, технике, антропологии. Во время Второй мировой войны и сразу после
нее теорией игр серьезно заинтересовались военные, которые увидели в ней мощный
аппарат для исследования стратегических решений. В начале 50-х Джон Нэш разрабатывает методы анализа, в которых все
участники или выигрывают, или терпят поражение. Эти ситуации получили
названия «равновесие по Нэшу». По его теории, стороны должны использовать
оптимальную стратегию, что приводит к созданию устойчивого равновесия. Игрокам
выгодно сохранять это равновесие, так как любое изменение ухудшит их положение.
Эти работы Нэша сделали серьезный вклад в развитие теории игр, были
пересмотрены математические инструменты экономического моделирования. Джон Нэш
показывает, что классический подход к конкуренции А. Смита, когда каждый сам за
себя, не оптимален. Более оптимальны стратегии, когда каждый старается сделать
лучше для себя, делая лучше для других. За последние 20 — 30 лет значение
теории игр и интерес значительно растет, некоторые направления современной
экономической теории невозможно изложить без применения теории игр.
Смысл теории игр
Как мне
кажется, смысл теории игр проще всего пояснить на «Дилемме заключенного»,
классическая формулировка которой звучит так: Двое
преступников, А и Б, попались примерно в одно и то же время на сходных
преступлениях. Есть основания полагать, что они действовали по сговору, и
полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если
один свидетельствует против другого, а тот хранит молчание, то первый
освобождается за помощь следствию, а второй получает максимальный срок лишения
свободы (10 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и
они приговариваются к 6 месяцам. Если оба свидетельствуют против друг друга,
они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать
или свидетельствовать против другого. Однако ни один из них не знает точно, что
сделает другой. Что произойдёт?
Представлю
игру в виде таблицы
|
Преступник Б |
Преступник Б |
|
|
Преступник А |
Полгода каждому |
10 Лет преступнику А |
|
Преступник А |
10 Лет преступнику Б |
2 года каждому |
А
теперь представим развитие ситуации, поставив себя на место заключенного А.
Если мой подельник молчит, лучше его сдать и выйти на свободу. Если он говорит,
то так же лучше все рассказать, и получить всего два года, вместо десяти. Таким
образом, если каждый игрок выбирает, что лучше для него, оба сдадут друг друга,
и получат два года, что не является идеальной ситуацией для обоих. Если бы
каждый думал об общем благе, они бы получили всего по полгода.
Типы
теории игр
1.
Кооперативная или некооперативная
игра
Кооперативной игрой является конфликт, в котором
игроки могут общаться между собой и объединяться в группы для достижения
наилучшего результата. Примером кооперативной игры можно считать карточную игру
Бридж, где очки каждого игрока считаются индивидуально, но выигрывает пара,
набравшая наибольшую сумму. Из двух типов игр, некооперативные описывают
ситуации в мельчайших деталях и выдают более точные результаты. Кооперативные
рассматривают процесс игры в целом. Несмотря на то, что эти два вида
противоположны друг другу, вполне возможно объединение стратегий, которое может
принести больше пользы, чем следование какой-либо одной.
2.
С нулевой суммой и с
ненулевой суммой
Игрой с нулевой суммой называют игру, в которой
выигрыш одного игрока равняется проигрышу другого. Например, банальный спор:
если вы выиграли сумму N, то кто-то эту же сумму N проиграл. В игре же с
ненулевой суммой может изменяться общая цена игры, таким образом принося выгоду
одному игроку, не отнимаю ее цену у другого. В качестве примера здесь отлично
подойдут шахматы: превращая пешку в ферзя игрок А увеличивает общую сумму своих
фигур, при этом не отнимая ничего у игрока Б. В играх с ненулевой суммой
проигрыш одного из игроков не является обязательным условием, хотя такой исход
и не исключается.
3.
Параллельные и
последовательные
Параллельной является игра, в которой игроки
делают ходы одновременно, либо ход одного игрока неизвестен другому, пока не
завершится общий цикл. В последовательной игре каждый игрок владеет информацией
о предыдущем ходе своего оппонента до того, как сделать свой выбор. И совсем не
обязательно информации быть полной, что подводит на с следующему типу.
4.
С полной или неполной
информацией
Эти типы являются подвидом последовательных игр,
в которых имеется полная или неполная информация.
Глава2.
Разбор теории игр в ЕГЭ (Задания 19-21)
Игра с одной кучей камней
Два игрока, Петя и Ваня, играют в следующую
игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход
делает Петя. За один ход игрок может добавить в кучу один камень, или добавить
в кучу два камня, или увеличить количество камней в куче в два раза.
Например, имея кучу из 10 камней, за
один ход можно получить кучу из 11, 12 или 20 камней. У каждого игрока, чтобы
делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда
количество камней в куче превышает 33. Победителем считается игрок, сделавший
последний ход, то есть первым получивший кучу, в которой будет 34 или больше
камней. В начальный момент в куче было S камней, 1 ≤ S ≤
33.
Говорят, что игрок
имеет выигрышную стратегию, если он может выиграть при любых ходах
противника. Описать стратегию игрока — значит, описать, какой ход он должен
сделать в любой ситуации, которая ему может встретиться при различной игре
противника.
19)Известно, что Ваня выиграл своим
первым ходом после неудачного первого хода Пети. Укажите минимальное значение S,
когда такая ситуация возможна.
20) Найдите три таких
значения S, при которых у Пети есть выигрышная стратегия, причём
одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым
ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе
в порядке возрастания без разделительных знаков.
21) Найдите минимальное
значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия,
позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая
позволит ему гарантированно выиграть первым ходом.
Решение: 19) Так как нам нужно
указать минимальное значение S,
мы будем использовать только умножить на 2, потому что оно прибавляет больше
всего камней. Возьмем минимальное число S при победе — 34, разделим его на 2, получим 34÷2=17, значит Петя должен
сделать 17 или больше, так как меньше не подойдет. 17÷2=8,5 округляем в большую
сторону и получаем 9, тогда минимальное число S будет 9. Проверим, 9×2=18 ход Пети, 18×2=36 ход Вани, подходит.
Ответ: 9
20) Так как Петя не может выиграть
своим первым ходом, значит нам не подходят числа от 17 (узнали в 19 задании) до
33. Тогда нужно сделать, чтобы после хода Пети было число 16, так Ваня не
сможет победит, и он сделает для Пети число от 17 до 32, с помощью чего Петя
сможет победить во втором ходе умножив на 2. 16 можно получить 3 способами. 1.
15 + 1 =16
2.
14 + 2 =16
3.
8 × 2 = 16
Значит
эти три числа 15, 14, 8.
Ответ: 81415
21)Так как у Вани нет стратегии,
которая позволит ему выиграть первым ходом гарантированно, мы не берем числа от
15 до 33, потому не зависимо от хода Пети, Ваня может выиграть первым ходом
гарантированно. Мы должны взять S
такое, чтобы после хода Пети Ваня в любом случае могли из него сделать число 16
(Потому что при числе 16 Петя не может победить, а Ваня гарантированно
выиграет) или победить. На первый критерий подходят числа 14(+1 +1),13(+2 +1 или
+1 +2),7(+1 ×2),6(+2 ×2),4(×2 ×2), дальше проверим все числа.
14 не подходит, потому что Петя может
прибавить 2, тогда Ваня проиграет, потому что после хода Вани получится число
17 или больше.
13 подходит, так как если Петя
прибавит 1 или 2, Ваня сможет сделать из полученного числа 16, а если Петя
умножит на 2, тогда Ваня выиграет первым ходом.
7 не подходит, потому что Петя может
прибавить два и получится 9, тогда Ване и Пете придется придется прибавлять по
1 или 2, тогда Ваня не сможет выиграть 2 ходом.
6 не подходит, так как Петя может
прибавить 1 и получить 7, если Ваня умножит на 2 он проиграет, а если прибавит
один или два, тогда не сможет выиграть вторым ходом.
4 не подходит, потому что Ваня может
прибавить 2 или 1, тогда Ваня не сможет выиграть 2 ходом.
Остается только одно верное число 13.
Ответ: 13
Игра с двумя кучами
камней
Два игрока, Петя и Ваня, играют в
следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди,
первый ход делает Петя. За один ход игрок может убрать из одной из куч
один камень или уменьшить количество камней в куче в два
раза (если количество камней в куче нечётно, остаётся на 1 камень больше,
чем убирается). Например, пусть в одной куче 6, а в другой 9 камней; такую
позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно
получить любую из четырёх позиций: (5, 9), (3, 9), (6, 8), (6, 5).
Игра завершается в тот момент, когда
суммарное количество камней в кучах становится не более 20. Победителем
считается игрок, сделавший последний ход, то есть первым получивший позицию, в
которой в кучах будет 20 или меньше камней.
В начальный момент в первой куче было
10 камней, во второй куче — S камней, S > 10.
Будем говорить, что игрок имеет
выигрышную стратегию, если он может выиграть при любых ходах противника.
Описать стратегию игрока — значит, описать, какой ход он должен сделать в
любой ситуации, которая ему может встретиться при различной игре противника. В
описание выигрышной стратегии не следует включать ходы играющего по ней игрока,
которые не являются для него безусловно выигрышными, т.е не гарантирующие
выигрыш независимо от игры противника.
19) Известно, что Ваня выиграл своим
первым ходом после неудачного первого хода Пети. Укажите максимальное
значение S, когда такая ситуация возможна.
20) Найдите пять таких значений S,
при которых у Пети есть выигрышная стратегия, причём одновременно выполняются
два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым
ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе
в порядке возрастания без разделительных знаков.
21) Найдите максимальное
значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия,
позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая
позволит ему гарантированно выиграть первым ходом.
Решение:19)Так
как нам нужно найти максимальное значение S,
я буду уменьшать количество камней в куче в два раза, потому так будет больше
камней, в отличии от способа, где мы забираем один камень. Всего было два хода
(Петин и Ванин), тогда я максимально возможное s,
которое должно получиться в итоге, умножу на 4. Должно получиться 10, так
получится минимальная сумма двадцать для победы. Тогда максимальное значение s,
10×4=40.
Ответ:40
20)Рассмотрим
разные случаи.
1.
Петя забирает один камень из второй кучки. Ваня может забрать один камень из
любой кучки или уменьши количество камней в два раза в любой кучке. Если Ваня
заберет камень из второй кучи, тогда Пете надо будет уменьшить количество
камней в два раза во второй куче, потому что если бы Пете оставалось забрать
один камень из любой кучи для победы, тогда Ваня мог не забирать камень у
уменьшить количество какой то кучки в 2 раза и победить, что неверно. Тогда в
первой кучке 10 камней, во второй должно быть тоже 10, чтобы Ваня не победил,
10 мы получим, когда 20 поделим на 2. Значит во второй кучке изначально было 20
+1(забрал Ваня) +1 (забрал Петя) = 22 камня. Если бы Ваня уменьшил количество в
какой-то кучке в два раза или забрал камень из первой кучи, тогда Петя все
равно смог бы победить вторым ходом.
2.Петя
уменьшит количество камней в два раз во второй кучке. Тогда Ваня так же как и
первом случаи может забрать один камень из любой кучи или уменьшить количество
камней в 2 раза в любой куче. Из первого случая мы знаем, что перед ходом Вани
в первой куче 10 камней, а во второй 21. 21 можно получить если мы 42 сократим
на 2 и 43 сократим на 2. Значит это два значения S.
3.
Петя забрал один камень из первой кучи. Тогда в первой куче осталось 9 камней,
тогда вконце во второй должно получиться 11, меньше не может, потому что тогда
Ваня победит. Допустим, что Петя вторым ходом сократил количество камней в 2
раза, тогда после хода Вани в первой куче было 9 камней, а во второй 21 или 22.
В данном случае Ваня точно забрал один камень, так как если бы он уменьшил их
количество в два раза, тогда Петя мог победить вторым ходом не гарантированно,
потому что меня мог не уменьшить число 42 или 44, а забрать у них один камень.
Значит, если он забрал у второй кучи один камень, тогда там было 22 или 23
камня. 22 мы уже доказали, проверим 23. Ваня мог сократить количество в первой
кучке или во второй в 2 раза, тогда бы Петя все равно бы победил. Если бы Ваня
забрал из первой кучки камень, Ваня так же смог победить гарантированно.
4.Петя
уменьшил количество камней в первой кучке. Значит в первой кучке осталось 5
камней, тогда в конце во второй должно получиться 15, меньше не может, потому
что тогда Ваня победит. Допустим, что на втором ходу Петя сократил количество
камней в два раза, тогда после хода Вани в первой куче было 5 камней, а во
второй 30. S не может быть 60 или
59, потому что тогда Петя не победит, получается Ваня забрал из второй кучи
один камень, и изначально там лежал 31 камень. S=31
это подходит, так как если бы Ваня захотел уменьшить количество камней в одной
из двух кучек или забрать камень из первой кучки, Петя все равно бы победил.
Ответ:2223314142
21)Так как Ваня не обязательно
выиграет первым ходом, тогда S
21 не подходит, потому что Ваня всегда может выиграть первым ходом. S
будет меньше 31, так как тогда Ваня не всегда может выиграть вторым ходом. Из
оставшихся чисел подходит 24, так как В
любой из перечисленных позиций Ваня может выиграть, уменьшив вдвое количество
камней в большей куче. Числа больше не подойдут, так Петя может дотянуть и не
дать Ване выиграть вторым ходом гарантированно.
Заключение
В ходе данного проекта, мы узнали,
что такое теория игр. Мы изучили историю появления теории игр и ее развитие, мы
узнали, зачем нужна теория игр. Мы рассмотрели виды теории игр. Так же в ходе
данного проекта я разобрал задачи теории игр из ЕГЭ. Это поможет мне и другим
старшеклассникам понять теорию игр и самостоятельно решить три номера по этой
теме на ЕГЭ по информатике.
Список
литературы
1)
https://habr.com/ru/post/163681/
2)
https://kpfu.ru/portal/docs/F1858685921/lekcii24.pdf
3)
https://inf-ege.sdamgia.ru/
Public user contributions licensed under
cc-wiki license with attribution required
Канал видеоролика: Алекс ЕГЭ Информатика
Смотреть видео:
#информатика #егэинформатика #икт #экзамены #егэ_2020 #мгту #школьникам #помощь_студентам #подготовкакэкзаменам
Свежая информация для ЕГЭ и ОГЭ по Информатике (листай):
С этим видео ученики смотрят следующие ролики:
Теория игр. ЕГЭ по информатике 2023. 19 20 21 номера. Новый метод. Часть 2
Алекс ЕГЭ Информатика
Теория игр. ЕГЭ по информатике 2023. 19 20 21 номера. Новый метод. Часть 4
Алекс ЕГЭ Информатика
ЕГЭ по информатике 2023 — Задание 19-21 (Теория игр на Python)
Code Enjoy
Стрим №10. ТЕОРИЯ ИГР!!! Задания 19, 20, 21. ЕГЭ по информатике 2023
ЕГЭ по информатике
Облегчи жизнь другим ученикам — поделись! (плюс тебе в карму):
06.02.2023
- Комментарии
RSS
Написать комментарий
Нет комментариев. Ваш будет первым!
Ваше имя:
Загрузка…
30 декабря 2020
В закладки
Обсудить
Жалоба
Теория игр. Поиск выигрышной стратегии
В данном материале представлен разбор задачи ЕГЭ по информатике по теме «Теория игр. Поиск выигрышной стратегии». Данная задача входила в материалы экзамена под № 26. Представлены рассуждения и оформления решений в словесной форме и в виде дерева игры. В ЕГЭ-2021 она разбита на три отдельных задания (№ 19, 20, 21).
teoriya-igr.pdf
Автор: Лицкевич Елена Францевна.
ЕГЭ информатика 19-21 задание разбор, теория, как решать.
Теория игр, выигрышная стратегия, 19.(Б) — 1 балл, 20.(П) — 1 балл, 21.(В) — 1 балл
Е19-21.31 когда количество камней в куче становится не менее 129
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается …
Читать далее
Е19-21.31 Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 211.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока …
Читать далее
Е19-21.30 когда количество камней в куче становится не менее 29
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. …
Читать далее
Е19-21.29 когда суммарное количество камней в кучах становится не менее 44
когда суммарное количество камней в кучах становится не менее 44 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в …
Читать далее
Е19-21.28 Игра завершается в тот момент, когда количество камней в куче становится не менее 84.
Игра завершается в тот момент, когда количество камней в куче становится не менее 84. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в …
Читать далее
Е19-21.27 добавить в кучу один камень, два камня, увеличить количество камней
добавить в кучу один камень, два камня, увеличить количество камней. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) добавить в кучу два камня; г) увеличить количество камней в куче …
Читать далее
Е19-21.26 добавить в кучу один камень, два камня, три камня; увеличить количество камней
добавить в кучу один камень, два камня, три камня; увеличить количество камней в куче в два раза. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в кучу один камень; б) добавить в кучу два …
Читать далее
Е19-21.25 добавить в кучу два камня, добавить в кучу три камня или увеличить
добавить в кучу два камня, добавить в кучу три камня или увеличить. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня, добавить в кучу три камня или увеличить количество камней в куче …
Читать далее
Е19-21.24 добавить в кучу три камня или увеличить количество камней в куче в два раза
добавить в кучу три камня или увеличить количество камней в куче в два раза. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня или увеличить количество камней в куче в два раза. …
Читать далее
Е19-21.23 когда количество камней в куче становится не менее 25
Игра завершается в тот момент, когда количество камней в куче становится не менее 25. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. …
Читать далее