Раздвижная головоломка 3 x 2

Question

Можно ли решить такую ​​скользящую головоломку (x - пробел) ?:

1  3  2

4  5  x

Я не смог это решить и даже не знаю, возможно ли это.

Answer 1

Решение:

нет, невозможно перейти с позиции, которую вы дали, к "решенной" головоломке с помощью $1,2,3,4,5$в правильном порядке и пробел в правом нижнем углу. Это можно доказать так же, как и в оригинальной (знаменитой) « головоломке 14,15 ».

Это можно показать, используя некоторую базовую теорию групп, аналогичную найденному здесь доказательству .

Каждое положение головоломки можно интерпретировать как перестановку $\{1,2,3,4,5,6\}$, с пустым квадратом, интерпретируемым как $6$. Тогда каждый ход головоломки можно интерпретировать как перестановку в симметричной группе$S_6$, заменяя пустой квадрат $6$с одной из настоящих плиток. Позиция, которую вы указали, находится на расстоянии одного транспонирования от решенной позиции, но она может быть достигнута только за четное количество$6$-swaps, так как этот пустой квадрат $6$должен оказаться в том же положении, поэтому он должен иметь четное количество движений вверх-вниз и четное количество движений влево-вправо. Но любая комбинация четного числа транспозиций должна быть в чередующейся группе.$A_6$, и, следовательно, с помощью такой комбинации мы не можем достичь единого транспонирования.

Answer 2

Если ваша цель - получить «1 2 3» в первой строке и «4 5 x» во второй, ответ отрицательный , это невозможно.

Это уменьшенная версия головоломки Сэма Лойда 14-15 . Если у вас есть скользящая головоломка с одним пустым пространством, вы можете проверить, разрешима ли она на основе четности - количества переключателей, которые вам понадобятся, чтобы добраться до решения. Конкретно:

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

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

В вашем примере для решения головоломки требуется ровно одна замена. Так что сползать невозможно.