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

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение дополнительного образования детей «Заочная физико-техническая школа

Московского физико-технического института (государственного университета)»

ИНФОРМАТИКА и ИКТ

Элементы теории математических игр

Задание №3 для 11-х классов

(2013 – 2014 учебный год)

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

Составитель: Е.Г. Молчанов, ассистент кафедры высшей математики МФТИ.

Информатика: задание №3 для 11-х классов (2013 – 2014 учебный год), 2013, 25 с.

Дата отправления задания – 14 января 2014 г.

Составитель:

Молчанов Евгений Геннадьевич

Подписано 22.10.13. Формат 60×90 1/16.

Бумага типографская. Печать офсетная. Усл. печ. л. 1,56. Уч.-изд. л. 1,38. Тираж 400. Заказ №24-з.

Заочная физико-техническая школа Московского физико-технического института (государственного университета)

ООО «Печатный салон ШАНС»

Институтский пер., 9, г. Долгопрудный, Москов. обл., 141700. ЗФТШ, тел./факс (495) 408-51-45 – заочное отделение,

тел./факс (498) 744-63-51 – очно-заочное отделение, тел. (499) 755-5580 – очное отделение.

e-mail: zftsh@mail.mipt.ru

Наш сайт: www.school.mipt.ru

© ЗФТШ, 2013

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

Элементы теории математических игр

§ 1. Математические игры

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

Пример 1. Можно ли считать ЕГЭ по математике игрой?

Определимся с количеством участников. С одной стороны, балл за ЕГЭ является конкурентным преимуществом или недостатком одного абитуриента перед другим – пишущие ЕГЭ конкурируют между собой напрямую и при написании ЕГЭ ведут борьбу за реализацию своих интересов поступления в лучшие ВУЗы страны, например, в МФТИ. С другой стороны, каждый выполняет задания самостоятельно и может не обращать внимания на то, что одновременно с ним эти же задания выполняют и другие. Однако даже если целью пишущего ЕГЭ не является поступление в ВУЗы (что приводит к конкуренции), его итоговый балл зависит не только от своих результатов и умений, а от результатов всех остальных участников. Дело в том, что шкала перевода из «первичных» баллов в «тестовые» (по 100-балльной системе) устанавливается уже после проведения ЕГЭ и зависит от совокупных результатов всех участников. Поэтому, в принципе, ЕГЭ по математике, вне зависимости от целей каждого его участника, может считаться игрой. Данный пример показывает, что «игрой» согласно написанному выше определению может считаться огромное количество жизненных ситуаций.

Пример 2. Два игрока по очереди пишут цифры на доске слева направо. Если после восьми ходов полученное 10-значное число делится на девять, побеждает второй игрок, иначе – первый. Докажите, что второй игрок может победить, как бы ни ходил первый игрок.

Второй игрок должен дополнять число, написанное первым игроком, до девяти. Если ход первого игрока – «9», то ход второго игрока – «0» и т. п. После восьми ходов получим 10-значное число, сумма цифр которого равна 9*5=45, и полученное число будет делиться на девять. Таким образом, второй игрок сможет выиграть при любых ходах перво-

го игрока. У второго игрока есть выигрышная стратегия (более по-

дробно см. в следующем параграфе).

Зададимся вопросом: а всегда ли существенны действия игроков?

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

Пример 3. Петя и Вася записывают на двух листах бумаги по натуральному числу (не показывая записи друг другу). Если сумма этих чисел чѐтна, то выигрывает Петя. Если сумма нечѐтна, выигрывает Вася. Как играть Пете?

Ответ на этот вопрос прост: что бы Петя ни написал, его шанс выиграть составляет 50/50. Существуют игры, в которых нет способа, позволяющего игроку выиграть наверняка.

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

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

Условие 1. В игре участвуют два игрока.

Условие 2. Игра заканчиваются выигрышем одного из участников. Это автоматически означает проигрыш соперника. Иногда в математических играх допускают ничью.

Условие 3. В игре участники ходят по очереди и помнят все предыдущие ходы.

Условие 4. Игра характеризуется позицией, которая зависит

только от ходов игроков.

Пример 4. Два человека встречаются и обмениваются закрытыми сумками, понимая, что одна из них содержит деньги, другая — товар. Каждый игрок может уважать сделку и положить в сумку то, о чѐм договорились, либо обмануть партнѐра, дав пустую сумку. Является ли эта игра математической?

