Теория игр информатика егэ 2022

Public user contributions licensed under
cc-wiki license with attribution required

Продолжаем наш видеокурс по подготовке к ЕГЭ по информатике 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, который будет олицетворять позицию игры (ход).

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 задания и подобрали к ним «противоядие». До новых встреч!

Муниципальное
АВТОНОМНОЕ общеобразовательное учреждение муниципального образования город
Краснодар Лицей № 90

имени михаила лермонтова

пРОЕКТ

«ТЕОРИЯ ИГР В ЗАДАНИЯХ
ЕГЭ»

Проект
подготовил: Кондратьев Данила 11 «В»

Руководитель
проекта: Савина Р.Р.

2022-2023 учебный
год

Оглавление

ВВЕДЕНИЕ

Глава
1. История, смысл и типы теории игр

Смысл теории игр

Типы
теории игр

Глава2. Разбор теории игр в ЕГЭ (Задания
19-21)

Заключение

Список литературы

ВВЕДЕНИЕ

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

Данный подход логичен при
исследовании экономических систем с огромным числом участников, когда
отдельному субъекту невозможно предвидеть решения всех других субъектов. Такая
децентрализованная экономическая система может устойчиво функционировать, когда
рынок находится в состоянии совершенной конкуренции. В действительности
«совершенного рынка» не существует, и мы имеем только взаимодействия между
людьми, регулируемые некоторыми правилами. Теория игр предполагает, что
субъекты при принятии своих решений должны просчитывать возможные решения
других субъектов, поскольку результат зависит от решений всех участников.
Поэтому в теории игр предполагается, что все субъекты не только рациональны, но
и разумны, в том смысле, что они способны находить не только свои оптимальные
решения, но также и оптимальные решения других участников.

Глава 1. История, смысл и типы теории
игр

Основы
теории игр зародились еще в 18 веке, с началом эпохи просвещения и развитием
экономической теории. Первое математически строгое
определение игры было дано венгерским математиком Джоном фон Нейманом, которого
по праву считают одним из величайших математиков 20-го века. Удивительно, но в
своей работе, опубликованной в далеком 1928 году, он сформулировал игру n лиц с
нулевой суммой точно также, как она формулируется сегодня. Впервые математические аспекты и
приложения теории были изложены в классической книге 1944 года Джона фон
Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение». Первые
концепции теории игр анализировали антагонистические игры, когда есть
проигравшие и выигравшие за их счет игроки. Несмотря на то, что теория игр
рассматривала экономические модели, вплоть до 50-х годов 20 века она была всего
лишь математической теорией. После, в результате резкого скачка экономики США
после второй мировой войны, и, как следствие, большего финансирования науки,
начинаются попытки практического применения теории игр в экономике, биологии,
кибернетике, технике, антропологии. Во время Второй мировой войны и сразу после
нее теорией игр серьезно заинтересовались военные, которые увидели в ней мощный
аппарат для исследования стратегических решений. В начале 50-х Джон Нэш разрабатывает методы анализа, в которых все
участники или выигрывают, или терпят поражение. Эти ситуации получили
названия «равновесие по Нэшу». По его теории, стороны должны использовать
оптимальную стратегию, что приводит к созданию устойчивого равновесия. Игрокам
выгодно сохранять это равновесие, так как любое изменение ухудшит их положение.
Эти работы Нэша сделали серьезный вклад в развитие теории игр, были
пересмотрены математические инструменты экономического моделирования. Джон Нэш
показывает, что классический подход к конкуренции А. Смита, когда каждый сам за
себя, не оптимален. Более оптимальны стратегии, когда каждый старается сделать
лучше для себя, делая лучше для других. За последние 20 — 30 лет значение
теории игр и интерес значительно растет, некоторые направления современной
экономической теории невозможно изложить без применения теории игр.

Смысл теории игр

