Методы решения задач разных типов по теме: “Теория игр”, включенных в ЕГЭ по информатике

Муниципальное автономное общеобразовательное учреждение

средняя общеобразовательная школа с. Чапланово

муниципального образования «Холмский городской округ»

Сахалинской области

 Сахалинская область, Холмский район, с. Чапланово, ул. Школьная,1

 тел. /факс. – 95-133;   E–mail:  khgo.maousoshcha@sakhalin.gov.ru

Тема исследовательской работы

«Методы решения задач разных типов по теме: “Теория игр”, включенных в ЕГЭ по информатике»

выполнила: Полякова Александра Владимировна

ученица 11 класса МАОУ СОШ с.Чапланово

Научный руководитель:

Алексеева Светлана Валерьевна

учитель математики МАОУ СОШ с.Чапланово

Холмск 2024

Оглавление

Введение        3

ГЛАВА I        4

Основные понятия и определения        4

ГЛАВА II        8

Задача 19.        8

Задача 20        10

Задача 21        13

Заключение        17

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

Введение

Решение задач на игровые стратегии является отличным инструментом для развития интеллекта. Умение логически рассуждать, искать оптимальные решения, просчитывать свои действия наперёд – это те навыки, которые необходимы каждому человеку. Эти задачи проверяют не знания, а умение анализировать алгоритм логической игры. Умение найти выигрышную стратегию. Не случайно задания по этой теме присутствуют в контрольно-измерительных материалах ЕГЭ по информатике с самого первого года его проведения.

Актуальность: Данная работа будет полезна всем ученикам, выбравшим информатику, как предмет для сдачи ЕГЭ, поскольку примеры и советы, описанные здесь, помогают освоить решение задач на тему: «Теория игр».

Объект исследования: Задачи на тему: «Теория игр» в ЕГЭ по информатике.

Предмет исследования: Способы решения задач на тему «Теория игр».

Цель проекта: Рассмотреть несколько способов решения задач на тему: «Теория игр» и найти наиболее подходящий для меня, чтобы воспользоваться им на ЕГЭ по информатике.

Задачи проекта: 

• Проанализировать задачи ЕГЭ по информатике по теме «Теория игр».
• Подобрать и изучить необходимую литературу
• Разбить все задачи на основные виды.
• Изучить возможные способы решения подобных задач.
• Сравнить все возможные способы решений. Сделать соответствующие выводы.
• Выбрать наиболее подходящий для меня способ решения.
• Попробовать составить полезный алгоритм для решения таких задач, которым можно будет поделиться с другими выпускниками.

ГЛАВА I

Основные понятия и определения

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

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

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

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

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

Понимание этих понятий поможет нам лучше анализировать и понимать стратегии и исходы игр.

Стратегия в теории игр – это план действий, который игрок выбирает для достижения своих целей в игре. Стратегия определяет, как игрок будет реагировать на действия других игроков и какие действия он сам будет предпринимать.

Для решения 19 задания необходимо вспомнить следующие темы и понятия:

Выигрышная стратегия

• для того чтобы найти выигрышную стратегию в несложных играх, достаточно использовать метод перебора всех возможных вариантов ходов игроков;
• для решения задач 19 задания чаще всего для этого применяется метод построения деревьев;
• если от каждого узла дерева отходят две ветви, т.е. возможные варианты хода, то такое дерево называется двоичным (если из каждой позиции есть три варианта продолжения, дерево будет троичным).

Кто выиграет при стратегически правильной игре?

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

• Может ли какой-либо из игроков выиграть, независимо от ходов других игроков?
• Что должен сделать игрок с выигрышной стратегией первым ходом, чтобы он смог выиграть, независимо от действий ходов игроков?

Рассмотрим пример:

Игра: в кучке лежит 5 спичек; играют два игрока, которые по очереди убирают спички из кучки; условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку

Решение:

• Будем использовать метод построения дерева. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3), эти два варианта отобразим при помощи дерева:

• если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:

• если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:

проанализируем стратегию игры:

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

Ответ: при правильной игре (стратегии игры) выиграет первый игрок; для этого ему достаточно своим первым ходом убрать одну спичку.

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

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

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

Разбирая разные задачи и выделила несколько предложенных способов решения подобных задач:

• Построение дерева (графа) или таблицы всевозможных вариантов, ещё этот метод называют метод перебора или ручной;
• Решение с помощью языков программирования, чаще всего на Python;
• Решение задачи с помощью Microsoft Office Excel;
• Логический метод

Все способы применимы, как к задачам для одной, так и для двух куч. Я решила рассмотреть только два способа:

Логический и при помощи языка программирования Python.

ГЛАВА II

Задача 19.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить в кучу четыре камня, или увеличить количество камней в куче в 2 раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 52. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 52 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 51.

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

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

        Первый способ “решение на языке Python”, такой способ довольно надежный и практичный. Однако, требует особых знаний и умений владения данным языком.

Итак, приведем пример программы для решения задачи:

     f=(x, h):

    if h == 3 and x >= 52:            (#if-если)

        return 1

    elif h == 3 and x < 52:          (#Elif- иначе если)

        return 0

    elif x >= 52 and h < 3:

        return 0

    else:                                       (#else- иначе)

        if h % 2 == 0:

            return f(x + 1, h + 1) or f(x + 4, h + 1) or f(x * 2, h + 1)  # стратегия победителя

        else:

            return f(x + 1, h + 1) or f(x + 4, h + 1) or f(x * 2, h + 1)  # стратегия проигравшего(неудачный ход)

for x in range(1, 52):            (#range-диапазон)

    if f(x, 1) == 1:

        print("Задача 19: ", x)          ( #print-вывод)

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

Чтобы решить задачу вторым способом, нужно следовать определенному алгоритму:

1. Определить при каком значении S камней игрок выигрывает. (Игра завершается в тот момент, когда количество камней в куче становится 52>= )

2. Внимательно прочитать условия задачи и определить возможные ходы игроков (За один ход игрок может добавить “+1” или “+4” или “ *2 ”)

3. Обозначить последовательность ходов игроков, учитывая условия задачи (1.Петя, 2.Ваня:

” Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети”)

4. Для того чтобы, найти минимальное значение камней, я предлагаю применить метод перебора, отталкиваясь от самого большого количества камней(52>=)

Самое подходящее, на мой взгляд, число 20. От него я буду отталкиваться.

Допустим, число 20 и есть минимальное кол-во камней в куче, тогда его нужно проверить.

Не обязательно проверять каждый ход Пети, ведь мы сами выбираем тот ход, при котором Петя проиграет. (“Ваня выиграл своим первым ходом после неудачного первого хода Пети”)

Итак, чтобы проверить число 20 мы выполняем следующие действия:

1.ход Пети: 20*2=40

1ход Вани: 40*2=80-Ваня победил

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

К примеру, возьмем число 16 и проверяем его:

1.ход Пети: 16*2=32

1ход Вани: 32*2=64-Ваня победил

Число 16 нам подходит, и опять же не стоит на этом останавливаться, нужно убедиться, что 16 — это самое минимальное значение.

Допустим, возьмем следующее число 13, проверяем:

1.ход Пети: 13*2=26

1ход Вани: 26*2=52-Ваня победил.

Доказываем, что число 13-минимальное значение в куче камней:

Возьмем следующее число 12, проверяем:

1.ход Пети: 12*2=24

1ход Вани: 24*2=48-Ваня не победил.

Таким образом, мы доказали, что число 13 самое минимально значение S в куче. Это и будет ответом на предложенную задачу. (Ответ: 13)

ВАЖНО! Если изначально число 20- не удовлетворяло условиям задачи, нужно действовать в обратном порядке, то есть увеличивать число, а не уменьшать. (НАПРИМЕР, если мы брали число 20, то следующем 16. НО ЕСЛИ ЧИСЛО 20 НЕ ПОДХОДИЛО, то следующее число было бы 21,22,23,24,25 и так до 51)

Задача 20

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 74. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 74 или больше камней. 

В начальный момент в куче было S камней, 1 ≤ S ≤ 73.

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

Найдите три таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

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

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

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Данную задачу можно решить несколькими способами.

Способ 1:

Через решение на языке Python

F= (x, h):

    if h == 4 and x >= 74: (#if-если)

        return 1

    elif h == 4 and x < 74: (#Elif- иначе если)

        return 0

    elif x >= 74 and h < 4:

        return 0

    else: (#else- иначе)

     if h % 2 != 0:

            return f(x + 1, h + 1) or f(x + 2, h + 1) or f(x * 3, h + 1)   # стратегия победителя

        else:

            return f(x + 1, h + 1) and f(x + 2, h + 1) and f(x * 3, h + 1)  # стратегия проигравшего

for x in range(1, 74): (#range-диапазон)

    if f(x, 1) == 1:

        print("Задача 20: ", x) ( #print-вывод)

Способ 2:

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

1. Определить при каком значении S камней игрок выигрывает. (Игра завершается в тот момент, когда количество камней в куче становится 74>= )

2. Внимательно прочитать условия задачи и определить возможные ходы игроков (За один ход игрок может добавить “+1” или “+2” или “ *3 ”)

3. Обозначить последовательность ходов игроков, учитывая условия задачи (1.Петя, 2.Ваня, 3.Петя.

”На втором ходе Петя выигрывает независимо от того, как походит Ваня”)

4. Для того, чтобы найти значения чисел, при которых Петя выиграет независимо от того, как походит Ваня, необходимо найти некое “смертельное число”. Как его найти? Нужно число, при котором игра завершается, разделить на самый “большой ход”. Число, которое получится в результате и будет является “смертельным”: 74/3=24,6(6) (За “смертельное число” мы берем только целую часть. Если число получилось изначально целым, мы убавляем его на единицу.)

5. Проверяем, действительно ли число 26 является “смертельным числом”.

Как проверить?

Мы к числу 24 прибавляем столько камней, сколько указано в условиях задачи. При этом каждый из предложенном ходов не должен оказаться выигрышным для Вани.

Например: у нас имеется всего три способа сделать первый ход, при котором по условии задачи, Ваня проиграет (За один ход игрок может добавить “+1” или “+2” или “*3”)

Итак, проверяем наше смертельное число

24+1=25-Ваня не выигрывает

24+2=26- Ваня не выигрывает

24*3=72- Ваня не выигрывает

Таким образом, при любом ходе Вани, Петя выиграет свои вторым ходом.

НО! Важно помнить, что смертельное число - это не ответ на задачу. Нам необходимо найти изначальное кол-во камней в куче, при котором бы получилось наше смертельное число.

6. Как найти изначальное число? (их может быть более одного).

Изначальное количество камней мы находим также, как проверяли наше смертельное число, только наоборот:

24-1=23

24-2=22

24/3=8

Итак, у нас получилось 3 числа: 23, 22, 8- они и будут решением данной задачи.

Однако, важно запомнить, что необходимо писать их в порядке возрастания без каких-либо знаков. (Ответ: 82223)

Задача 21

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня, или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 45 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 50.

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

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

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

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

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

Для начала:

Исключим стратегию Вани, при которой он гарантировано выиграет первым ходом.

Итак, 1_способ:

решение на языке Python.

F=(x, h):

    if (h == 3 or h == 5) and x >= 51:

        return 1

    elif h == 5 and x < 51:

        return 0

    elif x >= 51 and h < 5:

        return 0

    else:

        if h % 2 == 0:

            return f(x + 1, h + 1) or f(x + 2, h + 1) or f(x * 3, h + 1)   # стратегия победителя

        else:

            return f(x + 1, h + 1) and f(x + 2, h + 1) and f(x * 3, h + 1)  # стратегия проигравшего

def f1(x, h):

    if h == 3 and x >= 51:

        return 1

    elif h == 3 and x < 51:

        return 0

    elif x >= 51 and h < 3:

        return 0

    else:

        if h % 2 == 0:

            return f1(x + 1, h + 1) or f1(x + 2, h + 1) or f1(x * 3, h + 1)   # стратегия победителя

        else:

            return f1(x + 1, h + 1) and f1(x + 2, h + 1) and f1(x * 3, h + 1)  # стратегия проигравшего(любой ход)

for x in range(1, 51):

    if f(x, 1) == 1:

        print(x)

print("====")

for x in range(1, 51):

    if f1(x, 1) == 1:

        print(x)

2-способ:

1. Определить при каком значении S камней игрок выигрывает. (Игра завершается в тот момент, когда количество камней в куче становится 51>=.)

2. Внимательно прочитать условия задачи и определить возможные ходы игроков (За один ход игрок может добавить “+1” или “+2” или “*3”)

3. Обозначить последовательность ходов игроков, учитывая условия задачи (1.Петя, 2.Ваня, 3.Петя, 4.Ваня

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

4. Итак, для решения этой задачи, снова нужно найти то самое “смертельное число”, которое будет располагаться на втором ходе Пети. ( 51/3=17. Т.к. число получилось целым, мы отнимаем от него 1, поэтому “смертельным числом” будет являться число 16)

5.Теперь, когда мы нашли смертельное число, необходимо найти такое минимальное значение S, при котором смертельное число окажется на втором ходе Пети.

Рассмотрим несколько вариантов событий:

А) Допустим, минимальным значением S будет является число 14, тогда проверяем:

1.ход Пети: 14+1=15

1.ход Вани: 15+1=16

Итак, смертельное число оказывается на втором ходе Пети. Проверяем следующий случай:

1.ход Пети: 14+2=16

1.ход Вани: 16.....Итак, в этот раз смертельное число оказывается на первом ходе Вани, что означает его проигрыш. Поэтому по условию задачи, число 14 нам не подходит. И следующий случай хода мы можем не рассматривать.

В) Допустим, минимальным значением S будет является число 13, тогда проверяем:

1.ход Пети: 13+1=14

1.ход Вани: 14+2=16

(Почему +2, а не +1, как с числом 14? Нам необходимо привести Петю к “смертельному числу "первым ходом Вани и то, как он будет ходит мы выбираем сами, а рассматриваем мы все случаи именно первого хода Пети)

Итак, смертельное число оказывается на втором ходе Пети. Проверяем следующий случай:

1.ход Пети: 13+2=15

1.ход Вани: 15+1=16

Итак, смертельное число оказывается на втором ходе Пети. Проверяем следующий случай:

1.ход Пети: 13*3=39

1.ход Вани: 39*3=117

В этом случае, Ваня выигрывает своим первым ходом без “смертельного числа”, по 1 условию число 13 нам полностью подходит.

Осталось убедится, что 13 является минимальным значением S.

Действуем все по той же схеме:

С) Допустим, минимальным значением S будет является число 12 тогда проверяем:

1.ход Пети: 12+1=13

1.ход Вани: 13+1=15(13+2=15; 13*3=39)

Итак, число 12 нам не подходит, т.к. посоле него мы не можем ни выиграть, ни привести к “смертельному числу”. Поэтому, число 13 будет являться ответом на данную задачу.                (ответ: 13)

Заключение

В данной работе мы рассмотрели основные методы решения задач по теме «Теория игр» из Единого государственного экзамена (далее - ЕГЭ) по информатике (задания 19-21), а также попробовали найти универсальный способ решения, который подойдёт большинству обучающихся (без Python и Excel).

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

Для начала я бы порекомендовала учащимся обратиться к следующим источникам:

https://kpolyakov.spb.ru/ 

https://ege.sdamgia.ru/.

Два этих сайта предоставляют обширный банк заданий по данной теме.

И обязательно обратить внимание на то, что в актуальном ЕГЭ представлено два типа задач по теме: «Теория игр»: первый — «Задача с 1-ой кучей», и второй — «Задача с 2-мя кучами». Каждый тип требует индивидуального подхода и понимания работы теории игр и к каждому из них надо готовиться отдельно.

Разбирая разные задачи, я поняла, что если ты плохо владеешь языком программирования и тебе лень забивать формулы в Excel, то всегда модно логически поразмышлять!

Я думаю, что справлюсь с этими заданиями на экзамене, и готова поделиться с другими ребятами своим знанием.

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

1. Электронный ресурс, содержащий банк заданий по блоку «Теория игр» на ЕГЭ по информатике https://ege.sdamgia.ru/;
2. Электронный ресурс, содержащий банк заданий по блоку «Теория игр» на ЕГЭ по информатике https://kpolyakov.spb.ru/ ;
3. Электронный ресурс для поиска информации о Теории игр – Википедия https://www.wikipedia.org/.
4. https://habr.com/ru/post/163681/
5. https://kpfu.ru/portal/docs/F1858685921/lekcii24.pdf
6. https://inf-ege.sdamgia.ru