|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 10 Mar 2003 20:42:26
To : Valentine Kropov
Subject : Игpа Пятнашки
--------------------------------------------------------------------------------
Replying to a message of Valentine Kropov to Max Alekseyev:
VK> ЗЫ: как из пpоизвольного pазложения, не пpиводя ни к каким стандаpтным
VK> схемам узнать, возможно ли собpать сабж или нет?
================================= Алгоритмы ==================================
From: Max Alekseyev 2:5015/60 13 Aug 1998 23:05:26
To: Denis Tanayev
Subj: Пятнашки
==============================================================================
Hi, Denis !
Replying to a message of Denis Tanayev to All:
DT> А всегда ли сходятся пятнашки ???
Когда-то этот вопрос уже поднимался.
Hебольшое вступление
Пусть дана перестановка X=(x_1,x_2,...,x_n).
Инверсией называется пара (x_i,x_j) такая, что i<j и x_i>x_j.
Четность перестановки определяется как четность числа инверсий в ней.
Перестановка X это на самом деле биекция
X: {1,2,...,n} --> {1,2,...,n}, определяемая как X(i)=x_i.
X можно переписать ввиде X=(X(1),X(2),...,X(n)).
Теперь, если есть две перестановки X,Y одного порядка n, то их произведением
называется их композиция (как отображений). Т.е.
XY=(X(Y(1),X(Y(2)),...,X(Y(n))). Эта операция некомутативна, то есть результат
зависит от порядка следования сомножителей. Кроме того, существует единичная
(тождественная) перестановка E=(1,2,...,n), обладающая тем свойством, что
XE=EX=X для любой перестановки X.
Таким образом, множество S_n всех перестановок n-го порядка с такой операцией
умножения превращается в группу.
Четность произведения определяется так же как и для чисел:
чет на чет=чет
чет на нечет=нечет
нечет на чет=нечет
нечет на нечет=чет
Множество A_n всех четных перестановок также образует группу. Множество нечетных
перестановок B_n группы не образует, но выражается как B_n = A_n Y, где Y -
произвольная нечетная перестановка.
Теперь, собственно, к чему все это.
Занумерум поля "Пятнашек" так
0 1 2 3
7 6 5 4
8 9 10 11
15 14 13 12
Порядок следования пятнашек будем теперь рассматривать в соответствии с этой
нумерацией.
Hетрудно видеть, что в любом положении пустышку(пустое поле) можно перетащить на
поле номер 0 без изменения порядка следования 15 пятнашек. Hазовем такую
операцию канонизацией, а все положения с пустым полем номер 0 - каноническими.
Таким образом, каждому положению соответствует единственное каноническое
положение, в котором порядок следования пятнашек сохраняется.
Пример.
Положению
ЪДДДДВДДДДВДДДДВДДДДї
і 5 і 8 і 11 і 7 і
ГДДДДЕДДДДЕДДДДЕДДДДґ
і 14 і 2 і 6 і 13 і
ГДДДДЕДДДДЕДДДДЕДДДДґ
і 12 і і 10 і 3 і
ГДДДДЕДДДДЕДДДДЕДДДДґ
і 1 і 4 і 15 і 9 і
АДДДДБДДДДБДДДДБДДДДЩ
соотвествует каноническое
ЪДДДДВДДДДВДДДДВДДДДї
і і 5 і 8 і 11 і
ГДДДДЕДДДДЕДДДДЕДДДДґ
і 2 і 6 і 13 і 7 і
ГДДДДЕДДДДЕДДДДЕДДДДґ
і 14 і 12 і 10 і 3 і
ГДДДДЕДДДДЕДДДДЕДДДДґ
і 1 і 4 і 15 і 9 і
АДДДДБДДДДБДДДДБДДДДЩ
Теперь каждому игровому положению поставим в соотвествие перестановку 15
элементов, которую будем получать по положению 15 пятнашек в соответствующем
каноническом положении.
Так примеру выше будет соответствовать перестановка
(5,8,11,7,13,6,2,14,12,10,3,9,15,4,1),
а целевой позиции (собранному полю) будет соотвествовать перестановка
(1,2,3,4,8,7,6,5,9,10,11,12,15,14,13).
Так вот, позиция разрешима(в смысле из нее можно получить целевую), если
соотвествующая ей перестановка _нечетная_. В частности, вышерассмотренный пример
неразрешим.
Доказательство.
Рассмотрим как всевозможные ходы (в _обычных_ положениях) сказываются на
соответствующем _каноническом_ положении (а точнее на соотвествующей ему
перестановке).
Hесложно заметить, что "горизонтальные" перемещения никак на него не влияют.
Теперь "вертикальные":
Ход 0->7 есть на самом деле умножение слева на _четную_ перестановку
(7,1,2,3,4,5,6,8,9,10,11,12,13,14,15)
Ход 1->6 - умножение слева на _четную_ перестановку
(1,6,2,3,4,5,7,8,9,10,11,12,13,14,15)
Ход 2->5 - умножение слева на _четную_ перестановку
(1,2,5,3,4,6,7,8,9,10,11,12,13,14,15)
Ход 3->4 не влияет на каноническое положение (умножение на _четную_ единичную
перестановку E)
Ход 7->0 - умножение слева на _четную_ перестановку
(2,3,4,5,6,7,1,8,9,10,11,12,13,14,15)
и т.д. и т.п.
Замечание. Ходы 0->7 и 7->0 взаимно обратны. Это видно и на соотвествующих
перестановках: их произведение равно единичной перестановке E.
Таким образом, никакие ходы не могут изменить четность позиционной перестановки.
Поэтому если мы хотим прийти к нечетной целевой позиции, то и отталкиваться мы
должны также от нечетной позиции.
То, что из целевой (нечетной) позиции нельзя получить четную я доказал. Осталось
доказать, что можно получить любую нечетную. Hо это можно проверить в любом
математическом пакете (например, в Maple) - а именно, что все перестановки
соотвествующие "вертикальным" ходам порождают всю A_{15}.
Число нечетных перестановок 15-го порядка (а, значит, и разрешимых канонических
положений) есть 15!/2. Каждому же каноническому положению соответствуют 16
положений, которые в него переходят при канонизации. Таким образом, общее число
разрешимых положений есть 16*15!/2 = 16!/2
Regards, ш.ш
Max ~
==============================================================================
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.8
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
