По какому алгоритму рассчитывается количество возможных состояний кубика Рубика N * N?
GD Star Rating
loading...
Количество возможных состояний кубика Рубика,
loading...
Обсуждения в блоге
- ДОБРО ПОЖАЛОВАТЬ В НАУКУ!
- блогерс, кто может дать радиометр погонять на денёк?
- про IR лазеры теперь, чтоб те долго жили.
- Не уверен, что чисто алгебраические задачи будут тут уместны, но всё же.
- Швейцарские и грузинские археологи обнаружили в ходе раскопок человеческий череп, который доказывает, что уже 1,8 миллиона лет назад все люди, живущие на земле, принадлежали к одному и тому же виду приматов —
- Суббота.
- Господа, у меня своеобразный вопрос.
- Пару недель назад мы с каналом «Наука 2.
- Друзья, объясните мне пожалуйста, чем отличается альфа частица 3.
- Байты и биты.
Ну давай посчитаем. Будем делать так, разберем кубик на детали и посмотрим сколькими способами его можно собрать обратно.
Пусть N четное.
Кубик NxNxN состоит из:
1) 8 угловых подкубиков, каждый из которых встает на одно из 8 мест одним из 3х способов.
2) Реберные подкубики. Они бывают (N–2)/2 типов (по расстоянию от угла). Каждого типа имеется 2*12 кубиков, каждый из которых встает на одно из 2*12 мест одним из 2–х способов.
3) Остальные («граневые») подкубики. Они бывают (N–2)*(N–2)/4 типов (по положению от угла).
Каждого типа имеется 6*4 кубиков, каждый из которых встает на одно из 6*4 мест одним способом.
Итого имеем (8!*3*(24!*2)^((N–2)/2)*(24!)^((N–2)(N–2)/4)) способов собрать сломанный кубик.
Теперь возникает вопрос, как пространство «собранных» кубиков делится на связные компоненты касательно операций с кубиком (другими словами, если я соберу кубик по кусочкам случайным образом, смогу ли я потом вращая его привести его к «правильной раскраске»). Детский опыт с кубиком 3х3х3 подсказывает что связных компонент две, поэтому собрав кубик из кусочков случайным образом ты лишь в половине случаев получишь конфигурацию, из которой можно вернуться к «правильной раскраске». Кубик 4*4*4 мне менее понятен. С одной стороны, его как будто можно всегда собрать. С другой стороны, у него по раскраске невозможно отличить две конфигурации, различающиеся лишь перестановкой двух соседних реберных подкубиков. Для простоты предположим что у любого кубика рубика всегда две связные компоненты.
Тогда получаем ответ (8!*3*(24!*2)^((N–2)/2)*(24!)^((N–2)(N–2)/4))/2
Дальше можно его уменьшать разными способами. Например, как я заметил, можно не учитывать конфигурации, которые визуально не различаются (например, перестановки граневых подкубиков одного цвета на одной грани, и т.п.).
Еще можно пытаться посчитать с учетом изоморфизма относительно поворотов и отражений, для этого есть одна клевая теорема, но там будет чуть другой ход вычислений, и я не уверен что все легко получится.
мне кажется гигантское количество комбинаций кубика это маркетинговый ход. Реально — гораздо меньше. Ведь не все комбинации допустсимы, если разобрать, а потом произвольно собрать.
Если не ошибаюсь, кубик гарантировано собирается максимум за 15–20 манипуляций. Если посмотреть ролики, где кубик собирают роботы, то это порядка 10 манипуляций.
Повторюсь, что для кубика 3х3х3, если разобрать а потом произвольно собрать, то с вероятностью 1/2 выйдет «легальная сборка» (т.е. пространство конфигураций имеет две связных компоненты). Известно что он собирается максимум за 26 ходов (см сюда, третий слайд).
Кстати если проделать подсчет для кубика 3*3*3 по приведенной выше логике [кстати, у меня там забыто возведение в степень в паре мест], получается
(8!*(3^8)*12!*(2^12)),
что будет ровно в 12 раз больше, нежели число на слайде у Эделькампа. Значит либо связных компонент таки 12 (причем 6 из них не отличимы по раскраске от «правильной сборки»), либо я что–то где–то пересчитал, либо мне в дестве очень везло с собиранием кубика.
Зацените между прочим, какая у меня штука есть:
скажи мне, есть смысл брать 7х7х7, если 4х4х4 и 5х5х5 уже освоены? Есть ли там над чем поломать голову?
Интересен ли будет Мегаминкс, не знаешь? Что–то другое?
Не знаю, этот 7х7х7 не мой, надо будет скоро отдать, и я его «путать» не решаюсь ибо дико пугает осознание того, что даже если бы одним поворотом я проставлял бы по одному кубику в правильное место, на обратную сборку ушло бы 218 поворотов, а посвятить несколько часов–суток–недель механическому кручению кубика я сейчас не готов. (У меня и на 5х5х5–то всего однажды терпения хватило, а у 4х4х4 я так и не разобрался как уголки менять если они не сойдутся).
Но как средство для того чтобы окончательно и бесповородно доказать себе что ты таки освоил алгоритм сбора кубика NxNxN, как клевый гэджет друзей попугать или нервно покрутить в руках от нечего делать — он клев. Мегаминкс не пробовал, но тут дело вкуса же. Если тебе такие штуки нравятся — наверняка и этот понравится, даже если окажется что ты его на раз–два–три собирать умеешь 🙂