Математики разобрались с гигантскими кубиками Рубика
Математики из Массачусетского технологического университета оценили количество ходов, необходимых для решения кубика Рубика (то есть приведения граней куба к одному цвету) произвольного размера. Препринт их статьи (pdf) появился на сайте arXiv.org.
Исследования кубика Рубика математиками начались в начале 80-х годов прошлого века (сама головоломка была создана в 1974 году). Как оказалось, группа симметрий кубика, действующая на множестве его квадратов, довольно сложна и плохо поддается изучению. В 2010 году специалисты по теории игр просчитали на суперкомпьютере все 43 252 003 274 489 856 000 возможных первоначальных позиций для стандартного кубика Рубика (3 на 3 на 3) и установили, что из любого начального положения кубик можно собрать всего за 20 ходов.
В рамках нового исследования ученых интересовала асимптотическая оценка количества движений, необходимых для решения кубика Рубика (хотя, в данном случае, его правильнее было бы называть прямоугольным параллелепипедом) с сторонами произвольной величины. В качестве параметра оценки выступало число n - длина максимальной стороны головоломки, а "асимптотическая" в названии означает, что оценка не точная, но с ростом n оптимальное число ходов растет как оценка.
Исследователям удалось установить, что в общем случае количество ходов есть O(n2) - то есть число необходимых для решения движений куба увеличивается примерно как квадрат n, умноженный на некоторую константу. При этом учеными предложен непосредственный алгоритм решения, который реализует предложенную оценку. В двух частных случаях ученым удалось улучшить этот результат.
Так, оказалось что для "кубического" кубика Рубика, то есть головоломки с размерами n на n на n, и для "веревки" Рубика - головоломки с размерами n на n на 1, оценка выглядит как O(n2/log n). Последний эффект связан с тем, что за одно движение в подобных головоломках можно ставить на нужное место сразу несколько квадратов.
Задача о решении кубика Рубика относится к классу алгоритмических задач реорганизации. Типичным примером такой задачи, встречающимся на практике, является перестановки нужным образом коробок на складе.