Дольше всех распутывается, скорее всего, «зеркало» — кольцо, отражённое через окошко обмена, и на него нужно столько ходов, сколько у шариков пар: n(n−1)/2. Это подтверждают полный перебор до 15 шариков, нейросеть с лучевым поиском до 100 и открытое соревнование до 200 шариков, а доказательства зажимают ответ в узкую вилку.
Ролик: та же история за 11 минут
Статья идёт по сюжету ролика, сцена за сценой, и подробнее его. Под схемами — ссылка на этот момент видео.
Статья: CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs, arXiv 2502.18663, 25 февраля 2025; журнал Advances in Theoretical and Mathematical Physics, 2026. Кольцо, этажи, потолок, компас и фронт — образы для объяснения; в статье это граф Кэли, расстояние, диаметр, нейросеть и лучевой поиск.
Вопрос: кольцо, три хода и самая запутанная расстановка
Возьмём кольцо с шариками, на каждом номер. Как ни перемешай шарики, по порядку их можно вернуть. Вопрос — какую расстановку распутывать дольше всех и сколько на неё нужно ходов.
Три слова понадобятся дальше. Ход — повернуть кольцо влево, повернуть вправо или поменять местами два шарика в окошке наверху. Расстановка — то, как шарики стоят по кругу. Других ходов нет: нельзя взять шарик с середины и переставить, всё делается через окошко.
Слева шарики по порядку, в центре — после поворота влево, справа — после обмена в окошке. ▶ 0:08
Почему вопрос трудный? Распутать любую расстановку несложно: подгоняем нужный шарик к окошку и меняем, пока все не встанут по местам. Но так получается много лишних ходов. Чтобы узнать минимум, нужно сравнить все пути, а расстановок у кольца — 1·2·3·…·n, и это число растёт быстрее любой степени.
Родственную задачу — то же кольцо, но с поворотом только в одну сторону и обменом — поставил кибернетик Виктор Глушков в 1968 году. Она до сих пор открыта.
Статья, авторы и соревнование
Этот вопрос разбирают 34 автора проекта CayleyPy — та же команда, что научила нейросеть собирать кубики Рубика 4×4×4 и 5×5×5.
Статья «CayleyPy RL» — вторая в серии: первая показала метод на кубиках, эта переносит его на графы Кэли общего вида и проверяет на кольце из шариков. В ней сошлись четыре способа ответить на один вопрос: полный перебор маленьких колец, обученная программа для больших, открытое соревнование программистов и строгие доказательства.
34 автора в порядке статьи; имена — как напечатаны в статье.
Kaggle — площадка, где исследователи выкладывают задачи, а команды со всего мира соревнуются в решениях. Авторы открыли там три задачи про это кольцо и выложили свой код, чтобы любой мог его запустить и попробовать обойти.
Башня расстановок: этажи и потолок
Нарисуем все расстановки сразу. Для пяти шариков их 120.
Поставим каждую расстановку на этаж — сколько ходов от неё до порядка по самому короткому пути. Внизу сам порядок, на первом этаже три соседки (по одной на каждый ход), дальше этажи расширяются и снова сужаются. Самый верхний этаж — потолок: за столько ходов распутывается любая расстановка. У пяти шариков потолок — десятый этаж, и на нём ровно одна расстановка.
Ширина полосы — сколько расстановок на этаже; посчитано перебором. ▶ 1:13
Потолок — то же, что число Бога у кубика Рубика: наибольшее число ходов, которое может понадобиться самой короткой сборке. В математике это диаметр графа. Если бы этаж каждой расстановки был известен, распутывать было бы просто: всегда шагать на этаж ниже.
- 1ЭтажСколько ходов от расстановки до порядка по самому короткому пути
- 2ПотолокВерхний этаж: столько ходов хватает на любую расстановку; число Бога, диаметр графа
- 3ВопросКто стоит на потолке и какой он высоты для любого числа шариков
Кто на потолке: зеркало
Авторы сделали перебор: обошли все расстановки колец до 15 шариков. Для 15 это больше триллиона расстановок и несколько дней счёта на кластере.
И каждый раз наверху одна-единственная — зеркало: кольцо, отражённое через окошко. Шарики, стоявшие в окошке, меняются местами, а остальные — парами напротив оси. Неожиданно: если просто поставить шарики задом наперёд, получится расстановка на два этажа ниже.
Слева порядок, в центре зеркало (пунктир — ось через окошко), справа задом наперёд. ▶ 1:52
Длина полосы — число цифр в количестве расстановок. ▶ 1:58
Потолок равен числу пар шариков
Пять шариков соединяются в пары десятью линиями, и потолок у пяти шариков — тоже 10. У шести — 15 пар и потолок 15.
Каждая линия — одна пара шариков. ▶ 2:30
Так совпадает на всех кольцах, где сделали перебор, начиная с четырёх шариков; у трёх шариков потолок 2, а пар 3. Отсюда гипотеза из энциклопедии целочисленных последовательностей (OEIS A186783): потолок всегда равен числу пар, n(n−1)/2.
| Шариков | Пар | Потолок по перебору |
|---|---|---|
| 4 | 6 | 6 |
| 5 | 10 | 10 |
| 6 | 15 | 15 |
| 10 | 45 | 45 |
| 15 | 105 | 105 |
Двадцать шариков: перебор не дотянуть
У 20 шариков расстановок уже 2,4·10¹⁸ — миллиарды миллиардов. Поэтому гипотезу проверяют иначе: берут зеркало и ищут, как распутать его покороче.
Если путь каждый раз выходит не короче числа пар, гипотеза держится. Сначала — классическая программа математиков для вычислений в группах (GAP). Она всегда находит какой-то путь, но не заботится о его длине: на кольце из 20 шариков она думает 41 минуту и выдаёт 217 944 хода. А пар всего 190.
Сверху — число пар, снизу — путь классической программы. ▶ 3:00
Компас из прошлого ролика
Авторы берут тот же приём, что и для кубика Рубика: компас, который учится на случайных прогулках.
Сначала прогулки: от порядка делают случайные ходы и после каждого записывают расстановку и сколько ходов уже сделано. Карта всех расстановок для этого не нужна, а прогулки стоят почти ничего. На таких записях учится компас — нейросеть, которая смотрит на расстановку и угадывает её этаж.
Компас — обычная нейросеть: расстановка на входе, число на выходе.
Угадывает компас с ошибкой: прогулка петляет, и ходов в ней больше, чем на кратчайшем пути. Но чем дальше ушла прогулка, тем в среднем выше этаж, поэтому компас верно показывает направление: где число меньше, там ближе к порядку.
Прогулка из ролика: серая линия — шаг прогулки, синяя — настоящий этаж. ▶ 3:42
Фронт: много расстановок сразу
Ошибки компаса заводят одиночный путь в тупик. Поэтому поиск идёт фронтом — в статье это лучевой поиск.
Фронт — несколько расстановок сразу. На каждом шаге от каждой из них пробуют все три хода, компас оценивает новых соседей, и на следующий шаг остаются только самые многообещающие. Если компас ошибся в одной расстановке, рядом во фронте есть другие, и путь не обрывается.
На 20 шариках так находится путь ровно в 190 ходов — за 3 минуты 48 секунд вместо 41 минуты. До 28 шариков путь совпадает с числом пар, до 44 — находится, но выходит длиннее.
Высота столбика — найденный путь, делённый на число пар; черта — ровно число пар. Таблицы 2–3 статьи. ▶ 4:18
Подсказка в одну строчку
Авторы добавили в поиск одну строчку: не менять шарики в окошке, если они уже стоят по порядку.
Смысл простой: менять уже упорядоченную пару почти никогда не выгодно, а лишний вариант раздувает фронт. Эта строчка отодвинула предел с 40 шариков до 100. Для 100 шариков путь находится за 9 часов, правда, пока он больше чем втрое длиннее числа пар: 16 632 хода при 4 950 парах. И подсказка придумана под это кольцо: для других задач её ещё предстоит найти.
Слева окошко, где обмен запрещён; справа — сколько шариков удаётся распутать. ▶ 4:54
Открытое соревнование
Распутать зеркало авторы предложили всем желающим: открытое соревнование программистов на Kaggle, кольца от 2 до 200 шариков.
Участники дошли до пути длиной ровно в число пар. Короче не нашёл никто — ни программой, ни вручную.
Кольца от 2 до 200 шариков; галочка — путь ровно в число пар. ▶ 5:27
Почему короче не выходит: тройки
Возьмём любую тройку шариков. По кругу они идут либо по часовой стрелке, либо против.
Поворот кольца тройку не переворачивает: все шарики едут вместе, и порядок обхода сохраняется. Перевернуть её может только обмен в окошке, и только если в окошке два шарика из этой тройки. А зеркало переворачивает все тройки сразу. Отсюда авторы доказали: на зеркало нужно почти столько ходов, сколько пар: меньше числа пар — самое большее на половину числа шариков и ещё один ход.
Тройка 1, 2, 4: слева исходная, в центре после поворота, справа после обмена. ▶ 5:51
Вилка: доказанные границы
Сверху потолок зажимает способ распутывания, который придумали авторы: любая расстановка распутывается не дольше, чем за число пар плюс три хода на каждый шарик.
Так получилась вилка. Для 20 шариков потолок лежит между 179 и 250, а гипотеза говорит — 190. Чем больше шариков, тем уже вилка по сравнению с самим потолком: у 100 шариков она занимает несколько процентов от числа пар.
Полоса — доказанные границы, черта — гипотеза. ▶ 6:29
Главное
Вопрос был: какую расстановку распутывать дольше всех и сколько на неё нужно ходов? Скорее всего, зеркало, и ходов на него столько, сколько у шариков пар.
Уже после статьи один из авторов, Григорий Антюфеев, выложил доказательство, что быстрее числа пар зеркало не распутать (arXiv 2601.08715, препринт 2026 года). Открытым осталось одно: нет ли где-то расстановки ещё дальше.
Оговорка. Равенство «потолок = число пар» — гипотеза: доказаны только границы. Нижняя граница ровно в число пар — препринт, рецензенты её ещё не проверяли.
Формально: тот же путь языком статьи
Вторая часть ролика: те же шаги формулами.
| В ролике | В статье | Как устроено |
|---|---|---|
| кольцо со всеми расстановками | граф Кэли LRX симметрической группы Sₙ | вершины — перестановки, рёбра — ходы |
| ходы | образующие L, R, X | L — сдвиг влево, R = L⁻¹, X = (0, 1) — обмен первых двух мест |
| потолок | диаметр графа | гипотеза: n(n−1)/2 при n ≥ 4 |
| зеркало | самый длинный элемент ℓₙ | (1 0 n−1 … 3 2) = R² · (обратный порядок) |
| компас | нейросеть по диффузионному расстоянию + Q-обучение | сначала учится на прогулках, потом сверяется с уравнением Беллмана d(s) = 1 + min d(t) по соседям t |
| фронт | лучевой поиск (beam search) | ширина до 2²⁰; подсказка — X-trick |
| вилка | утверждения 4.2 и 4.3 | n(n−1)/2 − n/2 − 1 ≤ диаметр ≤ n(n−1)/2 + 3n |
Новинка статьи — как учат компас. Прогулки дают первую прикидку, а дальше компас сверяют с соседями: до порядка на один ход больше, чем от ближайшей соседки. Как с дорогой домой: если соседу идти пять минут, тебе — не больше шести. На кольце из 28 шариков это сократило обычный путь с 650 ходов до 402 при 378 парах.
def beam_search(start, model, W, steps=1000):
front = [start]
for _ in range(steps):
nbrs = {m(s) for s in front for m in (L, R, X)
if not (m is X and s[0] < s[1])} # подсказка
if SORTED in nbrs: return True
front = sorted(nbrs, key=model)[:W] # W лучших по компасу
return FalseСхема лучевого поиска с подсказкой; полный код авторы выложили на Kaggle. ▶ 9:46
Где это пригодится
Компасу и фронту не важно, что перед ними кольцо: им нужны только состояния, ходы и цель. Поэтому тот же подход годится для любой задачи, где нужно кратчайшим путём перейти из одного состояния в другое.
| Связь | Где |
|---|---|
| прямо | головоломки «Овальная трасса» (TopSpin) и «Венгерские кольца» устроены почти так же |
| прямо | сети процессоров: диаметр графа связей — самая долгая задержка сообщения |
| прямо | кратчайшие пути в огромных графах перестановок, где перебор невозможен |
| аналогия | планирование: дойти от одного состояния к другому мелкими шагами |
Урок. Перебор даёт гипотезу, обученная программа проверяет её далеко за пределом перебора, а доказательство зажимает ответ в вилку.
Кто и когда, что доказано
- 11968Виктор Глушков: задача о кольце с двумя ходами
- 22011Последовательность для трёх ходов появилась в OEIS (A186783)
- 32020Записана гипотеза: потолок = n(n−1)/2
- 42025Статья CayleyPy RL: 34 автора, ИИ, перебор, соревнование и границы
- 52026Статья в журнале; препринт Антюфеева: нижняя граница ровно в число пар
Доказаны границы n(n−1)/2 − n/2 − 1 ≤ диаметр ≤ n(n−1)/2 + 3n; равенство и единственность зеркала — гипотеза. В тексте статьи есть мелкие расхождения: в аннотации на arXiv нижняя граница записана без «− 1», а в разделе 3.3 вместо таблицы 6 упомянута таблица 8.
Частые вопросы
Схема всех состояний головоломки или группы: каждое состояние — точка, каждый разрешённый ход — линия к соседнему состоянию. Для кольца с шариками это все расстановки и три хода между ними.
Наибольшее число ходов, которое может понадобиться самому короткому пути между двумя состояниями. У кубика Рубика его называют числом Бога: 20 ходов, если пол-оборота считать одним ходом.
По гипотезе — n(n−1)/2, числу пар шариков, начиная с четырёх шариков. Это проверено перебором до 15 шариков; доказано, что ответ лежит между n(n−1)/2 − n/2 − 1 и n(n−1)/2 + 3n.
Нет, полностью — нет. В 2026 году один из авторов выложил доказательство нижней границы ровно в число пар, но это препринт; верхняя граница пока на 3 хода на шарик выше.
Нейросеть-компас учится на случайных прогулках угадывать расстояние до цели, а лучевой поиск держит сразу много лучших по её оценке состояний, чтобы одна ошибка не заводила в тупик.
Да: код авторов открыт и запускается бесплатно на Kaggle, библиотека CayleyPy лежит на GitHub (ссылки ниже).