Путешествия по графам

Игры и головоломки

Путешествия
по графам

Д. И. ВАКАРЕЛОВ (НРБ)

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

Мы предложаем вам широкий класс игры, обобщающих знаменитию игры в «пятнадцать» Сэма Ллюйда. Некоторые из них по трудности не уступают кубику Рубика, причем, в отличие от него, очень просты в изготовлении, так что каждый может придумать и изготовить сколько угодно таких головоломок. Мы рассскажем о двух играх этого класса, а затем даим их общее описание.

Головоломка ТЕРПЕНИЕ

Вырежьте из картона восемь кружков с пятиопеечную монету и напишите

A= 2,1,4,6,7,0.

A^{-1}= 7,6,4,1,2,0.

Рис 2 A

Рис 2 A^{-1}

на каждом из них одну из букв слова ТЕРПЕНИЕ. На листе бумаги начerte схему, изображенную на рисунке 1, которое будем называть церповым полем. Круjukи игрового поля будем называть ячейками, а написанные около них числа — номерами ячейек. Ячейки, соединенные отрезками, будем называть соседним. Расположите круjukи-фишки в произвольном порядке в ячейках игрового поля так, чтобы центральная ячейка (№ 0) осталась свободной. Под ходом будем попомать перемещение некоторой фишки в соседнию с ней свободную ячейку. Первым ходом игры может быть перемещение фишки из ячейки с номером 2 или 7 в ячейку с номером 0. Цель игры состоит в том, чтобы посредством серии ходов привести произвольное расставленные фишки в конфигурацию, показанную на рисунке 1.

А пока попробyte, не читая статью дальнейше, вооружиться терпением и самостоятельно решить головоломку ТЕРПЕНИЕ. Для этого сначала более легкую задачу.

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

В результате мы получим либо стандартную конфигурацию, либо одну из следующих трех:

$$\begin{array}{cccc} T & P & E & T & E & T & E \\ a = \Pi & E & b = \Pi & P & c = \Pi & E \\ H & I & E & H & I & E & H & I \end{array}$$

Позному возникает следующая задача.

Задча 2. Найдите три последовательности ходов, X, Y и Z, которые соответственно преобразуют конфигурации a, b и c в стандартную. Последовательность ходов записьать последовательностью номеров ячейек, занимаемых фишками, которые делается очередной ход.

Вот одно из решений задачи 2, дающее вместе с решением задачи 1 алгоритм решения игры ТЕРПЕНИЕ. X=2,3,5,8,7,0,2,1,4,6,7,8,5,3,2,0,7,8,5,3,2,0,7,6,4,1,2,3,5,8,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2,1,4,6,7,0,2

ких серий, действие которых обозримо и легко запоминается, а затем составлять из них любую последовательность ходов. При этом оказываются полезными следующие четыре серии (ячеека с номером 0 свободна перед их выполненем):
$$A=2,1,4,6,7,0, A^{-1}=7,6,4,1,2,0, B=7,8,5,3,2,0, B^{-1}=2,3,5,8,7,0.$$
Обозначения $A^{-1}$ и $B^{-1}$ показывают, что действия этих серий образны действиям серий $A$ и $B$.

Условиям $A, A^{-1}, B$ и $B^{-1}$ называют элементарными сериями, а преобразования, которые они производят — элементарными (допустимыми) преобразованиями. На рисунке 2 изображены наглядные схемы-графики, демонстрирующие действия этих серий на фишки игрового поля.

Элементарные серии имеют одно поленое свойство: после их выполнения центральная ячеека снова становится свободной, что дает возможность выполнять их в произвольном порядке одну за другой. Конечную последовательность элементарных серий, например $A, AB, A^{-1}BA$, будем называть допустимой серей или формулой, а ее действие на фишки игрового поля — допустимый преобразование. При исследовании действия различных формул условиями используется фишки, на которых вместо букв написаны цифры от 1 до 8. Тогда стандартной конфигурацией фишек будем считать ту, при которой каждая фишка находится в ячееке с соответствующим ей номером.

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

Если две формулы $X$ и $Y$ производят одинаковые преобразования, то будем писать $X=Y$. Пусть серию ходов, которая не изменяет конфигурацию будем обозначать символом 1. Если $X$ и $Y$ — две допустимые серии, то произведение $XY$ тоже является допустимой серей, действие которой состоит в последовательном выполнения $X$ и $Y$. Нетрудно видеть, что $A^{-1}A=AA^{-1}=1, B^{-1}B=BB^{-1}=1$. Аналогично, для любого допустимого преобразования $X$ имеется обратное, то есть такое, что $X^{-1}X=XX^{-1}=1$.

