Знаменитости
Математики разобрались с гигантскими кубиками Рубика
Наука
30 июня 2011 г. 4:00
Время чтения: 2 минуты

Математики разобрались с гигантскими кубиками Рубика

Математики из Массачусетского технологического университета оценили количество ходов, необходимых для решения кубика Рубика (то есть приведения граней куба к одному цвету) произвольного размера. Препринт их статьи (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). Последний эффект связан с тем, что за одно движение в подобных головоломках можно ставить на нужное место сразу несколько квадратов.

Задача о решении кубика Рубика относится к классу алгоритмических задач реорганизации. Типичным примером такой задачи, встречающимся на практике, является перестановки нужным образом коробок на складе.

Читайте также

16 сентября 2019 г.
Ученые создали из гидрогеля кубик Рубика
21 октября 2019 г.
Россияне назвали Штирлица лучшим кандидатом на пост президента страны
22 октября 2019 г.
Подольская годами обманывала Преснякова, что ей нравится его утренний кофе
20 октября 2017 г.
Знаки зодиака по месяцам и числам
вчера
Чемпионка Паралимпиады Марике Верворт сделала эвтаназию
22 октября 2019 г.
28-летняя дочь посла Ирана Арефех Санаи погибла в Москве — СМИ