Конкурсная задача ММ13 (8 баллов)

(Эта задачка была предложена Ольгой Рукосуевой в конференции RU.Golovolomka. Но не вызвала особого интереса. На мой взгляд, зря.)

Для каких натуральных n можно расставить числа 1,2,…n по окружности так, чтобы абсолютная величина разности соседних чисел равнялась 3, 4 или 5.

Решение

Достаточно легко проверяется что для n<7 требуемая расстановка невозможна.
При n=7 имеем: 1-5-2-6-3-7-4;
При n=8: 1-5-8-3-6-2-7-4;
При n=9: 1-4-8-3-7-2-6-9-5;
Заметим, что левые соседи максимальных чисел и 'последние' числа в цепочках не отличаются от максимальных на 5 (это пригодится нам в дальнейшем). При n из диапазона [10..13] расстановка невозможна. Этот факт несложно установить компьютерным перебором, но можно обойтись и без оного.

Рассмотрим, например, 'ручное' доказательство для n=10.
Ясно, что наша задача сводится к доказательству отсутствия гамильтонова цикла в графе, которой задается списками смежности вершин так:
1) 4,5,6;
2) 5,6,7;
3) 6,7,8;
4) 1,7,8,9;
5) 1,2,8,9,10;
6) 1,2,3,9,10;
7) 2,3,4,10;
8) 3,4,5;
9) 4,5,6;
10) 5,6,7.
Если гамильтонов цикл есть, то вершины из множества {1,4,5,6,9} должны располагаться в нем подряд (это следует из того, что вершины 1 и 9 имеют один и тот же набор смежных вершин). К этой пятерке должны примыкать вершины, 2, 8 и 10 (каждая из них смежна лишь одной вершине не из этой пятерки), что, разумеется, невозможно.

Для n=19 и n=20 подходящие расстановки существуют. Таковыми являются, например:
1-4-7-3-8-11-16-19-15-10-13-18-14-17-12-9-6-2-5 и
1-4-7-3-8-11-14-10-13-18-15-19-16-20-17-12-9-6-2-5.

Остальные натуральные числа представимы в виде суммы некоторого количества семерок, восьмерок и девяток. Существование требуемой расстановки для таких чисел следует из возможности 'склеивания' ранее полученных расстановок.

Покажем как это делается на примере n=22.
Сначала получим расстановку для n=14. Для этого возьмем два экземрляра цикла 1-5-2-6-3-7-4. Превый 'разрежем' между 3 и 7. А во втором увеличим все числа на 7 и вставим в разрез:
1-5-2-6-3–8-12-9-13-10-14-11–7-4.
Полученный цикл вновь разрежем возле максимальными числа и вставим в разез числа цикла для n=8, увеличенные на 14:
1-5-2-6-3-8-12-9-13-10–15-19-22-18-21-16-20-17–14-11-7-4.

Таким образом, требуемая расстановка возможна для всех натуральных n, за исключением n из множества {1,2,3,4,5,6,10,11,12,13}.

Награды

За правильное (но несколько тяжеловесное) решение этой задачи Борис Бух получает 7 призовых баллов.