Количество фигур из змейки Рубика

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Количество фигур из змейки Рубика

Сообщение peregoudov » 28 авг 2020, 22:55

Сын крутил змейку Рубика и задал вопрос: а сколько всего фигур можно из нее сложить?

Навскидку: 24 звена, каждое можно 4 способами ориентировать по отношению к предыдущему, всего $4^{23}=2^{46}$ комбинаций. Оценка, конечно, очень завышена, скорее всего, большинство этих комбинаций нереализуемо (звенья должны были бы наложиться друг на друга). Но вот хороших идей уменьшить это число нет...

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Количество фигур из змейки Рубика

Сообщение Ian » 31 авг 2020, 11:10

Любая собранная фигура представляет собой приложенные друг к другу несколько полных кубиков и несколько полукубиков (6 типов полукубиков), в сумме 12 полных кубиков. Реализуемрость ее змейкой проверяется быстро. Устраивается некоторое блуждание по кубикам пространства, каждому из которых присвоен один из 8 типов -тип 0 -кубик пространства не занят,1...6 типы полукубиков, тип 7-полный кубик. При входе в полукубик дольнейший путь однозначен и определяется его типом, а тип пройденного полукубика обратить в 0 При входе в полный кубик развилка на 3 варианта разбиения на полукубики, каждый раз уход из него однозначен, а тип оставшегося полукубика с 7 изменить на известный. Невозможность продолжать путь -проверить продолжение в обратную сторону и если не набирается 23 хода забраковать.
Наиболее сложный расчет для параллелепипеда 2х2х3 , там до 12 тройных развилок в переборе, но и тогда перебор реализуем [math] случаев. В результате для каждой объемной фигуры получим инструкцию по сборке. если она возможна.
Вот тут https://www.youtube.com/watch?v=PCN4X5Z ... e=youtu.be люди рекламируют 100 фигур, конечно, их намного больше, просто не все имеют аналог из жизни. Так или иначе, способы, приводящие к одной и той же объемной фигуре, надо считать одинаковыми. И оценить число объемных фигур , с присвоенными однозначно типами кубиков, а по числу типов 7 -среднее количество способов реализации. Хотя, по правде, фигуры совмещаемые поворотом пространства, тоже стоило бы считать одинаковыми.
В то же время я кажется, могу построить [math] разных несамопересекающихся цепочек (про "большинство"), но это же неинтересные фигуры, ни один из кубиков пространства не имеет типа 7.

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Количество фигур из змейки Рубика

Сообщение peregoudov » 31 авг 2020, 13:27

Так я не понял, какой-то ответ у вас есть? Или только "рассуждения мысли"?

Скажем, в английской википедии написано, что два чувака сосчитали количество фигур компьютерным перебором и оно получилось примерно в 7 раз меньше, чем моя примитивная оценка. Вы вот какой-то множитель такого типа обосновать можете?

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Количество фигур из змейки Рубика

Сообщение Ian » 31 авг 2020, 17:52

Логарифм числа комбинаций оценен с ошибкой менее 50%.
Жаль, что вы алгоритм реализуемости не стали читать, это как раз заинтересовало меня

peregoudov
Сообщений: 620
Зарегистрирован: 29 дек 2015, 13:17

Количество фигур из змейки Рубика

Сообщение peregoudov » 31 авг 2020, 18:53

Я все прочитал, только ничего не понял. "Алгоритм реализуемости" у меня и свой есть:

У каждого звена есть две квадратных грани и одна прямоугольная. Будем следить за центрами прямоугольных граней и соединяющими их отрезками. Эта ломаная имеет ряд очевидных свойств:
1) соседние звенья перпендикулярны;
2) если два последовательных звена соединяют узлы кубической пространственной сетки, то и все остальные звенья соединяют ее узлы;
3) звенья не могут накладываться друг на друга;
4) наложение вершин возможно, только если все отходящие звенья лежат в одной плоскости.

То есть получается некая задача подсчета количества путей на графе.

Только как это превратить в оценку --- я не понимаю.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 13 гостей