Поддержать TUT.BY
68 дней за решеткой. Катерина Борисевич
Коронавирус: свежие цифры
  1. «Как будто хотят сделать процедуру сложнее». Ковалкин — о грядущих изменениях по обращениям
  2. «Выживали — по-другому и не скажешь». Каково сейчас на Окрестина, где не принимают передачи
  3. Прокурор запросил пять лет за тяжкие телесные повреждения милиционера. Обвиняемый 12 дней был в реанимации
  4. Долги давят на баланс. БМЗ ждет новую порцию поддержки от государства
  5. Песков — о дворце в Геленджике: Кремль не имеет права разглашать
  6. Предложения по Конституции: Утверждать результаты президентских выборов будет Всебелорусское собрание
  7. Экс-студента БГУИР судят за частичный срыв занятий. Кажется, преподаватели не согласны с тем, что «срыв» был
  8. «Скучно, девочки». Путин прокомментировал расследование ФБК о дворце в Геленджике
  9. Врач Никита Соловей больше не главный инфекционист Минска
  10. У Комитета госконтроля новый «старый» руководитель
  11. Собрали протестные флаги районов Минска в одну карту. Полюбуйтесь на этот креатив
  12. «Службой был доволен, не жаловался». Что известно о погибшем в части в Островце 18-летнем срочнике
  13. «Шатать и раскачивать нас будут». Лукашенко назначил нового госсекретаря Совбеза
  14. Четыре спальни, гостиная и терраса. Проект каркасного дома на 108 «квадратов» со сметой
  15. За сутки в стране всего 847 случаев COVID-19 — в два раза меньше, чем в воскресенье
  16. Задержанные на акциях в поддержку Навального — о нарушении прав, отношении полиции и своей мотивации
  17. Экс-студента БГУИР, которому суд дал 114 суток ареста за марши, внезапно отпустили с Окрестина
  18. Видеофакт. В Минске замечена бронемашина — ранее ее не удавалось опознать
  19. «Люди спрашивали, как мы живем». История семьи с незрячими родителями и здоровым малышом
  20. «В весе 115 кг я перестала выходить из дома». История девушки, похудевшей на 55 килограммов
  21. Кадровый вторник, представители МВД в суде, Ян Солонович на свободе. Что происходит 26 января
  22. Смотрите, что творится на дорогах Гродненщины, которую накрыл циклон «Ларс»
  23. Активно протестовавший «Гродно Азот» доверили бывшему вице-премьеру Ляшенко
  24. Лукашенко чиновникам про биометрические паспорта: Даже двойки нельзя вам поставить по защите персональных данных
  25. «Людей лишают «плюшек». Официальные профсоюзы придумали, как удержать работников и «наказать» тех, кто вышел
  26. Тайна, которую хранили 30 лет. Белоруска узнала, что мать всю жизнь скрывала: она ей не родная
  27. Топ-баскетболистка Беларуси не верит, что в стране все останется как есть. И вот почему
  28. Узнали, какая ситуация с краудфандинговыми площадками, основатель которых — Эдуард Бабарико
  29. У кого было больше шансов найти работу в кризисный 2020 год? Вы удивитесь, но это не «айтишники»
  30. И ездить не стыдно, и налог платить не надо. Подборка крутых автомобилей старше 1991 года выпуска


Фото пользователя Hellbus с сайта wikipedia.org
Фото пользователя Hellbus с сайта wikipedia.org
Математики из Массачусетского технологического университета оценили количество ходов, необходимых для решения кубика Рубика (то есть приведения граней куба к одному цвету) произвольного размера. Препринт их статьи (
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). Последний эффект связан с тем, что за одно движение в подобных головоломках можно ставить на нужное место сразу несколько квадратов.
Задача о решении кубика Рубика относится к классу алгоритмических задач реорганизации. Типичным примером такой задачи, встречающимся на практике, является перестановка нужным образом коробок на складе.
-23%
-30%
-15%
-10%
-25%
-50%
-35%
-20%
-50%