Учеными математиками Массачусетского технологического университета было рассчитано количество решений кубика Рубика или приведение граней куба к одному цвету.

Исследования интереснейшего логического кубика Рубика проводятся учеными всего мира еще с начала 80-х годов прошлого века, сама же головоломка была изобретена в 1974 году. Оказывается группа симметрий кубика, которая основана на множестве квадратов различного цвета, весьма сложна и плохо поддается изучению. В 2010 году эксперты по теории игр подсчитали количество первоначальных позиций для стандартного кубика Рубика (3 на 3 на 3) на суперкомпьютере и получили цифру 43 252 003 274 489 856 000. При этом также стало известно, что из любого начального положения кубик можно собрать всего лишь за 20 ходов.

В рамках данного исследования ученых в первую очередь интересовала асимптотическая оценка количества движений, которые нужно произвести для решения кубика Рубика, хотя ученые говорят, что было правильнее называть его прямоугольным параллелепипедом со сторонами произвольной величины. В качестве основного параметра расчетов брали число n - длину максимальной стороны головоломки, а "асимптотическая" в названии означает, что оценка эта приблизительная, но с ростом n оптимальное число ходов увеличивается.

Ученые смогли установить, что при общем случае количество ходов есть O(n2), что означает,что число движений, которые нужно произвести необходимых для решения куба увеличивается примерно как квадрат n, умноженный на некоторую константу. При этом математики предположили, что данный алгоритм решения, реализует предложенную оценку.

Всего лишь в двух случаях ученым удалось оптимизировать данный результат. Оказывается, что для "кубического" кубика Рубика, то есть головоломки с размерами n на n на n, и для "веревки" Рубика - головоломки с размерами n на n на 1, оценка выглядит как O(n2/log n). Последний эффект предполагает, что за одно движение в таких головоломках можно ставить на необходимое место сразу несколько цветных квадратов.

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