Пусть $G_1$ — множество всех допустимых преобразований. В этом множество определяется операция умножения, то есть для любых $X$ и $Y$ из $G_1$ определяено произведение $XY$, состоящее в последовательном выполнения преобразования $X$, а затем — преобразования $Y$.

Это умножение обладает следующими свойствами: 1) $(XY)Z=X(YZ)$; 2) существует преобразование 1 такое, что $X \cdot 1=1 \cdot X=X$; 3) для любого $X$ существует $X^{-1}$ такое, что $X^{-1}X=XX^{-1}=1$.

В математике произвольное множество $G$, в котором введена операция умножения, обладающая свойствами 1—3, называется группой. Мы показали, что построенная нами совокупность допустимых преобразований $G_1$ является группой. Можно при этом добавить, что группа $G_1$ порождает преобразования $A$ и $B$.

Оказывается, построенная групп-

па $G_1$ обладает достаточно набором преобразований для решения головоломки ТЕРПЕНИЕ.

Задача 3. Пусть дана произвольная конфигурация фишек цры ТЕРПЕНИЕ со свободной центральной ячейкой. Докажите, что существует формула $X$ из $G$, которая дает решение цры ТЕРПЕНИЕ.

Решение этой задачи будет получено после того, как мы найдем алгоритм решения игры ТЕРПЕНИЕ.

Мы выясим также, какие конфигурации фишек, на которых написаны номера от 1 до 8, могут быть приведены к стандартной конфигурации.

Упражнения

1. Пусть неокоторое преобразование $X \in G_1$ допускает запись $X = X_1X_2...X_n$, где $X_i \in G_1$. Докажите, что $X^{-1} = X_n^{-1} \cdot X_{n-1}^{-1} \cdot ... \cdot X_1^{-1}$.
2. Нарисуйте графики действия преобразования $A^2, A^3, B^2, B^3, ABAB^{-1}A^{-1}$.
3. Пусть неокторая фишка неподвижна при выполнении преобразования $X$. Докажите, что она останется неподвижной и при преобразования $P^{-1}XP$, где $P$ — допустимое преобразование.
4. Докажите тождества $A^5 = B^5 = 1$, $A^4 = A^{-1}, A^3 = A^{-2}, (ABA^{-1})^4 = AB^{-1}A^{-1}$.

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

«Программирование формул»
При поисках алгоритма решения головоломки наиболее трудным делом является описание формул с заранее заданными графиками. Это немного

напоминает программирование, при котором команды — это элементарные преобразования, а программы — формулы, то есть последовательности команды.

Рассмотрим некоторые практические примеры этого своего образования.

A. Преобразования $ABA^{-1}B^{-1}$ и $A^{-1}B^{-1}AB$, действие которых показано на рисунке 3, в 2, называются коммутаторами. Они интересны тем, что представляют некоторые пары точек, оставляя остальные точки неподвижными.

B. Очень интересно преобразование $ABA$ (рис. 3, $\partial$), распадающейся на два цикла. Для него $(ABA)^5$ — это цикл, показанный на рисунке 3, $e$.

В задаче 2 для преобразования конфигурации $a$ к стандартному виду нужно было найти последовательность ходов, при которой буквы $P$ и $E$ оказываются на своих местах. Легко видеть, что этого можно добиться с помощью преобразования $X_2$, график которого показан на рисунке 4, $6$.

В. Расмотрим операцию, которая в теории групп называется сопряжением. С ее помощью можно действие неокторого преобразования перевести на другую зону игрового поля. Например, найдем формулу для преобразования $X_1$ (см. рис. 4, $\delta$). Для этого с помощью преобразования $B^{-2}$ перемещаем фишку 3 на место фишки 7, а фишку 5 — на место фишки 2. Затем применяем цикл $(ABA)^5$ и, наконец, преобразования $B^2$ возвращаем фишки 2 и 7 на старые места.

Получился цикл $4 \rightarrow 3 \rightarrow 5 \rightarrow 4$ с формулой $B^{-2}(ABA)^5B^2$.

