пятнашки, пpовеpка на pешаемость
- From
- Max Alekseyev (2:5015/60)
- To
- Ilya V Bursov
- Date
- 2002-05-07T22:18:54Z
- Area
- RU.ALGORITHMS
████ OS/2 Hi, Ilya !
Replying to a message of Ilya V Bursov to All:
IVB> есть всем известные пятнашки, матpица генеpится слyчайным обpазом,
IVB> поэтомy не всегда pешабельно, можно ли быстpо пpовеpить на
IVB> pешаемость и соответсвенно пеpегене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> А всегда ли сходятся пятнашки ???
Когда-то этот вопрос уже поднимался.
Небольшое вступление
Пусть дана перестановка 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
Порядок следования пятнашек будем теперь рассматривать в соответствии с этой
нумерацией.
Нетрудно видеть, что в любом положении пустышку(пустое поле) можно перетащить на
поле номер 0 без изменения порядка следования 15 пятнашек. Назовем такую
операцию канонизацией, а все положения с пустым полем номер 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,7,6,5,4,8,9,10,11,15,14,13,12).
Так вот, позиция разрешима(в смысле из нее можно получить целевую), если
соотвествующая ей перестановка _нечетная_. В частности, вышерассмотренный пример
неразрешим.
Доказательство.
Рассмотрим как всевозможные ходы (в _обычных_ положениях) сказываются на
соответствующем _каноническом_ положении (а точнее на соотвествующей ему
перестановке).
Несложно заметить, что "горизонтальные" перемещения никак на него не влияют.
Теперь "вертикальные":
Ход 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.
Таким образом, никакие ходы не могут изменить четность позиционной перестановки.
Поэтому если мы хотим прийти к нечетной целевой позиции, то и отталкиваться мы
должны также от нечетной позиции.
То, что из целевой (нечетной) позиции нельзя получить четную я доказал. Осталось
доказать, что можно получить любую нечетную. Но это можно проверить в любом
математическом пакете (например, в Maple) - а именно, что все перестановки
соотвествующие "вертикальным" ходам порождают всю A_{15}.
Число нечетных перестановок 15-го порядка (а, значит, и разрешимых канонических
положений) есть 15!/2. Каждому же каноническому положению соответствуют 16
положений, которые в него переходят при канонизации. Таким образом, общее число
разрешимых положений есть 16*15!/2 = 16!/2
Regards, ° °
Max ~
==============================================================================
Regards, ° °
Max ~
--- OS/2 Uptime: 0d 6h 2m 8s 257ms
* Origin: Пусто внутри, и поэтому полон стакан. (2:5015/60)