Задачи о перестановках фигур на шахматной доске

 

Конечно, одной из самых известных занимательных игр является игра «пятнадцать», придуманная С. Ллойдом. Она относится к перестановочным играм и имеет строгую математическую теорию. И на шахматных досках существует много интересных задач и головоломок, связанных с перестановкой фигур, причем для решения некоторых из них придуман математический приём.

 

Задача 24 «Пятнадцать». В коробочке 4 ´ 4 находятся пятнадцать квадратов, пронумерованных числами от 1 до 15. Требуется, не вынимая квадраты из коробочки, переставить их так, чтобы номера шли в возрастающем порядке.

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

Всего существует 16! Расположений квадратов, и все они распадаются на два равных по численности класса. Расположения первого класса приводятся при помощи перестановок к нужному расположению квадратов, а расположения второго удается при помощи перестановок привести к нужной позиции, только с переставленными квадратами 14 и 15.

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

 

Задача 25. На доске 4 ´ 4 расставлены 15 ладей, пронумерованных числами от 1 до 15. Требуется переставить ладьи так, чтобы их номера расположились в возрастающем порядке, а пустым осталось поле d1.

Так как ходы ладьи на доске 4´4 совпадают с перемещениями квадратов в игре «пятнадцать», эта задача о ладьях изоморфна игре Ллойда. То есть существование ее решения зависит от числа транспозиций ладей в данной позиции (если число транспозиций четно, то решение существует, если нечетно – нет решения).

Задачу о ладьях можно обобщить для досок любого размера. При этом на обычной доске все позиции с 63 пронумерованными ладьями так же распадаются на 2 равных по численности класса: в одном ладьи можно расположить в возрастающем порядке (с пустым полем h1), а в другом – нет. Любопытно, что такая же ситуация имеет место и для коней, т.е. все позиции с 63 пронумерованными конями распадаются на 2 класса, и в половине случаев коней можно расположить в возрастающем порядке, а в половине – нет. Для пронумерованных ферзей и королей необходимая перестановка возможна при любой начальной позиции, а для слонов задача лишена смысла, так как они не могут менять своего цвета.

 

Задача 26. Старинная головоломка.

Эту задачу придумал итальянец Гуарини ещё в XVI в. Она встречается в книгах по занимательной математике. В углах доски размером 3´3 стоят два белых и два чёрных коня (рис. 25, а). Требуется поменять местами белых и чёрных коней за наименьшее число ходов.

Наиболее изящно задача решается при помощи «метода пуговиц и нитей», открытого известным мастером математических головоломок Г. Дьюдени. На каждое поле маленькой доски, кроме центрального (на него кони попасть не могут), поместим по пуговице (на рис.25, б их заменяют кружки). Если между двумя полями возможен ход коня, то соответствующие пуговицы свяжем нитью (на рисунке нити – это отрезки прямой). Полученный клубок пуговиц и нитей распутаем так, чтобы все пуговицы расположились по кругу (рис. 25, а).

Теперь задача решается почти автоматически. Выбрав одно из направлений движения по кругу, будем переставлять коней до тех пор, пока они не поменяются местами. Чтобы переместить коней на доске, нужно заменить пуговицы соответствующими полями. Нетрудно убедиться, что решение состоит из 16 перемещений коней (восьми белых и восьми чёрных), причём кони противоположного цвета могут ходить по очереди. Если дополнительно потребовать, чтобы кони разного цвета при движении не угрожали друг другу (очерёдность ходов в этом случае позволяется нарушать), то решение тоже найдём на рис. 25, в. Необходимо только следить за тем, чтобы белые и чёрные кони не оказались соседями в клубке. Если круговое движение (против часовой стрелки) начинает белый конь а1, то решение будет такое: Ка1-b3, Ка3-с2, Кс-b1-а3, Кс1-а2-с3, Кb3-с1-а2, Кс2-а1-b3, Ка3-с2-а1, Кс3-b1-а3, Ка2-с3, Кb3-с1.

                  

 

                           а)                                         б)                                           в)

 

Рис. 25

 

Метод пуговиц и нитей легко объяснить в терминах теории графов. Действительно, задаче о перестановке коней можно сопоставить граф, вершины которого соответствуют полям доски (пуговицам), а рёбра – возможным ходам коня между полями (нитям). Тогда распутывание клубка пуговиц и нитей есть не что иное, как более наглядное расположение графа на плоскости.

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

 

 

Заключение

 

При написании работы я открыла для себя целый новый мир – шахматную математику.

У меня получилась следующая классификация найденных и прорешанных математических задач на шахматную тему:

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

В работу я поместила лишь некоторые задачи. Но, по моему мнению, их достаточно для того, чтобы показать, что шахматная математика привлекательна и интересна для молодых людей. Многие шахматные задачи до сих пор не решены и заслуживают пристального внимания и приложения интеллектуальных сил. Сейчас при решении задач на помощь к человеку приходит компьютер. Им уже поставлено много рекордов. Сейчас компьютеры могут решать окончания с семью фигурами и меньше, находя порой невероятные решения. К примеру, программисты Марк Буржуцкий и Яков Коновал обнаружили фантастический результат для семифигурного окончания «ферзь и конь против ладьи, слона и коня», в котором белые выигрывают лишь через 517 ходов! Мы можем только удивляться. Но, кто знает, может быть, в XXII веке дело дойдет и до 32 фигур на доске, и загадка шахмат будет окончательно разгадана?!

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

• метод раскраски, разрезания фигур;
• использование теории игр;
• использование теории графов;
• использование комбинаторных вычислений;
• «метода пуговиц и нитей».

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

 

 

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