В обшем случае операция сопряжения имеет вид $Q_1 = PQP^{-1}$. При этом говорят, что преобразование $Q$ сопряжение с преобразованием $Q_1$. В нашем случае $Q = (ABA)^5$, $P = B^{-2}$.

Аналогично $X_2 = A^{-2}X_1A^2$ и $X_3 = B^{-1}X_2B$. Отметим, что $X_2$ и $X_3$ осуществляют такое же действия, как преобразования $X$ и $Z$ из задачи 2, но имеют значительное большую длину. Преобразование $Y$, как легко понять, допускает запись $Y = Z^2$.

Сопряженем коммутатора $A^{-1}B^{-1}AB$ с $B^{-2}$ получаем формулу для $X_4 = B^{-2}(A^{-1}B^{-1}AB)$ $B^2 = B^{-2}A^{-1}B^{-1}AB^{-2}$ (мы воспользовались тем, что $B^3 = B^{-2}$).

Г. При построении формул с нужными свойствами можно действовать и инчаче. Осуществим для примера цикл $3 \rightarrow 5 \rightarrow 8 \rightarrow 3$. Будем выполнять перемещения фишек 3, 5, 8, не интересуясь судьбой остальных фишек, так, как показано на рисунке 5. В результате мы получим нужную перестановку с формулой $B^{-2}ABA^{-1}BAB^{-2}$. Тепер нужно проследить, что же происходит с остальных фишками. Для этого строим график полученного преобразования (рисунок 6, а). Получился еще один цикл длины 5, который можно уничтожить, даже не возведя в 5-ю степень, а с помощью предварительного выполнения операции $A^{-1}$. Итак, $X_3 = A^{-1}B^{-2}ABA^{-1}BAB^{-2}$.

Уражнение 5. Запишите формулы для преобразования, заданных графиками на рисунках 6, 7, 8.

Алгоритм решения игры ТЕРПЕНИЕ

Мы будем пользоваться формулой для $X_4$ и операцией сопряжения. Решение осуществляется в два этапа.

Первый этап. Установка на свой места трех букв E. Для этого специальные формулы не нужны, хотя при желании можно их выписать для каждой конкретной позиции.

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

| Буква в ячейке, 3 | Преобразование, ставящее ее на место |
| :— | :— |
| Т | $A^{-2}X_4A^2 = A^{-2}B^{-2}A^{-1}B^{-1}AB^{-2}A^2$ |
| П | $A^{-1}X_4A = A^{-1}B^{-2}A^{-1}B^{-1}AB^{-2}A$ |
| Н | $X_4 = B^{-2}A^{-1}B^{-1}AB^{-2}$ |
| И | $AX_4A^{-1} = AB^{-2}A^{-1}B^{-1}AB^{-2}A^{-1}$ |
| Р | $X_4$ — если стандартная конфигурация еще не доступна |

В приведенном алгоритме существует то, что в слове ТЕРПЕНИЕ две буквы E.

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

Уражнение 6. Получите алгоритмы решения игры англійского слова PATIENCE и болгарского слова ТЬРПЕНИЕ.

7. Постройте теорию игр УПОРСТВО, ВЕРЕНИЦА, СМЕКАЛКА — в этих словах есть по две повторяющиеся буквы, но стоит они не на тех местах, как в игре ТЕРПЕНИЕ.

Груша игры ТЕРПЕНИЕ

Каждай элемент α группы $G_1$ переставляет фишки. Пусть $\alpha(i)$ — номер фишки, на место которого переходит фишка из ячейки $i$. Набор чисел $\alpha(1), \alpha(2), \dots, \alpha(8)$ называется перестановкой из чисел 1,2,…,8. Итак, каждому элементу группы $G_1$ соответствует некоторая перестановка.

