Задачка о кубе

[Maximpg]

Есть куб $3$ на $3$, центральная ячейка которого - пустая, а во всех остальных расставлены числа от 1 до 26. Можно передвигать числа в соседнюю по грани ячейку, если она пустая. Можно ли, вообще говоря, поменять местами все $n$ и $27-n$, попросту говоря разбить числа на пары и поменять местами каждую?

[vorvalm]

Это задача про кубик Рубика.

[Maximpg]

Понятно, что кубик Рубика реализуется в модели из задачи. Вопрос, что дальше...

[Sonic86]

Maximpg в сообщении #715269 писал(а):

Есть куб $3$ на $3$, центральная ячейка которого - пустая, а во всех остальных расставлены числа от 1 до 26. Можно передвигать числа в соседнюю по грани ячейку, если она пустая. Можно ли, вообще говоря, поменять местами все $n$ и $27-n$, попросту говоря разбить числа на пары и поменять местами каждую?

Ответ: нельзя (любое такое преобразование выполнить нельзя)
В результате передвижения кубиков в центре должен остаться пустой кубик $E$. Множество передвижений кубиков, сохраняющий $E$ в центре - группа $H$. $H$ - подгруппа группы перестановок $S_{26}$. Если искомое преобразование существует, то оно принадлежит группе $H$. Найдем базис группы $H$.
Каждой последовательности перестановок кубика с пустым кубиком $E$ взаимно однозначно соответствует путь $E$ в графе $G$ куба $3\times 3$. Значит $H$ - гомоморфный образ группы путей $\pi_1(G)$ кубика $E$ в $G$. Известен простой способ вычисления базиса группы путей в графе - надо выбрать произвольное остовное дерево $T$ и построить все приведенные пути, содержащие в себе ровно одно ребро из $G\setminus T$ (если $G=(V,E), E$ - множество ребер $G$, $V$ - множество вершин, то мощность базиса равна $|G^1|-|T|, $ а $|T|=|G^0|-1$ - число вершин без единицы. Получается, что дерево имеет $3^3-1=26$ ребер, всего ребер $2\cdot 3^2\cdot 3=54$, значит базис $H$ имеет $28$ элементов). Выберем удобное дерево: составим его из всех горизонтальных ребер, всех вертикальных ребер среднего слоя и одного глубинного ребра среднего слоя. Теперь, если охота, можно пронумеровать вершины $G$ и вычислить базис $B$ группы $H$ явно.

(Оффтоп)

не очень хорошо получилось...

Попытаемся определить четность элементов $B$. Пусть $l$ - некий путь $E$ в графе, проходящий через ребра $T$ и содержащий только одно ребро из $G\setminus T$. Каждому замкнутому пути $E$ по $l$ в одну сторону соответствует циклический сдвиг всех чисел, лежащих в $l$ на единицу пути в противоположную сторону (причем циклический сдвиг происходит в пути, получаемом выбрасыванием $E$ из $l$). Даже точнее путь имеет вид петли с хвостиком - перестановка происходит в петле, а в хвостике все остается на месте. Значит, перестановка $\pi_l$, определяемая путем $l$, - это некий цикл. Далее, заметим, что длина $|l|$ всегда четна (разложим по базису, сколько раз шли влево, столько же идем вправо; сколько раз шли вверх, столько же идем вниз и т.п.). Значит $\pi_l$ всегда содержит нечетное число элементов (точнее длина $\pi_l$ - это длина цикла минус один минус удвоенное число ребер в хвостике). Но любая циклическая перестановка нечетной длины четна (можно явно ее представить в виде произведения транспозиций). Значит все элементы $B$ - четные перестановки, значит $H=\langle B\rangle$ - подгруппа $A_n$.
Ну и наконец, в задаче требуется осуществить перестановки $13$ пар элементов. $13$ - нечетное число, значит искомая подстановка - нечетна, а значит она не лежит в $H$.

Maximpg, спасибо за задачу!
Сейчас попробую картинки добавить.