KSTATIE.com | КСТАТИ

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

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

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

lenta.ru

Leave a Reply

*

НА ЗАМЕТКУ

  • “Разнообразие и сбалансированность питания: чем больше разных продуктов включено в рацион, тем больше физиологически активных веществ поступает в организм.”
  • “Повышенная чувствительность груди. Если вы беременны, то через неделю-две скоррее всего заметите, что грудь стала более чувствительной. Кроме этого, может появиться ощущение, что грудь несколько \"раздулась\".”
  • “Избегайте холодных напитков и холодной еды: они мешают пищеварению. Это всё равно равно, что лить ледяную воду на огонь. По крайней мере эффект в желудочно-кишечном тракте получается похожий.”
  • “Рыбу, пахнущую тиной, необходимо вымыть в крепком холодном растворе соли.”
  • “Снижайте потребление сахара, старайтесь меньше использовать его при приготовлении пищи, используйте заменители сахара и диабетические сладости.”
  • “Грязное белье храните в сухом, проветриваемом месте. Не стоит надолго откладывать стирку - кожные жиры и остатки косметики при длительном хранении разрушительно воздействуют на ткань.”
  • “Старайтесь готовить с минимальным применением жира; где это возможно варите или жарьте на шампуре (с помощью гриля), но не жарьте в масле, это добавляет более 100 калорий каждому блюду. Если уж приходится жарить, то сначала растопите масло в горячей сковородке прежде чем класть туда ингредиенты (пища быстрее впитывает холодное масло).”
  • “Горчица, разведенная на молоке вместо воды, значительно лучше сохраняется, не сохнет.”
  • “Принимайте витаминно-минеральные комплексы, экстракты лекарственных растений (с учетом своих индивидуальных особенностей). Практикуйте психическое и физическое расслабление (аутотренинг, йога, дыхательная гимнастика). Научитесь не гневаться.”
  • “Старайтесь не досаливать пищу, соль способствует задержке жидкости в организме;”
  • “Чтобы печенье в духовке не пригорело, под формы надо сыпать немного соли.”
  • “Масло в жаркую погоду не тает, если маслёнку обернуть салфеткой, смоченной в солёной воде.”
Log in |