РЕФЕРАТ

Математические  игры и головоломки

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

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

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

Игры 

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

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

Игра  ним и другие аналогичные  игры 

      Существует  несколько игр, в которых двое играющих  A и B, руководствуясь определёнными правилами, по очереди вынимают то или иное число фишек из одной или нескольких кучек – побеждает тот, кто берёт последнюю фишку. Простейшая такая игра – это игра с одной кучкой фишек, и сделать ход в ней – значит взять из кучки любое число фишек от 1 до m включительно. Многие подобные игры поддаются исследованию с помощью числа Шпрага-Гранди G(C). Пустой позиции O, не содержащей фишек, отвечает G(O)=0. Комбинацию кучек, состоящих соответственно из x, y, … фишек, обозначим C=(x, y, …) и предположим, что допустимые ходы переводят C в другие комбинации: D, E, … Тогда G(C) есть наименьшее неотрицательное число, отличное от G(D), G(E), … Это позволяет по индукции определить G(C) для любой комбинации C, разрешённой правилами игры. Так, в упомянутой задаче G(x)=x mod (m+1).

      Если G(C)>0, то игрок, делающий следующий ход, допустим, это игрок A, может обеспечить себе выигрыш, если ему удастся перейти к “безопасной” комбинации S с G(S)=0. Действительно, по определению G(S) в этом случае либо S – пустая позиция, и тогда A уже выиграл, либо B следующим ходом должен перейти к “опасной” позиции U с G(U)>0 – и тогда всё повторяется снова. Такая игра после конечного числа ходов заканчивается победой A.

      К подобным играм относится ним. Имеется произвольное число кучек фишек, и игроки по очереди выбирают одну какую-то кучку и вынимают из неё любое число фишек (но хотя бы одну обязательно).

      Более общий случай представляет игра Мура, которую также можно назвать k-ним. Правила её те же, что и в обычном ниме (1-ним), но здесь разрешается бать фишки из любого количества кучек, не превосходящего k.

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

      Есть  интересная вариация игры ним под  названием “звёздный ним”. Она довольно проста, но стратегия в ней видна не сразу. Играют в эту игру на звездообразной фигуре, изображённой на рис. 1, слева. Поставьте по одной фишке на каждую из девяти вершин звезды. Игроки A и B делают ходы по очереди, снимая при каждом ходе либо одну, либо две фишки, соединённые отрезком прямой. Тот, кто снимает последнюю фишку выигрывает.

      У игрока B при игре в звёздный ним есть выигрышная стратегия, использующая симметрию игровой доски (вообще, выигрышные стратегии многих математических игр строятся на этом). Представим, что отрезки прямых, соединяющие вершины звезды, - это нити. Тогда всю конфигурацию можно развернуть в окружность, топологически эквивалентную нитяной звезде. Если A снимает с окружности одну фишку, то B снимает две фишки с противоположного участка окружности. Если A берёт две фишки, то B снимает с противоположного участка окружности одну фишку. В обоих случаях на окружности остаются две группы из трёх фишек. Какую бы фишку (или какие бы фишки) ни взял A из одной группы, B берёт соответствующую фишку (или фишки) из другой группы. Ясно, что последняя фишка достанется игроку B. 

