Рассмотрим все возможные комбинации из трех цифр от 1 до 3, начиная от 111 и кончая 333. Всего таких 3*3*3=27. Сделаем из них 27 вершин графа и проведем стрелки от каждой вершины к трем следующим после нее по каждой из 3 координат. Например, из 112 можно "пойти" в 212 (увеличили первую координату), 122 (вторую), 113 (третью). После 3 всегда возвращаемся к 1, так что из 113, например, можно пойти в 213, 123 или 111.
Мы получили граф из 27 вершин и 27*3=81 ребер между ними. Он показан на картинке ниже (не обращайте внимания на цвета ребер пока что). Горизонтальные ребра, соединяющие по первой координате, надо представлять как уходящие вправо и возвращающиеся слева: например, в первой строке 111 -> 211 -> 311 -> 111. Эти возвращения не нарисованы, чтобы визуально разгрузить картинку. В этом графе есть много циклов, например только что написанный. Вопрос в том, какие есть в нем гамильтоновы циклы, т.е. проходящие через каждую вершину 1 раз. Длина такого цикла 27, по числу вершин. Найти гамильтонов цикл легко, но сложнее - хотя тоже возможно - найти три таких цикла, которые все используют разные ребра, и таким образом в них входят все 27*3=81 ребер графа.
Такое разбиение показано на картинке: три цикла выкрашены в три разных цвета. Я также нарисовал отдельно три графа, в каждом из которых один из циклов выделен, так что можно проследить глазами, как он путешествует сквозь все 27 вершин.
Таких разбиений, разных, есть много: сотни. Это не задача, которую решил ИИ. Это Кнут сделал сам; то, надо чем он работал, это как такое решение обобщить на любое количество цифр, не только от 1 до 3. Для любого числа m > 2 мы можем построить граф из m^3 вершин, в каждой записана тройка чисел от 1 до m; ребра как описано выше, их 3*m^3; и вопрос в том, как разбить этот граф на 3 гамильтоновых цикла.
Для m=3 легко найти решение и даже много решений перебором (не совсем наивным, но близко к тому). Для больших m это не работает; надо придумать подход, формулу (в первый цикл входят (i,j,k) с такими-то свойствами; во второй с такими-то итд.). Логично, чтобы суть формулы была одна для разных m; но есть разные довольно красивые и симметричные разбиения для m=3, которые не работают при попытке обобщить для больших m.
После многих попыток в разные стороны, которые не удавались, Клод смог найти формулу, которая эмпирически работала для всех нечетных m от 3 до 101, и Кнут позже доказал, что она работает для всех нечетных m. Еще пару дней спустя другие энтузиасты нашли также решение для всех четных m > 3, тоже с помощью LLM. Задача теперь полностью решена.
