⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀Решение:
⠀
1️⃣ Рассмотрим число 1. Рядом с ним могут стоять только 2 и 3, потому что разность должна быть 1 или 2.

2️⃣ Теперь рассмотрим число 2. Поскольку с одной стороны рядом с ним уже стоит 1, а число 3 стоит с другой стороны от 1, то рядом с 2 вторым числом можно поставить только 4.

3️⃣ Если продолжать рассуждать так далее, то приходим к тому, что числа одинаковой чётности будут соседними с разностью 2, то есть все числа разбиваются на цепочки 1 − 3 − 5 − 7 − 9 − 11 и 2 − 4 − 6 − 8 − 10 − 12.

4️⃣ Чтобы получить единый цикл, эти две «цепочки» надо соединить на концах. В результате возможна, с точностью до обращения (по часовой стрелке или против неё), фактически одна запись: 1, 2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3 или обратная ей.

⠀⠀Тык на цитату, если хотите
⠀⠀более строгих объяснений...
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀👉
⠀
Построим граф G на вершинах 1, 2, …, 12, где вершины i и j соединены ребром, если |i − j| = 1 или |i − j| = 2. Такой граф называется квадратом пути — рёбра исходного пути 1 − 2 − … − 12 плюс «перескоки» через одну вершину.

Задача «расставить числа по кругу так, чтобы соседи отличались на 1 или 2» — это в точности задача нахождения гамильтонова цикла в графе G: цикла, проходящего через каждую вершину ровно один раз и использующего только рёбра графа.

Основной приём решения — стандартная техника поиска гамильтоновых циклов через вынужденные рёбра:

▶️Вершина 1 в графе G имеет степень 2 (соединена только с 2 и 3). В гамильтоновом цикле у каждой вершины ровно два соседа — значит, оба ребра при вершине 1 обязаны войти в цикл. То же самое верно для вершины 12 (соединена только с 10 и 11).

▶️Это «вынуждает» выбор у соседних вершин (например, у вершины 2 одно место уже занято числом 1, и единственный оставшийся вариант — 4), и цепочка вынужденных выборов распространяется дальше.

Если убрать из G рёбра «разности 1» и оставить только рёбра «разности 2», граф распадается на два непересекающихся пути: 1 − 3 − 5 − 7 − 9 − 11 и 2 − 4 − 6 − 8 − 10 − 12. «Вынужденный» анализ показывает, что почти все рёбра цикла — это рёбра «разности 2» внутри этих путей, а рёбра «разности 1» используются лишь как редкие «мостики», соединяющие концы этих двух цепочек в единый цикл. По сути это означает, что G имеет (с точностью до симметрии — поворота и отражения круга) ровно один гамильтонов цикл — довольно редкое и красивое свойство для графа с таким количеством рёбер.

*️⃣В общем же случае подсчёт числа гамильтоновых циклов — NP-трудная задача. Но для графов специального вида (как квадраты путей или квадраты циклов) их можно перечислить явно — это довольно классический сюжет в комбинаторике.

При этом приём «вершина малой степени ⟹ оба её ребра входят в цикл» — рабочий инструмент не только в занимательных или олимпиадных задачках, но и в алгоритмах точного поиска гамильтоновых циклов, например в эвристиках для знаменитой задачи коммивояжёра.