Информатика и ИИ · эксперимент
Укроти гигантский кубик
Кубики шириной в сотни слоёв, константа 10⁴⁰, сортирующие сети. Четыре вопроса, от начального уровня до продвинутого, о новой оценке для гигантских кубиков Рубика.
1 · Сформулируй, что доказано
Начальный
Что статья доказывает для больших кубиков n×n×n?
2 · Найди константу
Лемма 5: универсальная последовательность из L этапов даёт старшую константу L/2. Лучшая последовательность статьи насчитывает 61 этап, отсюда 30,5.
Средний
Какую константу даёт последовательность permnet72 из 72 этапов?
3 · Найди, откуда взялось 10⁴⁰
Доказательство 2011 года опиралось на компьютерную проверку: 24 перестановки порождают любую чётную расстановку семейства из 24 деталей.
Продвинутый
Почему его константа выросла примерно до 10⁴⁰?
4 · Примени оценку к одному кубику
Оценка из статьи: 30,5 n²/lg n + o(n²/lg n) ходов.
Продвинутый
Может ли она дать точное число ходов, которого хватит для кубика шириной в 1000 слоёв?
Кубик укрощён
—