Филимоненков Виктор (fiviol) wrote,
Филимоненков Виктор
fiviol

Category:

n-мерный Кубик Рубика

Попытка написания популярного текста по математике.


Кубик Рубика 2*2*2
Начнем с упрощенного варианта стандартного кубика Рубика. При вращении его граней будем смотреть только на то, как переставляются 8 угловых кубиков, не обращая внимания на все остальные. То есть будем рассматривать, по сути, кубик 2*2*2, любые две параллельные грани которого можно поворачивать на 90 градусов друг относительно друга.
Еще одно упрощение: не будем интересоваться, как грани угловых кубиков повернуты относительно граней всего куба. Наклеим, например, на все видимые грани каждого угловых кубиков квадратики одинакового цвета - для каждого угла свой цвет. Или просто перенумеруем угловые кубики числами 0, 1, 2, 3, 4, 5, 6, 7.
Цель головоломки: вращением граней кубика относительно друг друга добиться некоего исходного положения угловых кубиков друг относительно друга.

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

Разберем эту упрощенную задачу.
Положение углов друг относительно друга не изменится, если мы будем его крутить и перемещать в пространстве целиком, не меняя положение граней друг относительно друга. Поэтому фиксируем его положение так, чтобы угол 0 всегда был на левой нижней задней грани (по отношению к нашему взгляду). Тогда при вращении граней будут перемещаться только углы 1-7. Всего есть шесть основных поворотов граней друг относительно друга, которые мы будем называть ходами:
Поворот верхней грани относительно нижней по часовой стрелке или против часовой стрелки; обозначим эти ходы A и A-1 соответственно.
Поворот передней грани относительно задней по часовой стрелке или против часовой стрелки; обозначим эти ходы Б и Б-1 соответственно.
Поворот правой грани относительно левой по часовой стрелке или против часовой стрелки; обозначим эти ходы В и В-1 соответственно.

Пусть в исходном положении на нижней грани были углы 0, 1, 2, 3 (допустим, по часовой стрелке, глядя сверху), а на верхней грани на ними соответственно 4, 5, 6, 7. Все ходы являются перестановками из элементов 1-7, при которых по 3 элемента остаются на месте, а четыре образуют цикл. Обозначим ходы:
А = (4 5 6 7) (то есть 4 становится на место 5, 5 на место 6, 6 на место 7, 7 на место 4);
A-1 = (7 6 5 4);
Б = (7 6 2 3);
Б-1 = (3 2 6 7);
В = (6 5 1 2);
В-1 = (2 1 5 6).

При последовательном произведении ходов получается перестановка чисел 1-7, называемая произведением перестановок, задаваемых отдельными ходами. Это произведение обладает некоторыми стандартными свойствами операции умножения, в частности, есть единичная перестановка (когда каждый элемент остается на месте, обозначим эту перестановку Е), которая при умножении на что угодно не меняет перестановки: Е*Х = Х*Е для любой перестановки Х. Очевидно также, что
A*A-1 = A-1*А = Е (так как вращение в обратную сторону все расставляет на прежние места; то же самое для Б и B).
A*A*A*A = Б*Б*Б*Б = В*В*В*В = Е.
С другой стороны, это произведение не обладает переместительным законом, так как порядок вращения граней важен: А*Б не равно Б*А.

Цель игры теперь можно переформулировать так: найти последовательность ходов, произведение которых дает нам произвольную перестановку из 7 элементов.
Цель игры (в отличии, например, от не менее известной игры в «пятнашки»), достижима: любую перестановку углов можно получить.
Возникает нетривиальная задача:

Задача. За сколько ходов из исходной позиции наверняка можно получить произвольную позицию.

Для стандартного кубика 3*3*3 аналогичная задача очень сложна, и, насколько я понимаю, текущий ответ таков: не больше 26 (могу ошибаться). Для нашей упрощенной головоломки ответ получается гораздо проще, например, простым перебором, так как есть всего 7! = 5040 перестановок из 7 элементов. Правда, я не в состоянии провести и такой перебор, а простого решения, основанного на теории перестановок, не вижу. Так что для меня эта проблема открыта. Предполагаю, что за 6-8 ходов любая перестановка может быть получена. Хорошо бы иметь и простой алгоритм, который по заданной перестановке указывал наименьшую цепочку ходов, приводящую к нужной перестановке.

