=====ММ13=====

**Конкурсная задача ММ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 призовых баллов. 
----