Сын крутил змейку Рубика и задал вопрос: а сколько всего фигур можно из нее сложить?
Навскидку: 24 звена, каждое можно 4 способами ориентировать по отношению к предыдущему, всего комбинаций. Оценка, конечно, очень завышена, скорее всего, большинство этих комбинаций нереализуемо (звенья должны были бы наложиться друг на друга). Но вот хороших идей уменьшить это число нет...
Количество фигур из змейки Рубика
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Количество фигур из змейки Рубика
Любая собранная фигура представляет собой приложенные друг к другу несколько полных кубиков и несколько полукубиков (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.
Наиболее сложный расчет для параллелепипеда 2х2х3 , там до 12 тройных развилок в переборе, но и тогда перебор реализуем [math] случаев. В результате для каждой объемной фигуры получим инструкцию по сборке. если она возможна.
Вот тут https://www.youtube.com/watch?v=PCN4X5Z ... e=youtu.be люди рекламируют 100 фигур, конечно, их намного больше, просто не все имеют аналог из жизни. Так или иначе, способы, приводящие к одной и той же объемной фигуре, надо считать одинаковыми. И оценить число объемных фигур , с присвоенными однозначно типами кубиков, а по числу типов 7 -среднее количество способов реализации. Хотя, по правде, фигуры совмещаемые поворотом пространства, тоже стоило бы считать одинаковыми.
В то же время я кажется, могу построить [math] разных несамопересекающихся цепочек (про "большинство"), но это же неинтересные фигуры, ни один из кубиков пространства не имеет типа 7.
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Количество фигур из змейки Рубика
Так я не понял, какой-то ответ у вас есть? Или только "рассуждения мысли"?
Скажем, в английской википедии написано, что два чувака сосчитали количество фигур компьютерным перебором и оно получилось примерно в 7 раз меньше, чем моя примитивная оценка. Вы вот какой-то множитель такого типа обосновать можете?
Скажем, в английской википедии написано, что два чувака сосчитали количество фигур компьютерным перебором и оно получилось примерно в 7 раз меньше, чем моя примитивная оценка. Вы вот какой-то множитель такого типа обосновать можете?
Количество фигур из змейки Рубика
Логарифм числа комбинаций оценен с ошибкой менее 50%.
Жаль, что вы алгоритм реализуемости не стали читать, это как раз заинтересовало меня
Жаль, что вы алгоритм реализуемости не стали читать, это как раз заинтересовало меня
-
- Сообщений: 620
- Зарегистрирован: 29 дек 2015, 13:17
Количество фигур из змейки Рубика
Я все прочитал, только ничего не понял. "Алгоритм реализуемости" у меня и свой есть:
У каждого звена есть две квадратных грани и одна прямоугольная. Будем следить за центрами прямоугольных граней и соединяющими их отрезками. Эта ломаная имеет ряд очевидных свойств:
1) соседние звенья перпендикулярны;
2) если два последовательных звена соединяют узлы кубической пространственной сетки, то и все остальные звенья соединяют ее узлы;
3) звенья не могут накладываться друг на друга;
4) наложение вершин возможно, только если все отходящие звенья лежат в одной плоскости.
То есть получается некая задача подсчета количества путей на графе.
Только как это превратить в оценку --- я не понимаю.
У каждого звена есть две квадратных грани и одна прямоугольная. Будем следить за центрами прямоугольных граней и соединяющими их отрезками. Эта ломаная имеет ряд очевидных свойств:
1) соседние звенья перпендикулярны;
2) если два последовательных звена соединяют узлы кубической пространственной сетки, то и все остальные звенья соединяют ее узлы;
3) звенья не могут накладываться друг на друга;
4) наложение вершин возможно, только если все отходящие звенья лежат в одной плоскости.
То есть получается некая задача подсчета количества путей на графе.
Только как это превратить в оценку --- я не понимаю.
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 5 гостей