Представление кубика Рубика в виде карты Карно.
Рассмотрим плоскую головоломку, равносильную описанному выше кубику 2*2*2, используя так называемые карты Карно. Расположим числа 0-7 в виде прямоугольной таблицы 2*4:
4567
0123

Эту таблицу стоит рассматривать как цилиндр: левая и правая ее границы считаются одним и тем же!
Граням кубика мы сопоставим прямоугольники этой таблицы, имеющие по 4 клеточки: то есть грани образуют четверки [4, 5, 6, 7], [0, 1, 2, 3] (четырехугольники 4*1), а также [0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6], [3, 0, 7, 4] (четырехугольники 2*2).
Ходам, то есть вращениям граней друг относительно друга будут тогда соответствовать циклические перестановки элементов в четырехугольниках не содержащих элемент 0 (этот элемент всегда остается в нижнем левом углу таблицы, за что и выделен черным).
Вот как изменяется исходная таблица при каждом из ходов:
А:
7456
0123

А-1:
5674
0123

(клетки верхнего ряда сдвигается влево и вправо)
Б:
4573
0162

Б-1:
4526
0137

(клетки четырехугольника, составленного из двух последних столбцов, поворачиваются по часовой и против часовой стрелки)
В:
4627
0513

В-1:
4157
0263

(клетки четырехугольника, составленного из 2 и 3 столбцов, поворачиваются по и против часовой стрелки).

Задача сстоит в том, чтобы с помощью последовательности таких операций нужно получить нужную перестановку чисел 1-7 в таблице.

Обобщение: кубик 2^n.
В таком виде можно представить себе и многомерный аналог кубика, и аналог вращения многомерных параллельных граней друг относительно друга. Ниже в терминах карт Карно я сформулирую задачу для четырехмерного куба (для больших размерностей задача также формулируется, но требует дополнительных рассуждений).

Но сначала заметим, что и тут случай трехмерного кубика не является самым простым. Можно сформулировать задачу для квадрата (правда, эта задача оказывается уже почти тривиальной).
В таблице 2*2 расставлены числа:
Е:
23
01

Разрешается делать ходы:
А:
32
01

(менять местами клетки в верхнем ряду)
Б:
21
03

(поменять элементы в последнем столбце).
Сколько нужно сделать ходов, чтобы из исходной получить любую перестановку элементов 1, 2, 3 в этой таблице?
Всего перестановок из трех элементов 3! = 6 штук. Три из них уже получены: Исходная перестановка, получаемая за 0 ходов, и перестановки, получаемые ходами А и Б (за 1 ход).
Рассмотрим, какие перестановки можно получить за 2 хода.
A*A = Е - исходная перестановка.
Б*Б = Е - исходная перестановка.
А*Б = (меняем элементы в верхней строке, а потом в правом столбце):
31
02

Б*А = (меняем элементы в правом столбце, а потом в верхней строке):
12
03

Осталась последняя перестановка:
13
02

которая может быть получена за 3 хода, например, А*Б*А или Б*А*Б.
Таким образом, для «кубика» 2*2, (то есть при n = 2) ответ на задачу, аналогичную для сформулированной выше для случая n = 3, равен трем ходам.

Перейдем к четырехмерному кубику. 16 вершин его занумеруем и расположим в виде таблицы 4*4:
12131415
891011
4567
0123

В этой таблице верхняя и нижняя граница, так же как и левая и правая, нужно рассматривать как одинаковые (если их «склеить», то получится ТОР)!
Вращениям трехмерных граней этого кубика друг относительно друга соответствуют циклические перестановки клеток в прямоугольниках карты, состоящих из 8 клеточек, (и не содержащих клетки 0). Таких прямоугольников 4 (они состоят соответственно из 1 и 2, строк, из 2 и 3 строк, из 2 и 3 столбца, из 3 и 4 столбца).
Значит, у нас есть 8 элементарных ходов (каждый из 4 прямоугольников можно повернуть по часовой или против часовой клетки). Каждый ход представляет собой циклическую перестановку восьми элементов из пятнадцати 1-15.
Задача остается прежней: за сколько ходов наверняка можно получить произвольную перестановку из 15 элементов?
Tags: Игры, Математика, НиЖ
Subscribe

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments