30 июня 2011, 16:44

Кубик Рубика можно собрать за 20 ходов, — решили ученые

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

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

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

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

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

Последний эффект связан с тем, что за одно движение в подобных головоломках можно ставить на нужное место сразу несколько квадратов.