Как мне
кажется, смысл теории игр проще всего пояснить на «Дилемме заключенного»,
классическая формулировка которой звучит так: Двое
преступников, А и Б, попались примерно в одно и то же время на сходных
преступлениях. Есть основания полагать, что они действовали по сговору, и
полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если
один свидетельствует против другого, а тот хранит молчание, то первый
освобождается за помощь следствию, а второй получает максимальный срок лишения
свободы (10 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и
они приговариваются к 6 месяцам. Если оба свидетельствуют против друг друга,
они получают минимальный срок (по 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/

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

В задачах 19-21 ЕГЭ по информатике требуется проанализировать некую простую игру. Однако хотя игра и проста, её анализ может оказаться достаточно хитрым делом. Поэтому приходит мысль: а нельзя ли, чтобы этот анализ выполнил компьютер? (Спойлер: Можно!)

Немного теории.

Основную идею, лежащую в основе теории игр, подобных описанным в задачах ЕГЭ, можно выразить в двух словах: игроки умные. Это означает, что если у кого-то из игроков в текущей позиции есть возможность сделать выигрышный ход, то он этот ход сделает.

Таким образом, если в текущей позиции у игрока есть хотя бы один ход, ведущий к выигрышу, то это — выигрышная позиция для данного игрока. 

Если же в ответ на любой ход текущего игрока его противник выигрывает, то для текущего игрока такая ситуация — проигрышная.

Теперь более-менее понятно, как должна выглядеть программа, анализирующая ход игры. Прежде всего она должна проверить, не выиграл ли уже кто-то из игроков. Если это так — то дальнейший анализ позиции не требуется. 

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

Если же неверно ни первое, ни второе — то ситуация неопределенная.(Вообще-то для игр из задач ЕГЭ всегда можно сказать, кто из игроков выиграет, такая неопределенность возникает только из-за ограничения на число ходов.)

Данную процедуру следует рекурсивно применять к позициям, возникающим по ходу игры.

А теперь — практика.

Решим программно задачи 19-21 из 8 варианта с сайта Полякова. Условие выглядит следующим образом:

(№ 3084) (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход
делает Петя. За один ход игрок может
  а) добавить в кучу один камень;
  б) увеличить количество камней в куче в два раза;
  в) увеличить количество камней в куче в три раза.
Игра
завершается в тот момент, когда количество камней в куче становится не
менее 43. Если при этом в куче оказалось не более 72 камней, то
победителем считается игрок, сделавший последний ход. В противном случае
победителем становится его противник. В начальный момент в куче было S
камней, 1≤S≤42.
Ответьте на следующие вопросы:
  Вопрос 1. Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
  Вопрос 2. Сколько существует значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите минимальное и максимальное значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.

Функция имеет три параметра: number (номер хода), limit (ограничение на количество ходов) и s (количество камней в куче). При первом обращении следует задавать значение number,  равное 1 (т.е. ходы мы нумеруем с единицы).

Переменная player принимает значение 1 для нечетных номеров ходов (т.е. ходы 1, 3 и т.д. совершает первый игрок) и значение 2 — для четных номеров. Переменная rival, наоборот, равна 2 для нечетных номеров ходов и 1 — для четных. Таким образом, player — это номер игрока, который делает текущий ход, а rival — номер его противника.

Прежде всего функция проверяет, не завершилась ли игра. Если число камней S не менее 43 и не более 72, то это означает, что текущий игрок проиграл: перед этим его противник сделал победный ход. Функция завершается, вернув значение rival. Если же число камней более 72, то соперник текущего игрока только что сделал проигрышный для себя ход, и выиграл текущий игрок. Программа возвращает значение player. 

Далее проверяется ограничение на число ходов. Если это ограничение превышено (number>limit), то дальнейшие ходы не выполняются и программа возвращает значение 0 (т.е. победитель не определён).

Далее осуществляются рекурсивные вызовы функции  hod с параметром number+1 (т.е. номер хода увеличен на единицу), с тем же самым значением limit и числом камней в куче 3S, 2S и S+1 (согласно условиям задачи).

Рекомендую сначала проверять значения, как можно сильнее отличающиеся от исходного (т.е. 3S и 2S) и потом S+1. Это позволяет уменьшить число вершин «дерева игры», которые анализирует программа. С этой же целью программа, обнаружив выигрышный для текущего игрока ход (т.е. результат вызова функции равен player), немедленно возвращает значение player и не выполняет дальнейших проверок ходов.

Если все три результата ходов равны rival, то в данной позиции все ходы текущего игрока приводят к его проигрышу, и программа возвращает значение rival. 

Если же для текущего игрока нет ни одного выигрышного хода, но у него есть ходы, не приводящие к его проигрышу, то ситуация неопределённая, и программа возвращает 0.

Теперь проведем анализ данной игры и получим ответы на заданные в задаче вопросы.

Первый вопрос: каково минимальное значение S, при котором второй игрок выигрывает своим первым ходом? Для ответа на него достаточно вызвать функцию для всех значений S таких, что 1<=S<=42, с ограничением на количество ходов, равным 2 (т.е. игроки делают по одному ходу). Если функция hod вернет значение, равное 2, то при данном начальном значении S второй игрок выигрывает в любом случае.

