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

*

НА ЗАМЕТКУ

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