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