V Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Игры и стратегии с точки зрения математики
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
1. Введение.
Математические науки выделили собственную дисциплину, которая исключительно исследует игровые явления как явления, поддающиеся обработке математическим аппаратом. Истоки теоретико-игровых рассуждений восходят с работам Баше де Мезирака (середина 17 века). Сама же идея создания математической теории конфликта - теории игр - формируется с начала 20 века, о чем свидетельствуют труды К. Бутона, Э. Ласкера, Е. Мура, Э. Цермело, Э. Бореля, Г. Штейнгауза.
Теория игр представляет собой раздел математики, занимающейся исследованием вопросов поведения и разработкой оптимальных правил (стратегий) поведения каждого из участников в конфликтной ситуации.
Однако даже математическая теория игр не способна стопроцентно предопределить исход некоторых конфликтов.
Математические игры очень популярны, как, впрочем, и все игры. И далеко не всегда более сложная игра – более интересная. Часто миллионы людей с неугасаемым интересом играют в самые простые игры, и именно эти игры больше всего ценят, именно они входят в историю математики и прославляют своих создателей.
Простейшие математические игры часто используют как задачи, в которых нужно найти выигрышную стратегию, либо одно положение перевести в другое.
Иногда задачи бывают весьма простыми, когда они решаются известными методами, такими как инвариант и раскраска, но есть и весьма простые, но до сих пор неразрешённые задачи, связанные с математическими играми.
Что такое игровая, стратегическая задача? Это не совсем обычная математическая задача, так как, во-первых, в ней часто нет ничего числового, то есть непонятно, а что, собственно говоря, нужно решать или точнее, что писать в решении таких задач?
Во-вторых, иногда в играх нельзя придумать алгоритм победы или, как говорят, стратегию победы, то есть иметь возможность действовать определенным алгоритмическим образом в ответ на каждый ход противника, иными словами, в игре возможна победа и без стратегии, а также ничья.
В-третьих, для решения игровой задачи нужно уметь правильно записать его. И эта запись зависит, например, от того, кто выигрывает в данной игре.
Итак, сложностей при решении данного типа задач достаточно. Поэтому мы определяем следующую цель своей работы:
изучить новые методы решения нестандартных задач, классификацию данных методов; расширить свои знания по математике;
2. Основные идеи решения игровых задач
Как уже было сказано выше, для решения игровой задачи нужно уметь правильно записать его. И эта запись зависит, например, от того, кто выигрывает в данной игре.
Поэтому сначала рассмотрим общие правила записи решения игровых задач.
Так как же правильно записать решение игровой задачи?
В решении игровой задачи нужно записать:
I) ход первого игрока;
II) алгоритм ходов в ответ на каждый ход соперника, т. е. стратегию победы;
III) показать, что найдется независимо от хода соперника возможность сделать ход, т. е. его последний ход будет победным.
В работе рассмотрены следующие идеи стратегий:
Игры-шутки.
Игры, использующие симметрию.
Игры, в которых стратегия — дополнение до фиксированного числа.
Игры, использующие метод выигрышных позиций
Остановимся на каждой идее более подробно.
3. Игровые задачи.
1. Игры-шутки.
Игры – шутки – это такие игры, где для построения выигрышного алгоритма можно ничего и не знать, так как в них результат будет зависеть не от игры партнеров, а от начальных условий. Однако для этого в решении нужно заметить, что это игра-шутка, а не какая-то другая, в которой нужно искать выигрышную стратегию. На самом деле, нет никакой стратегии (а нас хотят обмануть, что она якобы есть!) Просто... как бы кто ни ходил, либо всегда выиграет первый игрок (тот, кто начинает игру), либо всегда второй. Задача - в том, чтобы математически доказать такую закономерность. Для доказательства обычно находится какая-то величина, которая понятно чему равна в начале и конце и понятно как изменяется на каждом ходу - тут даже частенько число ходов до конца однозначно посчитать можно. Это величина называется инвариантом (четность – самый известный инвариант в математике).
Инвариант (от лат. invarians - неизменяющийся), в математике - величина, остающаяся неизменяемой при тех или иных преобразованиях.
1. В ряде задач встречается следующая ситуация. Некоторая система последовательно изменяет своё состояние, и требуется выяснить нечто о её конечном состоянии. Полностью проследить за всеми переходами может оказаться делом сложным, но иногда ответить на требуемый вопрос помогает вычисление некоторой величины, характеризующей состояние системы и сохраняющейся при всех переходах (такую величину называют инвариантом для рассматриваемой системы). Ясно, что тогда в конечном состоянии значение инварианта будет то же самое, что и в начальном, т.е. система не может оказаться в состоянии с другим значением инварианта.
2. На практике этот метод сводится к тому, что некоторая величина вычисляется двумя способами: сначала она просто вычисляется в начальном и конечном состояниях, а затем прослеживается её изменение при последовательных мелких переходах.
3. Наиболее простым и часто встречающимся инвариантом является четность числа; инвариантом может быть также и остаток от деления не только на 2, но и на какое-нибудь другое число. Для построения инвариантов иногда бывают полезны вспомогательные раскраски, т.е. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета).
Многие задачи легко решаются, если заметить, что некоторая величина имеет определённую чётность. Из этого следует, что ситуации, в которых эта величина имеет другую чётность, невозможны. Иногда эту величину (функцию) надо сконструировать, например, рассмотреть чётность суммы или произведения, разбить объекты на пары, заметить чередование состояний, раскрасить объекты в 2 цвета.
Отметим, что часто для нахождения идеи решения задачи можно использовать «метод маленьких чисел», т. е. начинать поиск решения с небольших чисел.
Задача 1. Двое по очереди ломают шоколадку 5x8. За ход можно разломать любой кусок по прямой линии между дольками. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?
Решение: Долек всегда будет 5x8=40 штук, а шоколадка в начале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т.е. количество различных кусков шоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 40. Значит, игра продолжалась ровно 39 ходов. Поэтому последний (39-й) ход был обязательно ходом первого (его ходы - первый, третий и все с нечетными номерами) - и первый выиграл.Вот такая получилась шутка - как ни ходи, первый всегда выигрывает.
Решить ту же задачу в общем виде, про шоколадку MxN.
Если число кусочков шоколадки четно, тогда побеждает первый, если число нечетно, тогда второй.
Задача – игра Ним.
Задача 2. Имеется три кучки камней: в первой - 10, во второй - 15, в третьей - 20. За ход можно разбить любую кучку на две меньшие. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение: И это задача-шутка. Количество возможных ходов для раскладывания кучек: 45 – 3 = 42. Поэтому, как бы ни ходил первый игрок, при его ходе всегда будет четное число кучек. При ходе же второго игрока количество кучек будет всегда нечетно. Значит, победит первый игрок, так как по окончании игры всегда остается ровно 45 кучек по одному камню в каждой.
2.Симметрия.Очень простой, но мощный и красивый метод решения игровых задач - симметричная стратегия. Суть его - делать каждый раз ход, симметричный ходу противника или дополняющий его до чего-либо. Доказательство правильности нашей стратегии будет пользоваться тем, что после каждого нашего хода позиция симметрична: раз так, то если противник сумел сделать свой ход, то и мы сможемсделать ход, симметричный ему.
Задача 1. Двое по очереди кладут пятаки на круглый стол так, чтобы они не накладывались друг на друга и не выступали за край стола. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение: Нам нужно найти такую последовательность ходов, которая позволила бы, глядя на ходы соперника, делать ходы, которые привели бы к победе. Как же ходить после хода соперника? Стол круглый, поэтому первый ход так и просится — положить пятак в центр доски. А дальше? А дальше — по симметрии, относительно центра стола! И понятно, что первый выиграет.
Можно отметить, что если доска обладает центром симметрии (и не обязательно круглая), тогда первый сможет выиграть на ней, действуя аналогичным образом: ставя свою фишку или монету в центр стола, а затем используя центральную симметрию.
Заметим, что симметрия бывает не только центральной, но и осевой. Рассмотрим одну из таких задач.
Задача 2. Двое по очереди ставят слонов в клетки шахматной доски 8x8 так, чтобы слоны не били друг друга. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение: Здесь нет центральной клетки. А если бы и была, поставить симметрично относительно нее слона мы не можем, так как тогда слон вставал на поле, которое бьется слоном, который поставил соперник.
Но шахматная доска обладает другим свойством симметрии. У нее целых четыре оси симметрии. Используем симметрию относительно оси, которая проходит параллельно одной из сторон доски. Тогда, ставя своего слона симметрично относительно этой оси слону, поставленному первым игроком, выигрывает второй игрок.
3. Игры, в которых стратегия — дополнение до фиксированного числа.
Другая идея выигрышной стратегии в играх — дополнение хода соперника до некоторого фиксированного числа, уменьшая каждым «совместным» ходом (т. е. ход первого и второго игрока) общее число элементов на некоторое постоянное число, что сводит игру к игре с меньшим числом элементов, т. е. более простой. Понятно, что победа в данной стратегии зависит от общего количества данных по условию элементов.
Рассмотрим пример такой стратегии на конкретной задаче.
Задача 1. Двое играют в игру. Ходы, которые делаются по очереди, заключаются в том, что из кучки в 50 камней убирается любое число камней от 1 до 5. Выигрывает тот, кто возьмет последний камень. Кто выиграет в данной игре?
Решение: И опять выработку стратегии лучше начинать с небольшого числа камешков. Понятно, что если в нашей кучке меньше шести камней, тогда выиграет первый игрок: он первым своим ходом заберет все камни.
Если бы в нашей кучке было 6 камешков, тогда понятно, что второй выиграет, так как он забрал бы все оставшиеся камни после первого хода начинающего.
Если камней семь? Что делать тогда первому? Ему нужно забрать один камень и свести задачу к предыдущему случаю. Аналогично надо выработать стратегию игры и для 7, 8, 9,10,11 камней.
Когда камней 12, то понятно, что выиграет второй: как бы первый не ходил, он своим ходом может взять такое количество камней, чтобы осталось ровно 6. А в этом случае он выигрывает, как мы уже разобрали.
Итак, если число камней делится на 6, то выигрывает второй, если не делится, то первый. Докажем это.
Пусть у нас 6tкамней. После первого хода игрока, начинающего игру, второй делает ход, после которого остается 6t - 6 камней, т. е. число камней в кучке уменьшилось на 6. Несложно понять, что последний камень возьмет игрок, делающий второй ход, и также понятно, что у него всегда есть возможность сделать ход.
Пусть у нас 6t+a, где 1 < а < 5, камней. Тогда начинающий первым своим ходом убирает все, что «мешает», т. е. а камней, и остается всего 6t камней, т. е. сводит игру к рассматриваемому выше случаю, где он уже второй игрок. Значит в этом случае побеждает игрок, делающий первый ход.
В нашей задаче 50 камней. Поэтому выигрывает первый, беря из кучки два камня и оставляя 48 камней. Далее после его последующих ходов в кучке будет оставаться соответственно 42, 36, 30, 24, 18, 12, 6, 0, таким образом, последний камень забирает первый игрок.
Задача 2. Двое играют в игру, которая заключается в прибавлении к нулю любого натурального числа, не превышающего пяти. Выигрывает тот, кто скажет число 50. Кто выиграет в данной игре?
Решение: Мы видим, что игра совершенно аналогична рассматриваемой выше, только там убираются камни, а здесь добавляются числа, т. е. игра идет как бы в обратном порядке.
Начинающий первым ходом говорит число 2, и при каждом следующем ходе будет говорить число, которое больше предыдущего (т. е. сказанному им на предыдущем ходу) ровно на 6. Итак, на втором ходу он говорит число 8, на третьем - 14, ..., на девятом - 50.
Второй игрок не сможет помешать начинающему, так как максимальное число, которое он может прибавить к сказанному первым игроком — это 5, а минимальное - это 1 (а разность между числами, произносимыми первым, - 6).
5. Метод выигрышных позиций
Задача 1.Имеются две кучки конфет: в одной — 20, в другой — 21. За ход нужно съесть все конфеты в одной из кучек, а вторую разделить на две необязательно равные кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение: Если мы решили использовать метод выигрышных позиций, то нам нужно найти эти выигрышные позиции. Чтобы их найти, рассмотрим простейшие случаи.
Простейшая выигрышная позиция для того игрока, кто ее создал: это 1 и 1. Понятно, что в этом случае побеждает тот, кто ходит вторым, так как у первого игрока нет хода.
Очевидно, что позиция 2 и 1 выигрышная для первого и проигрышная для второго.
Если 3 и 1, тогда второй вновь с победой, как несложно убедиться простой проверкой, так как есть ровно два хода.
Когда в кучках 3 и 2, победа у первого (убираем 3, делим 2).
Если же 3 и 3, тогда победа вновь возвращается ко второму, что можно показать простым перебором и т. д.
Замечаем закономерность: если в каждой из кучек по нечетному числу конфет, тогда позиция выигрышная для второго.
Если же хотя бы в одной из кучек четное число конфет, то такая позиция выигрышная для первого.
Несложно понять, что когда в обеих кучках по нечетному числу конфет, то за один ход нельзя получить такую же позицию, так как при разделении любого нечетного числа на два слагаемых одно из них будет четным. Однако если хотя бы в одной из кучек четное (ненулевое) число конфет, то ее несложно разбить на два нечетных слагаемых. Таким образом мы можем разбить все позиции на выигрышные и проигрышные с учетом того, сколько конфет в кучках. И задача выигрывающего делать ход на выигрышные позиции.
После этого уже понятно, кто выиграет в данной по условию игре и как ему этого добиться.
Делим все возможные ходы на «выигрышные» и «проигрышные». Если после разбиения получились две кучки с нечетным числом конфет, тогда назовем такую позицию «выигрышной», а все остальные — «проигрышные».
Стратегия победителя заключается в том, что он делает ход на «выигрышные» поля. Так как первый может сделать ход на «выигрышное» поле, а хода с одного «выигрышного» поля на другое нет, и с любого «проигрышного» поля за один ход можно попасть на «выигрышное», то побеждает начинающий. Своим первым ходом он может съест кучку из 21 конфеты, а кучу с 20 конфетами разделить на две, в которых нечетное количество конфет в обеих кучках (например, 19 и 1). Заметим, что последняя позиция, когда две кучки, по одной конфете в каждой, выигрышная, т. е. последний ход сделает первый.
3. Заключение.
Несомненно, что игровые задачи являются одним из самых мощных инструментов развития человеческого интеллекта. Человеку в течение всей жизни приходится не один раз оказываться в затруднительном положении, выход их которого можно найти с помощью логических рассуждений. А способность логически мыслить, и отрабатывается на решении нестандартных занимательных задач, при решении которых развивается интеллект человека. Эти задачи проверяют не знания, а умение логически рассуждать, ориентироваться в необычных ситуациях, предвидеть и действовать.
Наша дальнейшая работа над этой темой кажется нам еще перспективой, потому что именно теории игр посвящено задание № 26 из ЕГЭ по информатике.
Работая в среде программирования Scratch мы встретились с некоторыми проблемами. Нам хотелось более углубленно изучить горизонты возможностей нашего исследования, но в связи с тем, что это программа ориентирована на детей начальной школы, нам не все удалось осуществить. Позже мы планируем продолжить это исследование, но уже обхватив множество других способов решения задач, проводя работу в другой среде программирования Lazarus.
Используемая литература:
Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. Киров: АСА, 1994.
Гусев В.А., Орлов И.А., Розенталь А.Л. Внеклассная работа по математике в 6-8 классах. М.: Просвещение, 1984.
Петров Н.Н. Математические игры. Ижевск: УдГУ, (1 изд.) 1994.
Гарднер. Математические чудеса и тайны. 1985 г.
Шень А. Ш47 Игры и стратегии с точки зрения математики. | 2-е изд., стерео- типное. | М.: МЦНМО, 2008. | 40 с.: ил.