Творческая работа Как научиться искусству побеждать

ЧИСТЕНСКИЙ УВК «ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА
I – III СТУПЕНЕЙ – ГИМНАЗИЯ»
НАПРАВЛЕНИЕ МАТЕМАТИКА
«КАК НАУЧИТЬСЯ ИСКУССТВУ ПОБЕЖДАТЬ»
Работу выполнила
ученица 6а класса
Кудрявская Кристина
Научный руководитель
специалист высшей категории
Федоренко Ирина Витальевна

Чистенькое, 2013
Оглавление
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1. Стратегия успеха . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Игры – шутки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Задача про шоколадку . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Игра Ним . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3. Симметрия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4. Дополнение до фиксированного числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.1 Стратегия выигрыша в играх Ним . . . . . . . . . . . . . . . . . . . . . . . . . 11
5. Метод выигрышных позиций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Введение
Математические игры очень популярны, как, впрочем, и все игры. И далеко не всегда более сложная игра – более интересная. Часто миллионы людей с неугасаемым интересом играют в самые простые игры, и именно эти игры больше всего ценят, именно они входят в историю математики и прославляют своих создателей.
Математические науки выделили собственную дисциплину, которая исследует игровые явления как явления,  поддающиеся обработке  математическим аппаратом.
Теория игр — математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу — в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках.
Теория игр — это раздел прикладной математики. Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках — социологии, политологии, психологии, этике и других. Начиная с 1970-х годов её взяли на вооружение биологи для исследования поведения животных и теории эволюции. Очень важное значение она имеет для искусственного интеллекта.
Цель работы: научиться побеждать (выбирать стратегию успеха).
Задачи работы:
изучить методы решения нестандартных задач;
расширить свои знания по математике;
провести исследование решения некоторых типовых задач в общем виде, в измененных ситуациях, попробовать вывести «правила» решения некоторых игровых задач.
1. Стратегия успеха
Простейшие математические игры часто используют как задачи, в которых нужно найти выигрышную стратегию, либо одно положение перевести в другое.
В игровых задачах под стратегией успеха (выигрышной стратегией) понимают план игры, реализация которого позволяет игроку одержать победу независимо от действий соперника.
Задача считается решенной, если указана выигрышная стратегия.
Существуют общие правила записи решения игровых задач.
В решении игровой задачи нужно записать:
I) ход первого игрока;
II) алгоритм ходов в ответ на каждый ход соперника, т. е. стратегию победы;
III) показать, что независимо от хода соперника найдетсявозможность сделать последний победный ход.
В работе рассмотрены следующие идеи стратегий:
Игры-шутки.
Игры, использующие симметрию.
Игры, в которых стратегия — дополнение до фиксированного числа.
Игры, использующие метод выигрышных позиций.
Остановимся на каждой идее более подробно.
2. Игры-шутки
Игры – шутки – это такие игры, где для построения выигрышного алгоритма можно ничего и не знать, так как в них результат будет зависеть не от игры партнеров, а от начальных условий. Однако для этого в решении нужно заметить, что это игра-шутка, а не какая-то другая, в которой нужно искать выигрышную стратегию. На самом деле, нет никакой стратегии (а нас хотят обмануть, что она якобы есть!) Просто... как бы кто ни ходил, либо всегда выиграет первый игрок (тот, кто начинает игру), либо всегда второй. Задача - в том, чтобы математически доказать такую закономерность. Для доказательства обычно находится какая-то величина, которая понятно чему равна в начале и конце и понятно как изменяется на каждом ходу - тут даже частенько число ходов до конца однозначно посчитать можно. Это величина называется инвариантом (четность – самый известный инвариант в математике).
2.1 Задача про шоколадку
Задача 2.1.1 Двое по очереди ломают шоколадку 5x8. За ход можно разломать любой кусок по прямой линии между дольками. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?
Решение.
Долек всегда будет 5x8=40 штук, а шоколадка вначале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т.е. количество различных кусков шоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 40. Значит, игра продолжалась ровно 39 ходов. Поэтому последний (39-й) ход был обязательно ходом первого игрока (его ходы - первый, третий и все с нечетными номерами) - и первый выиграл.Вот такая получилась шутка - как ни ходи, первый всегда выигрывает.
Задача 2.1.2 Решить задачу 2.1 для шоколадки размером 3x7.
Решение.
Теперь долек будет 3x7=35 штук, а шоколадка вначале была одна. Значит, игра продолжалась ровно 34 хода. Поэтому последний (34-й) ход был обязательно ходом второго игрока. Второй всегда выигрывает.
Вывод. Стратегия успеха зависит от размеров шоколадки!
Если число кусочков шоколадки четно, тогда побеждает первый, если число нечетно, тогда второй.
2.2 Игра Ним
Задача 2.2.1 Имеется три кучки камней: в первой - 10, во второй - 15, в третьей - 20. За ход можно разбить любую кучку на две меньшие. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение.
И это задача-шутка. Количество возможных ходов для раскладывания кучек: 45 – 3 = 42. Поэтому, как бы ни ходил первый игрок, при его ходе всегда будет четное число кучек. При ходе же второго игрока количество кучек будет всегда нечетно. Значит, победит первый игрок, так как по окончании игры всегда остается ровно 45 кучек по одному камню в каждой.
Задача 2.2.2 На доске написаны цифры: 10 нулей и 10 единиц. За ход можно стереть две любые цифры и написать вместо них 0, если они были одинаковые или 1, если они были разные. Если на доске остается 1 - выигрывает первый. Если 0 - второй.Решение.
Поскольку число цифр с каждым ходом уменьшается ровно на 1 (2 стираем, одну пишем), а всего их было 20 и в конце должна остаться одна, то игра будет продолжаться ровно 19 ходов. Выигрыш зависит от четности последнего числа. Начальная сумма всех чисел четна, поэтому и в конце будет четна. А это значит, что последнее число, оставшееся в конце игры, будет четным, т.е. оно будет нулем.
Это число напишет первый игрок, а выигрывает второй.Эта задача показывает, что не в любой игре тот, кто делает последний ход, выигрывает: можно заставить противника сделать ход, после которого он проиграет.
Симметрия
Очень простой и красивый метод решения игровых задач - симметричная стратегия. Суть его - делать каждый раз ход, симметричный ходу противника или дополняющий его до чего-либо. Для доказательства правильности нашей стратегии будет пользоваться тем, что после каждого нашего хода позиция симметрична. Значит, если противник сумел сделать свой ход, то и мы сможем сделать ход, симметричный ему.
Задача 3.1 В таблице размером 1×13 девочка и мальчик по очереди закрашивают одну или две соседние клетки. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение.
Нам нужно найти такую последовательность ходов, которая позволила бы, глядя на ходы соперника, делать ходы, которые привели бы к победе. Как же ходить после хода соперника?
Количество клеток – нечетное число. Если девочка своим первым ходом закрасит седьмую (центральную) клетку таблицы, то в дальнейшем она сможет закрашивать клетки, симметричные тем, что закрасил мальчик. И понятно, что девочка выиграет.
Задача 3.2 Решить задачу 3.1 если размеры таблицы 1×20.
Решение.
Теперь и таблице количество клеток –четное число. Значит, девочка своим первым ходом должна закрасить две десятую и одиннадцатую (центральные) клетки таблицы, тогда в дальнейшем она сможет закрашивать клетки, симметричные тем, что закрасил мальчик. И понятно, что опять девочка выиграет.
Задача 3.3 Двое по очереди кладут пятаки на круглый стол так, чтобы они не накладывались друг на друга и не выступали за край стола. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение.
Стол круглый, поэтому первый ход так и просится — положить пятак в центр стола. А дальше? А дальше — по симметрии, относительно центра стола! И понятно, что первый выиграет.
Задача 3.4 Двое играют, поочередно выставляя крестики и нолики на квадратном поле 9х9. В конце каждый получает очко за каждую строку и столбец, в которых его знаков больше. Сможет ли первый игрок выиграть?
Решение.
Да. Если первый игрок занимает центральное поле и далее отвечает центрально - симметрично ходам второго игрока. В результате он выиграет центральную строку и столбец, а остальные распределятся поровну. Счет 10:8.
Задача 3.5 Имеется две кучки камней — по 7 в каждой. За ход можно взять любое количество камней, но только из одной кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение.
Камни уже разделены на две симметричные кучки. В этой игре может победить игрок, делающий второй ход, для этого он должен делать точно такие же ходы, как и первый, но только убирать камни он должен из той кучки, которую не тронул последним ходом его противник.
Как несложно понять, у победителя всегда есть ход после хода противника.
Задача 3.6 Решить задачу 3.5если в кучках различное число камней.
Решение.
Если число камней в кучках неравное, тогда начинающий своим ходом уравнивает число камней в кучках и далее действует так же как, как и в первом случае. Здесь побеждает игрок, делающий первый ход.
В данной игре симметрия несколько необычная — вроде бы и не симметрия вовсе, однако, равенство камней в кучках, и «одинаковые» ходы, проводимые игроками, очень ее напоминают.
На самом деле, нередкое явление: в зависимости от исходных данных одна и та же стратегия приносит успех то первому, то второму игроку.
Дополнение до фиксированного числа
Другая идея выигрышной стратегии в играх — дополнение хода соперника до некоторого фиксированного числа, уменьшая каждым «совместным» ходом (т. е. ход первого и второго игрока) общее число элементов на некоторое постоянное число, что сводит игру к игре с меньшим числом элементов, т. е. более простой. Понятно, что победа в данной стратегии зависит от общего количества данных по условию элементов.
Рассмотрим пример такой стратегии на конкретной задаче.
Задача 4.1 Двое играют в игру. Ходы, которые делаются по очереди, заключаются в том, что из кучки в 50 камней убирается любое число камней от 1 до 5. Выигрывает тот, кто возьмет последний камень. Кто выиграет в данной игре?
Решение.
Выработку стратегии начнем с небольшого числа камешков.
Если в нашей кучке меньше шести камней, тогда выиграет первый игрок: он первым своим ходом заберет все камни.
Если бы в нашей кучке было 6 камешков, тогда понятно, что второй выиграет, так как он забрал бы все оставшиеся камни после первого хода начинающего.
Если камней семь? Что делать тогда первому? Ему нужно забрать один камень и свести задачу к предыдущему случаю. Аналогично надо выработать стратегию игры и для 8, 9,10,11 камней.
Когда камней 12, то понятно, что выиграет второй: как бы первый не ходил, он своим ходом может взять такое количество камней, чтобы осталось ровно 6. А в этом случае он выигрывает, как мы уже разобрали.
Итак, если число камней делится на 6, то выигрывает второй, если не делится, то первый.
В нашей задаче 50 камней. Поэтому выигрывает первый, беря из кучки два камня и оставляя 48 камней. Далее после его последующих ходов в кучке будет оставаться соответственно 42, 36, 30, 24, 18, 12, 6, 0, таким образом, последний камень забирает первый игрок.
Задача 4.2 Двое играют в игру, которая заключается в прибавлении к нулю любого натурального числа, не превышающего пяти. Выигрывает тот, кто скажет число 50. Кто выиграет в данной игре?
Решение.
Игра аналогична рассматриваемой выше, только там убираются камни, а здесь добавляются числа, т. е. игра идет как бы в обратном порядке.
Начинающий первым ходом говорит число 2, и при каждом следующем ходе будет говорить число, которое больше предыдущего (т. е. сказанному им на предыдущем ходу) ровно на 6. Итак, на втором ходу он говорит число 8, на третьем - 14, ..., на девятом - 50.
Второй игрок не сможет помешать начинающему, так как максимальное число, которое он может прибавить к сказанному первым игроком — это 5, а минимальное - это 1 (а разность между числами, произносимыми первым, - 6).
Теперь рассмотрим задачу в общем виде и найдем «правило», позволяющее выбрать правильную стратегию при решении подобных задач.
Стратегия выигрыша в играх Ним
Игра Ним. Пусть лежат k камней. Играют двое, ходят по очереди. За один ход можно брать любое число камней от 1 до t. Проигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре?
Решение.
Найдем остаток от деления k на t + 1. Обозначим его a.
Если a ≠ 0. Первый игрок первым ходом должен взять aкамней. Второй игрок будет брать за один ход любое количество камней от 1 до t, тогда первый игрок своими ходами должен дополнять ходы противника до t+ 1. И тогда последний камень обязательно заберет первый игрок, а значит выиграет.
Действительно, если от kотнять a, то получим число, которое нацело делится на t+ 1. За один ход второй и первый игроки берут вместе t+ 1 камень, причем последним берет первый игрок. Так как k– a нацело делится на t+ 1, то первый игрок выиграет.
Еслиa= 0, тогда по сравнению с предыдущим случаем игроки как бы поменялись местами (число уже сразу нацело делится на t+ 1), а поэтому выигрывает второй игрок.
Задача 4.1.1 Втрёх кучах лежат 2007, 2008 и 2009 камней. Играют двое. За один ход разрешается убрать две кучи, а третью разделить на три новые (непустые) кучи. Выигрывает тот, кто не может сделать ход. Кто победит-первый или второй игрок?
Решение.
Выигрывает первый. Стратегия выигрыша проста: надо добиваться, чтобы некоторых новых кучах число камней оканчивалось цифрами 3 или 4, а в остальных новых кучах - не превышало 4. Например, кучу из 2009 камней можно разделить на такие три: 563, 663, 783 или 2, 3, 2004 и т. д. Легко видеть, что противник не может воспользоваться той же стратегией. Через несколько ходов первый игрок предложит 3 кучи: в одной 3или 4 камня, в двух других - не более, чем по 4. Второй игрок может сделать ход, а следующий ход уже невозможен.
Метод выигрышных позиций
Задача 5.1 "Хромая ладья" может ходить по прямой вправо или вверх. Исходно она стоит в нижнем левым углу доски. Играют двое. Выигрывает тот, кто поставит ладью в верхний правый угол.Решение.
Ладья стоит на главной диагонали доски. Первый игрок своим ходом уводит ее с диагонали в сторону. Тогда второй игрок может вернуть ладью обратно на диагональ. Потом первый опять уведет ее с диагонали, а второй опять сможет вернуть и т.д. Так как клетка назначения лежит на главной диагонали, то на ней ладья обязательно окажется после хода второго - и второй выигрывает.
«Множество выигрышных позиций» - это главная диагональ.
Задача 5.2Имеются две кучки конфет: в одной — 20, в другой — 21. За ход нужно съесть все конфеты в одной из кучек, а вторую разделить на две необязательно равные кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Решение.
Если мы решили использовать метод выигрышных позиций, то нам нужно найти эти выигрышные позиции. Чтобы их найти, рассмотрим простейшие случаи.
Простейшая выигрышная позиция для того игрока, кто ее создал: это 1 и 1. В этом случае побеждает тот, кто ходит вторым, так как у первого игрока нет хода.
Позиция 2 и 1 выигрышная для первого и проигрышная для второго.
Если 3 и 1, тогда второй вновь с победой, как несложно убедиться простой проверкой, так как есть ровно два хода.
Когда в кучках 3 и 2, победа у первого (убираем 3, делим 2).
Если же 3 и 3, тогда победа вновь возвращается ко второму, что можно показать простым перебором и т. д.
Замечаем закономерность: если в каждой из кучек по нечетному числу конфет, тогда позиция выигрышная для второго.
Если же хотя бы в одной из кучек четное число конфет, то такая позиция выигрышная для первого.
Когда в обеих кучках по нечетному числу конфет, то за один ход нельзя получить такую же позицию, так как при разделении любого нечетного числа на два слагаемых одно из них будет четным. Однако если хотя бы в одной из кучек четное (ненулевое) число конфет, то ее несложно разбить на два нечетных слагаемых. Таким образом, мы можем разбить все позиции на выигрышные и проигрышные с учетом того, сколько конфет в кучках. И задача выигрывающего делать ход на выигрышные позиции.
Своим первым ходом он может съест кучку из 21 конфеты, а кучу с 20 конфетами разделить на две, в которых нечетное количество конфет в обеих кучках (например, 19 и 1). Заметим, что последняя позиция, когда две кучки, по одной конфете в каждой, выигрышная, т. е. последний ход сделает первый.
Задача 5.3 На концах клетчатой полоски 1 х 20 стоит по шашке. За ход разрешается сдвинуть любую шашку в направлении другой на одну или две клетки. Перепрыгивать через шашку нельзя. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?
Решение.
Сначала перенумеруем поля доски. В любом случае за один ход, сделанный обоими игроками, расстояние между шашками сокращается не менее, чем на 2 клетки (а именно это и является главным в задаче). Поэтому можно считать, что оба игрока передвигают только одну из шашек, а вторая остается неподвижной. Расставляя знаки «+» и «-» на клетках доски согласно метода решения задачи с конечной позиции, получим следующий рисунок (если первоначально шашки не занимали клеток доски, т. е. между ними было 20 полей):
- + - - + - - + - - + - - + - - + - - +
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Таким образом, становится понятным «выигрышная» стратегия игры первого игрока, чтобы выиграть: он должен делать ходы на клетки со знаком «+», так как с любого поля со знаком «+» нельзя за один ход попасть на поле со знаком «+», а с любого поля со знаком «—» можно, т. е. сделано разбиение всего поля на «выигрышные» и «проигрышные» поля.
Выводы
Игровые задачи являются одним из самых мощных инструментов развития человеческого интеллекта. Человеку в течение всей жизни приходится не один раз оказываться в затруднительном положении, выход их которого можно найти с помощью логических рассуждений. А способность логически мыслить, и отрабатывается на решении нестандартных занимательных задач, при решении которых развивается интеллект человека. Эти задачи проверяют не знания, а умение логически рассуждать, ориентироваться в необычных ситуациях, предвидеть и действовать.
Чтобы успешно решать задачи такого вида, надо уметь выделять их общие признаки, подмечать закономерности, выдвигать гипотезы, проверять их, строить цепочки рассуждений, делать выводы. Игровые задачи от обычных отличаются тем, что не требуют вычислений, а решаются с помощью рассуждений. Можно сказать, что игровая задача – это особая информация, которую не только нужно обработать в соответствии с заданным условием, но и хочется это сделать.
Известный русский математик В.П. Ермаков говорил: «В математике следует помнить не формулы, а процесс мышления ». Это демонстрируют задачи с играми.
Литература
Вороний О.М., Готуемось до олiмпiад з математики. Харкiв Основа, 2009
Горбачев Н.В., Сборник олимпиадных задач по математике. Москва МЦИМО, 2004 г.
Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. Киров: АСА, 1994.
Петров Н.Н. Математические игры. Ижевск: УдГУ, (1 изд.) 1994.
Гарднер. Математические чудеса и тайны. 1985 г.
Интернет ресурсы.