Множество $S_n$ всех перестановок множества из $n$ элементов образует группу (произведение $\alpha\beta$ перестановок $\alpha$ и $\beta$ заключается в их последовательном выполнении, то есть $(\alpha\beta)(i) = \beta(\alpha(i))$. Эта группа называется симметрической группой. Мы убедились, что группу $G_1$ можно считать частью группы $S_8$.

Пусть теперь $f = f(x_1, x_2, \dots, x_8)$ — некоторый многочлен от всех переменных и $\alpha \in S_8$ — некоторая перестановка. Заменим теперь в многочлене $f$ переменную $x_1$ на $x_{a(1)}$, переменную $x_2$ — на $x_{a(2)}$, …, переменную $x_8$ — на $x_{a(8)}$. Мы получим новый многочлен $\alpha f = f(x_{a(1)}, x_{a(2)}, \dots, x_{a(8)})$.

Понятно, что для двух перестановок $\alpha$ и $\beta$ будет $(\alpha\beta)f = \beta(\alpha f)$.
Рассмотрим многочлен $P_n(x_1, x_2, \dots, x_n) = (x_1 - x_2)(x_1 - x_3) \dots (x_1 - x_n) \dots (x_2 - x_3) \dots (x_2 - x_n) \dots (x_{n-1} - x_n)$.

Перестановка $\alpha \in S_n$ называется четной, если $\alpha P_n = P_n$, и нечетной, если $\alpha P_n = -P_n$.

Упражнения

8. Докажите, что при перестановке любых двух переменных $x_i$ и $x_j$ многочлен $P_n$ переходит в $-P_n$.

9. Любая перестановка либо четна, либо нечетна.

10. Если $\alpha$ и $\beta$ — перестановки одинаковой четности, то $\alpha\beta$ — четная перестановка.

11. Если $\alpha$ и $\beta$ — перестановки разной четности, то $\alpha\beta$ — нечетная перестановка.

12. Перестановки $\alpha$ и $\alpha^{-1}$ имеют одинаковую четность.

13. Перестановки, соответствующие элементарным сериям $A, A^{-1}, B, B^{-1}$, — четные.

Из упражнения 8—12 следует, что множество $A_n$ всех четных перестановок образует группу. Эта группа называется знакоперменной группой порядка $n$.

Из упражнения 13 следует, что $A_8 \supset G_1$. Получаясь существование алгоритма решения игры ТЕРПЕНИЕ и результатами упражнения 10—12, можно доказать, что $A_8 = G_1$. Следовательно, с помощью $G_1$ можно осуществить любую четную перестановку фишек 1,2,…,8 и нельзя осуществить никакую нечетную перестановку.

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

Головоломка ДОМ

Игровое поле этой игры изображено на рисунке 7. Фишки для игры занумерованы цифрами от 1 до 9. В качестве элементарных серий игры используется следующие:

$A = 1, 4, 7, 8, 5, 2, 0; \quad A^{-1} = 2, 5, 8, 7, 4, 1, 0; \quad B = 2, 5, 8, 9, 6, 3, 0; \quad B^{-1} = 3, 6, 9, 8, 5, 2, 0; \quad C = AB = 1, 4, 7, 8, 9, 6, 3, 0; \quad C^{-1} = 3, 6, 9, 8, 7, 4, 1, 0.$

Алгоритм решения использует следующие две формулы:

$$X_5 = A^2 B^{-2} (ABA^{-1} B^{-1}) B^2 A^{-2} = A^2 B^{-2} CA^{-1} BA^{-2};$$

$$X_6 = (ABAB^{-1} ABA^{-2} B^{-1})^3 = (CAB^{-1} CA^{-2} B^{-1})^3.$$

Эти формулы можно получить с помощью описанных выше примов.

Этап 1. Установка на места фишек 1,4,7 и 8. Для этого целлюлозуется формула $X_5$ (анаалогично тому, как использовалась формула $X_4$ на этапе 2 алгоритма игры ТЕРПЕНИЕ). Отметим, что при каждом использовании формулы $X_5$ меняют свои места фишки 1 и 4. Поэтому в конце этапа они могут оказаться переставлены. Тогда с помощью формулы $X_6$ ставим их на свои места. Пусть $G_2$ — группа игры DOM.

Упражнение 15. Докажите, что группа $G_2$ совпадает с симметрической группой $S_9$. Указание. Докажите, что соответствует из существования описанного выше алгоритма решения.

Путешествия по графам

Читатель уже должен быть ясно, как можно самостоятельно придумать новые игры типа ТЕРПЕНИЕ и DOM. На рисунке 9 приведены еще несколько примеров таких игры.

Упражнения

16. Найдите алгоритмы решения игры ПЯТНАДЦАТЬ, ДУМАЙ БЫСТРЕЕ, КОМБИНАТОР и КУБОЛОГИЯ. Докажите, что соответствующие им группы — знакоперменные (типа $A_n$).

Обратите внимание, что все игры из упражнения 16 содержат по две одинаковые фишки (в первой из них — это фишки 6 и 9).

17. Найдите алгоритмы решения игры СТАДИОН, КРЕСТ, ДЕСЯТЬ. Покажите, что соответствующие им группы симметрические (типа $S_n$).

18. Докажите, что группы $S_n$ и $A_n$ содержат соответствующее $n! = 1,2...n$ и $\frac{1}{2} n!$ элементов.

Фигуры, подобные игровым полям рассмотренных головоломок, называются графами. Отсюда их общее название — «путешествия по графам». Более точно, граф — это конечное множество точек, называемых вершинами, некоторых которых соединены дугами, называемых ребрами графа. Очевидно, что любой граф можно связать с одной или несколько итераций и группами перестановок, которые им соответствуют. Читатель, может быть, уже заметил, что группы рассмотренных игры являются либо знаком переменными (типа $A_n$), либо симметрическими (типа $S_n$). Оказывается, что это не случайно: при некоторых весы общих ограничениях на структуру графов им всегда будет соответствовать группы либо типа $A_n$, либо типа $S_n$. Чтобы сформировать более точную эдиительную закономерность, нам понадобятся следующие определения.

Под простым циклом дины $k$ ($k \geqslant 3$) будем поннимать последовательность вершин графа $P_1,...,P_k$, которая удовлетворяет следующим условиям:

1. $P_1 = P_k$ (то есть начальная и последняя вершина цикла совпадает);
2. $P_i$ и $P_{i+1}$ связаны ребром ($i=1,...,k-1$),

3. $P_i \neq P_j$ при $i \neq j$ ($i, j=1, \dots, k-1$).

Граф будем называть циклический, если любые две вершины этого графа принадлежат неокторому простому циклу.

Теорема. Пусть $\Gamma$ произвольный циклический граф с вершинами $P_0, P_1, \dots, P_n$, а $G(\Gamma)$ — группа церры «путешествие по $\Gamma$» с фишками 1,…, $n$. Тогда справедливо следующее утверждение:

1. если все простые циклы $\Gamma$ имеют четную длину, то $G(\Gamma)$ совпадает с группой $A_n$;

2. если граф $\Gamma$ отличи от графа $\Gamma_6$, изображенного на рисунке 10, и содержит хотя бы один простый цикл нечетной длины, то $G(\Gamma)$ совпадает с группой $S_n$.

Доказательство этого утверждения мы опускаем. Заметим, что частиные случан этой теоремы уже доказаны ранее. Интерес представляется исключение, связанное с графом $\Gamma_6$ (рис. 10). На ЭВМ были вычислены все перестановки группы $G(\Gamma_6)$ и было установлено, что она является собственным подмножестом группы $S_6$, состоящим из 120 элементов. Если мы хотим, чтобы игра «путешествие по графу $\Gamma_6$» всегда имела решение, то необходимо использовать по крайней мере три одинаковые фишки. Это — единственный граф с таким свойством.

Модификции игра

Рассмотрим теперь неокторые модифики «путешествие по графам», связанные с переворочанием фишек и ограничениями на «правила движения».

Пусть фишки для игры ДОМ имеют квадратную форму и окрашены с двух сторон: одна сторона — в белый, а другая — в черный цвет. Поместим фишки на игровое поле, изображенное на рисунке 7, причем некоторые из них помещим белой стороной вверх, а неоторные — черной. Кроме старых правил передвижения фишек по игровому полю, введем одну новую операцию $R$: если ячейка с номером 0 свободна, то можно перевернуть одновременно все фишки, находящиеся в ячейках 4, 5 и 6. Цель игры — с помощью допустимых преобразований и операции $R$ перевернуть все фишки белой стороной вверх («зажигание света в окнах»). Задчача условияется, если на белой стороне каждой фишки написать соответствующее цифры от 1 до 9 и потребовать, чтобы в конце игры каждой фишка была не только белой стороной вверх, но и занимала ячейку с соответствующим ей номером. Эту игру будем называть СВЕТЯШИЕСЯ ОКНА.

Упражнение 19. Найдите алгоритмы решения для общих вариантов игры СВЕТЯШИЕСЯ ОКНА.

Конечно же, это далеко не единственный пример введения эффектива переорентиции фишек в играх типа «путешествие по графу». Например, в статье А. Калинина «Сначала был только кубик» («Наука и. жизнь»),

(Окончание см. на c. 60)