Другие  математические игры 

      В конце 60-х годов Дж. Леутуэйт из шотландского города Терсо изобрёл замечательную  игру с искусно скрытой стратегией “парных ходов”, обеспечивающей второму  игроку заведомый выигрыш. На доске  размером 5*5 квадратных клеток в шахматном  порядке расставлены 13 чёрных и 12 белых  фишек, после чего любая из чёрных фишек, например, стоящая на центральном  поле, снимается (рис. 2, слева).

      Игрок A ходит белыми фишками, игрок B – чёрными. Ходы делаются по вертикали и горизонтали. Проигравшим считается тот из игроков, кто первым не сможет сделать очередной ход. Если доску раскрасить подобно шахматной доске, то станет ясно, что каждая фишка со своего поля переходит на поле другого цвета и что ни одну фишку нельзя заставить ходить дважды. Следовательно, игра для каждого игрока не может продолжаться более 12 ходов. Но она может окончиться и раньше выигрышем для любого игрока, если только B не будет придерживаться рациональной стратегии.

      Рациональная  стратегия для игрока В состоит  в том, чтобы мысленно представить  себе всю матрицу (за исключением  пустой клетки), покрытую двенадцатью  неперекрывающимися костями домино. Как именно они разложены на доске, не имеет значения. На рис. 2, справа показан один из способов покрытия доски костями домино. Какой бы ход ни сделал игрок А, В просто делает ход на ту кость домино, которую только что покинул А. При такой стратегии у В всегда есть ход после очередного хода А, поэтому В заведомо выигрывает за 12 или за меньшее число ходов.

      В игру Леутуэйта можно играть не только фишками на доске, но и квадратными  плитками или кубиками, передвигаемыми внутри плоской коробочки, на дне  которой начерчена матрица. Предположим  теперь, что в правила игры внесена  поправка, позволяющая любому игроку в любое время ходить любым  числом (от 1 до 4) фишек, стоящих на одной  горизонтали или вертикали, если первая и последняя фишки в  выбранной им горизонтали или  вертикали “его” цвета. Перед  нами великолепный пример того, как  тривиальное (на первый взгляд) изменение  правила приводит к резкому усложнению анализа игры. Леутуэйту не удалось  найти выигрышную стратегию ни для  одного из игроков в этом варианте игры.

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

Головоломки 

      Математические  головоломки бывают самые разные: вращательные (кубик Рубика), “Волшебные кольца”, “Игры с дыркой” (пятнашки), решётчатые и многие другие. Мы рассмотрим лишь некоторые из них. 

Вращательные  головоломки 

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

      Знаменитейшая головоломка нашего времени –  кубик Рубика – начала своё победное шествие по свету с 1978 года, когда  с ней впервые ознакомились математики на Международном математическом конгрессе  в Хельсинки. Лишь несколько кубиков  увезли математики с конгресса, но это  стало начальным толчком лавинного  распространения игрушки по всему  миру.

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

      Кубик Рубика относится к вращательным головоломкам, отличительной чертой которых является то, что запутать их проще простого, а вот также  быстро собирать их умеет далеко не каждый. При запутывании мы действуем  как попало и стараемся испортить  сразу всё, при сборке же охватить сразу всю картину слишком  сложно, нам удобнее продвигаться методично, шаг за шагом, устанавливая сначала один кусочек, подгоняя к  нему второй и т. д. По мере выстраивания правильной картины свобода наших действий ограничивается, ведь достигнутое надо на последующих шагах сохранять. А ближе к концу сборки очередные продвижения уже невозможны без жертв, – мы вынуждены на время отдавать завоёванное с тем, чтобы вернуть его с прибылью. Здесь уже требуются специально разработанные операции, можно назвать их “локальными” или “минимальными”, которые вносят в расположение элементов головоломки самые малые изменения, например, переставляют два-три элемента или переворачивают их. При этом “минимальные” не значит “маленькие” - обычно они состоят из довольно большого числа ходов.

      Рассмотрим  алгоритм собирания вращательных головоломок  на примере кубика Рубика. 

Формулы операций в “кубике  Рубика” 

      При использовании “минимальных” операций возникает естественный вопрос: как  их систематизировать или сформулировать, чтобы ими удобно было пользоваться при собирании кубика. Прежде всего, перед тем, как воспользоваться  той или иной уже разработанной  операцией, следует как-то обозначить грани кубика, относительно которых  их проводить. Стандартные их названия: фасад, тыл, лево, право, верх, низ. А  обозначения соответственно: Ф, Т, Л, П, В, Н. Любую формулу операций можно  выполнить с помощью поворотов  боковых или центральных граней кубика. Один поворот грани по часовой  стрелке обозначается так же, как  и сама грань (Ф, Т и т. д.). Если грань поворачивают против часовой  стрелки, то к обозначению этого  действия приписывают знак ’ (Ф’, Т’ и т. д.). Понятно, что два поворота по часовой стрелке идентичны двум поворотам против, а следовательно обозначаются они одинаково: знаком ². (Ф², Т² и т. д.). С помощью этой системы обозначений можно сформулировать лишь повороты боковых граней, для центральных же обозначения показаны на рисунке 3.