Во-первых, эта игра не удовлетворяет условию 2: в условии не определено, какой игрок выигрывает в каком случае, а какой автоматически при этом проигрывает. Во-вторых, игроки ходят одновременно, а не по очереди, что нарушает условие 3. Поэтому данная игра не является математической.

Заметим, что условие 2 можно выполнить, считая, что в случае если один игрок обманул другого, обманувший игрок выиграл, а обманутый проиграл, в остальных случаях (оба игрока честные или оба обманщи-

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

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

Пример 5. Петя и Вася подкидывают игральный кубик. Если выпадет 1, выиграет Петя, если выпадет 2, 3, 4, 5 или 6 – выиграет Вася. Является ли эта игра математической?

Хоть в условии и прослеживается явная «несправедливость» по отношению к Пете, дело не в этом. Вне зависимости от того, какие числа на игральном кубике считать выигрышными для Пети и Васи, в данной игре результат зависит именно от игрального кубика. От ходов Пети и Васи (если они играют честно) вообще ничего не зависит, поскольку таковые ходы по условию игры отсутствуют вовсе. Условие 4 говорит, что позиция зависит только от непосредственных ходов самих игроков, т. е. позиция не должна зависеть от монеток, раскладов, игральных кубиков и прочего. Следовательно, и эта игра не является математической игрой.

Итак, в математической игре имеются два игрока, которые ходят поочередно. Участник, который начинает игру, обычно называется первым игроком, его соперник – вторым. Имеется конечное или бесконечное множество позиций. В каждой позиции для обоих игроков указаны допустимые ходы – разрешѐнные переходы в другие позиции. Некоторые позиции объявляются выигрышными для какого-то игрока, что автоматически означает, что эти позиции являются проигрышными для соперника. Очень часто выигрышными объявляются те, и только те позиции, из которых соперник не может сделать ход, т. е. выигрывает тот игрок, которому удаѐтся своим последним ходом достичь позиции, в которой у соперника нет допустимых ходов.

Пример 6. Игра «Ним». Есть две кучи по семь камней в каждой. За ход разрешается взять любое количество камней, но только из одной кучи. Проигрывает тот, кто не сможет сделать ход. Как можно определить позиции в данной игре, и какие позиции будут выигрышными?

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

Позицией в данной игре являются два числа (x,y): x – количество камней в первой куче, y – количество камней во второй куче. Игрок выигрывает, если противник не может сделать ход, т. е. перед ходом противника камней в обеих кучах не останется. Таким образом, позиция (0, 0) является выигрышной для того из игроков, который попал туда своим последним ходом.

Особенно отметим следующее.

Во-первых, в играх могут быть ничьи. Это значит, что некоторые позиции для обоих игроков объявляются ничейными. Игроку целесообразно добиваться ничьей только тогда, когда он не может гарантированно достичь выигрышной позиции.

Во-вторых оба игрока не обязательно должны преследовать одинаковые цели (например, чтобы противник не смог сделать ход). Так, например, в примере 2 один из игроков стремится к тому, чтобы полученное число не делилось на девять, а второй стремится к обратному.

Поэтому позиция должна ещѐ характеризоваться номером игрока (либо того, который пришѐл в эту позицию, либо того, который делает ход из этой позиции в зависимости). Так, если в примере 7 добавить номер игрока, который делает ход, то теперь позиция в этой задаче будет выражаться тремя числами (x,y,n), где n – номер игрока, который делает ход, имея в начале x камней в первой куче, а у – во второй.

Позиция (0,0,1) будет проигрышной для первого игрока (он не может сделать ход) и выигрышной для второго, позиция (0,0,2) – наоборот.

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

Пример 7. В точке 0 оси координат находится фишка. За ход игрок обязан подвинуть фишку на единицу влево или вправо. Выиграет тот игрок, после хода которого, координата фишки превысит десять. Как определить позиции в данной игре? Какие позиции следует объявить выигрышными? Какие позиции следует объявить ничейными?

Позицией является целое число (x): положение фишки на оси. При этом все позиции с x > 10 будут проигрышными для первого игрока,

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

т. е., выигрышными для второго. Стартуя из позиции (10), первый игрок может одним ходом передвинуть фишку в позицию (11) и выиграть. Если же игра начинается из позиции (x), [x < 10], то ни первый, ни второй игрок не могут гарантированно рассчитывать на победу, так как любой игрок в данной игре может не позволить своему противнику достичь выигрышной позиции, просто двигая каждый раз своим ходом фишку влево. Поэтому, стартуя из позиции (x), [x < 10], игра может закончиться выигрышем одного из игроков, если и только если соперник ошибется. Но что следует считать исходом игры при старте, например, из начала координат (как в условии примера)? Можно было бы, например, считать, что исход игры при старте из начала координат просто не определен. Но мы потребуем выполнения более жесткого условия.

Дополнительное условие математических игр

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

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

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

Для того, чтобы игра из примера 7 удовлетворяла условию 5, нужно кроме уже заданных выигрышных позиций (x), [x > 9] объявить все позиции (x), [x < 10] ничейными1.

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

1 Таким образом, в примере 7 при старте из любой точки кроме точки (10) игроки не сделают ни одного хода, и немедленно будет объявлен результат.

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

ничью. Так, в шахматах троекратное повторение одной и той же позиции на доске является поводом для объявления ничьей2.

§ 2. Стратегия. Правильная игра

Вернемся к примеру 6 и зададимся вопросом: кто выиграет? Заметим, что в общем случае может выиграть любой из игроков –

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

Выигрышной стратегией назовѐм набор правил, следуя которым, один из игроков обязательно выиграет при произвольных ответах со-

перника.

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

Подчеркнѐм в определении стратегии условие «при произвольных ответах соперника». Важно понимать, что на месте игрока может оказаться что или кто угодно, например компьютер. Нужно уметь отвечать на произвольные ходы соперника и в любом случае выигрывать.

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

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

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

Теорема

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

Идея доказательства этого утверждения в частном случае будет рассмотрена при решении задач методом анализа с конца (см. § 3).

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

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

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

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

Таким образом, ответить на вопрос, заданный в самом начале (см.

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

Взаключение параграфа отметим, что согласно теореме выигрышная или ничейная стратегия существуют даже в таких математических играх, как шахматы и шашки. Но если бы кто-то знал эти самые стратегии…

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

2013-2014 уч. год, №3, 11 кл. Информатика и ИКТ. Элементы теории математических игр

§3. Решение задач

3.1.Удачный ход

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

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

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

Пусть это неверно и второй игрок не сможет сделать хода. Разберѐм два случая.

Случай 1. На поле предполагаемого хода уже стоит ладья. Но эта ладья не могла быть поставлена ранее вторым игроком, так как он ставит ладьи только центрально симметрично ходам первого игрока. Если первый игрок ранее поставил ладью на это поле, то второй игрок был обязан своим ходом поставить ладью на поле, центрально симметричное полю противника. Однако по условию на это поле ладью поставил первый игрок текущим ходом. Получаем противоречие.

Случай 2. Данное поле находится под боем какой-то ладьи. Заметим, что эта ладья не была поставлена первым игроком на предыдущем ходе, так как две центрально симметричные ладьи не бьют друг друга. Тогда, в соответствии со стратегией второго игрока, ладья, расположенная центрально симметрично данной, также должна уже стоять на доске. Однако эта ладья будет бить ладью, поставленную первым игроком предыдущим ходом. Противоречие.

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

Пример 9. В кучке лежит: а) 30 камней; б) 32 камня. За ход можно взять от одного до четырѐх камней из

2013, ЗФТШ МФТИ, Молчанов Евгений Геннадьевич

По отзывам покупателей Иван Иванович оценил надёжность двух интернет-магазинов. Вероятность того, что нужный товар доставят из магазина А, равна 0,8. Вероятность того, что этот товар доставят из магазина Б, равна 0,9. Иван Иванович заказал товар сразу в обоих магазинах. Считая, что интернет-магазины работают независимо друг от друга, найдите вероятность того, что ни один магазин не доставит товар.

Перед началом волейбольного матча капитаны команд тянут жребий, чтобы определить, какая из команд начнёт игру с мячом. Команда «Мотор» по очереди играет с командами «Статор», «Стартер» и «Ротор». Найдите вероятность того, что «Мотор» будет начинать с мячом только вторую игру.

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

Стрелок стреляет по 4 одинаковым мишеням по одному разу, вероятность промаха 0,2, найдите вероятность что он попадёт в первую мишень, а в 3 оставшиеся промахнется.

Стрелок стреляет по одному разу по каждой из пяти одинаковых мишеней. Вероятность поразить мишень каждым отдельным выстрелом равна 0,8. Во сколько раз вероятность события «стрелок поразит ровно четыре мишени» больше вероятности события «стрелок поразит ровно три мишени»?