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

*

НА ЗАМЕТКУ

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