Комбинаторика: интересная задача :-)

Сколько всего различных состояний у кубика Рубика N x N ?

 

что, посчитать сложно?

на самом деле, просто. сама сложность - в обосновании метода расчета. приведу пример для N=3(только рассуждение). считай и обобщай сам (мне лень).

предположим, что все "квадратики" кубика Рубика 3*3 занумерованы номерами от 1 до ? (кстати, сколько "квадратиков")?

зафиксируем какое-нибудь состояние кубика Рубика. зададимся вопросом: сколько граней достаточно зафиксировать, чтобы нельзя было изменить состояние кубика Рубика? ответ - 2.



З.Ы. кстати, если найдешь ошибку - молодец.

 

Ну дык в комбинаторике так и бывает

1. Интуиция подсказывает что обобщение будет разным для четных и нечетных N.

2. Две грани зафиксировать не достаточно, если они противолежащие. И нумерация тут не катит, потому что нас не интересует взаимное расположение квадратиков одного цвета. Говоря языком комбинаротики, размещения тут не канают, юзать надо сочетания.

 

Можно попробовать оценить сверху.



Очень грубая оценка:



6 цветов, 6 граней. -> 6 * N * N клеточек. Каждая имеет 6 состояний. Следовательно первая грубая оценка сверху 6 ^ (6 * N * N).



Оценка поближе. По сочетаниям.

П(i = 1 to 6)(A(i * N * N, N * N))

 

Еже одна оценка сверху, возможно еще точнее. По всевозможным поворотам.



3 * 3 * (3!) * (2 ^ N) = 54 * (2 ^ N)



[EDIT]: Нет, это полная лажа

 

у кубика есть принципиально различные элементы

ну жно учесть состояние каждого , которое не ваш взгляд является различным

например будет ли поворот центрального квадрата плоскости считаться его различным положением ?

задача весьма сложная

 

Кое-что про кубик Рубика есть в книжке Applied Abstract Algebra, D. Joyner, R. Kreminski, J. Turisco. Книга неплохая, особенно для начинающих. В электронном виде свободно доступна на сайте авторов (http://web.usna.navy.mil/~wdj/book/book.html).

 

если брать боле-менее реальный кубик рубик 3*3, то за счёт поворота угловых кубиков, получается 3^8 комбинаций, а за счёт их перестановки (8!). В сумме за счёт углов получится (8!)*3^8 комбинаций. А за счет двух-цвЕтных кубиков (лежащих на рёбрах, между угловми кубиками, их тоже 8) 8!*2^8. Середины плокостей кубика-рубика местами менятся не могут - они ничего не дают.



итого (8!)*(3^8)*(8!)*(2^8)



Но это не учитывая что новые состояния кубика-рубика достигаются не повротами его "пластов", а сбором-разбором (без отклеивания/приклеивания приклеенных к каждому кубику идентификаторов цвета) составляющих его "кубиков".



Но если кубик NxN, то даже теряюсь как считать.

 

letopisec

Точнее, NxNxN. А если он при этом еще и N-мерный? ))

 

>Точнее, NxNxN. А если он при этом еще и N-мерный? ))



То это уже не кубик, и уж точно не рубик. Например сколько у такого кубика рёбер, плоскостей?



Вообще перестановок в кубике NxN посчитать легко: (N*N*6)!

Вот как учесть что два переставленных например красных квадратика не дают нового состояния? Или как учесть что если отправить один красный квадратик на жёлтую сторону, а другой на зелёную, и если при этом на жёлтой и зелёной стороне поменять местами эти два красных квадратика, то это не принесёт нового состояния? Вот это уже посложнее будет.

 

число состояний для кубика 3*3*3 = 43 252 003 274 489 865 000 Считайте, господа

 

R_NEW



И как это получается?

 

насколько я помню возможные положения кубика 3х3х3, сосчитать количество состояний можно так:

1. положение центральных фиксируем. Их повороты нам безразличны.

2. размещение угловых - их 8 штук, сверху ограничено 8!, но любое из этих положений сводится либо к правильному, либо к такому, в котором 2 соседних угловых переставлены местами. Значит только половина из 8! вариантов верна.

3. Повороты угловых. Всего 3**8. Причем любой расклад сводится к правильному, либо к такому, у которого один кубик перекручен на треть, либо на две трети. Следовательно только треть из этих вариантов реальна.

т.е. имеем 3**7.

4. размещения кубиков на сторонах. Всего 12 шт. Аналогично пункту 2 - только половина из 12! вариантов реальна, другая половина невозможна.

5. повороты этих кубиков. Всего 2**12, но половина нереальна.



Ничего не забыл?

Итого:

8!/2 * 3**8/3 * 12!/2 * 2**12/2 =

20160 * 2187 * 239500800 * 2048 =

21 626 001 637 244 928 000

это чуть больше 2в64.



Почему-то у меня в 2 раза меньше получилось, чем у R_NEW...



R_NEW

откуда цифра?

 

_DEN_

Хрен знает. Я нашёл только готовое значение.

Solo

Не поверите: детская книга "Я познаю мир" ) Но не думаю, чтобы они ошиблись...

 

Число состояний (а точнее число элементов в группе вращений) кубика Рубика равно 43252003274489856000

Подробности см. по ссылке: Analyzing Rubik's Cube with GAP.

 

А! Понял! видимо, во втором и в четвертом пункте я повторно исключил одни и те же варианты. Тогда мой результат нужно умножить на 2 и получим 43252003274489856000, что и является правильным решением...



R_NEW

все-таки ошибся - 4 и 5 знаки местами перепутал

 

согрешил

 

_DEN_

грани надо брать прилежащие

кстати говоря, в материале по ссылке тов. RElf, тоже используется нумерование "квадратиков"

 

slow

А я и не говорил, что так решить не возможно. Просто мне кажется это не совсем рациональный подход.

 

ну извини, за 2 минуты проще найти не вышло