Второй вопрос: сколько имеется значений S, при которых первый игрок не может выиграть своим первым ходом, но гарантированно выигрывает вторым?

Для этого надо запустить программу два раза, первый раз с ограничением на число ходов 1, а второй раз — с ограничением 3. Если в первом случае программа вернет значение 0 (нет победителя), а второй — 1, то при данном S первый игрок не может гарантированно выиграть своим первым ходом, но непременно выигрывает вторым. Вместо ограничений 1 и 3 можно взять 2 и 4: дополнительный ход второго игрока (если он возможен) ничего не меняет.

Наконец, последний вопрос: при каких значениях S второй игрок не может гарантированно выиграть первым ходом, но обязательно выиграет вторым? Для этого надо опять запустить функцию дважды, с ограничением на число ходов 2 и 4. Если в первом случае функция вернет 0, а во втором — 2, то это искомое значение.   

Вот программа, которая выполняет данные проверки:

for s in range(1,43):
    h2 = hod(1,2,s)
    h4 = hod(1,4,s)
    rez = »
    if h2 == 2: rez = ‘*** 19 ***’
    if h2 == 0:
        if h4 == 1: rez = ‘*** 20 ***’
        if h4 == 2: rez = ‘*** 21 ***’
    print(s,h2, h4, rez)

Результат выполнения программы следующий (из него исключены строки, которые не дают ответов не поставленные вопросы):

7 0 1 *** 20 ***
12 0 2 *** 21 ***
13 0 1 *** 20 ***
14 2 2 *** 19 ***
39 0 2 *** 21 ***
40 0 1 *** 20 ***
41 2 2 *** 19 ***

Следовательно, ответы на вопросы задачи таковы:

Вопрос 1: такие значения — 14 и 41, минимальное — 14.

Вопрос 2: такие значения — 7, 13 и 40, всего их 3.

Вопрос 3: такие значения — 12 и 39. Минимальное — 12, а максимальное — 39.

А теперь решим задачи 19-21 из демонстрационного варианта ФИПИ 2022 г.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

19. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

20. Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.

21. Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.

Вопросы по сути те же, что и в задаче с сайта Полякова, однако правила игры другие. 

Перепишем функцию hod для данных правил:

Основная программа выглядит так же, как и в предыдущем случае. Единственное изменение — вместо range(1,43) в ней записано range(1,29).

Результат выполнения программы следующий (в нём опять-таки опущены несущественные строки):

Если Петя глуповат…

При составлении программы мы предполагали, что игроки — умные и ошибочных ходов не делают. Но на сайте «Решу ЕГЭ» очень часто встречаются задачи, где один из игроков дает маху. Вот пример задачи 19 (задача 27416):

Но как быть с тем, что наша функция предполагает безошибочную игру, а условие задачи подразумевает, что первый игрок сделал ошибочный ход? А очень просто: надо вызвать функцию четыре раза с позициями, которые могут получиться после первого хода Пети. В параметрах функции надо указать, что это — второй ход, и задать ограничение на количество ходов, равное двум. Если хотя бы в одном случае функция даст ответ, что выиграл второй игрок, то это и будет ответом на вопрос задачи.

Таким образом, основная программа выглядит так:

s1=7
for s2 in range(1,70):
    if hod(2,2,s1*2,s2)==2 or hod(2,2,s1,s2*2)==2 or hod(2,2,s1+1,s2)==2 or hod(2,2,s1,s2+1)==2:
        print(s2)
        break

Она дает правильный ответ: 18 камней.

Когда основная функция написана, не представляет сложности решить задачи 20 и 21. Вот их вопросы (правила игры, естественно, те же самые):

Основная программа опять-таки похожа на первый вариант, отличия незначительные:

s1=7
for s2 in range(1,70):
    h2 = hod(1,2,s1,s2)
    h4 = hod(1,4,s1,s2)
    rez = »
    if h2 == 0:
        if h4 == 1: rez = ‘*** 20 ***’
        if h4 == 2: rez = ‘*** 21 ***’
    print(s2,h2, h4, rez)

Результат работы программы (опять-таки опущены несущественные строки):

30 0 2 *** 21 ***
31 0 1 *** 20 ***
33 0 2 *** 21 ***
34 0 1 *** 20 ***

Таким образом, ответ на вопрос задачи 20 — это 31 и 34, а на вопрос задачи 21 — 30 (напомню, что там требуется минимальное значение из двух ответов: 30 и 33).

Итак, мы убедились, что задачи 19-21 ЕГЭ по информатике можно решить программно, и решение — не слишком сложное.

(c) Ю.Д.Красильников, 2021 г.