===== ММ158 =====

Задача ММ158 предложена Олегом Полубасовым 

**Конкурсная задача ММ158 (ТГ-4)** (7 баллов)

I. Города занумерованы от 1 до N. Дорога, непосредственно соединяющая города i и j, существует, если и только если |i-j| - простое число. Длина дороги равна |i-j|.
Найти зависимость длины кратчайшего гамильтонова цикла от величины N.\\
II. Заменим в I |i-j| нат i+j. 
Найти зависимость длины кратчайшего гамильтонова цикла от величины N, при условии, что полученный граф гамильтонов. 

**Решение**

Решение:
I. При малых N кратчайший гамильтонов цикл находим прямым перебором:\\
При N < 5 гамильтоновых циклов нет.\\
При N = 5  минимальным будет цикл 1-3-5-2-4-1, длина 12 (цикл единственен с точностью до направления обхода). \\
При N = 6  минимальным будет цикл 1-3-5-2-4-6-1, длина 16 (цикл единственен с точностью до направления обхода). \\
При N = 7 минимальным будет цикл 1-3-5-7-2-4-6-1, длина 20 (цикл единственен с точностью до направления обхода).  \\
При N = 8 минимальным будет цикл 1-3-6-8-5-7-2-4-1, длина 22 (цикл единственен с точностью до направления обхода).  \\
При N = 9 минимальным будет цикл 1-3-8-6-9-7-5-2-4-1 или 1-3-5-8-6-9-7-2-4-1, длина 24 (минимальных циклов ровно два, с точностью до направления обхода). \\
При N > 9 построим цикл длины  следующим способом:\\ 

{{:marathon:mm158.jpg|:marathon:mm158.jpg}}

Для четных N "защелка" выглядит аналогично.\\

Докажем теперь, что этот гамильтонов путь минимален.\\
а) Длина пути от вершины i до вершины j не меньше |j-i|, при этом равенство достигается тогда и только тогда, когда в пути номера вершин строго монотонны, это следует из неравенства треугольника.
б) Длина пути из 1 в 2 не меньше 5, при этом равенство достигается только в случае пути 1-4-2. Доказательство очевидно - напрямую из 1 в 2 попасть нельзя, следовательно в пути не меньше двух ребер, длиной не менее 2.  Но два ребра длины 2 не меняют четность вершин, следовательно длина по крайней мере одного ребра не меньше 3.
в) Аналогично, длина пути из N в N-1 не меньше 5, при этом равенство достигается только в случае пути N - (N-3) - (N-1).
В гамильтоновом цикле есть три возможных порядка обхода вершин с номерами 1, 2, N-1, N (с точностью до направления обхода):
1. 1 - 2 - (N-1) - N. При этом длина пути не меньше 2N+6.  (1)\\
2. 1 - 2 - N - (N-1). При этом длина пути не меньше 2N+6.  (2)\\
3. 1 - N - 2 - (N-1). При этом длина пути не меньше 4N-8.  (3)\\
При N > 9 путь в (3) заведомо длиннее: 4N-8 > 2N+6.

II. Длина гамильтонова пути a<sub>1</sub>-a<sub>2</sub>-a<sub>3</sub>-...-a<sub>N-1</sub>-a<sub>N</sub>-a<sub>1</sub> в таком графе равна (a<sub>1</sub>+a<sub>2</sub>) + (a<sub>2</sub>+a<sub>3</sub>) + ... + (a<sub>N-1</sub>+a<sub>N</sub>) + (a<sub>N</sub>+a<sub>1</sub>) = 2( 1 + 2 + ... N-1 + N) = N(N+1).


**Обсуждение**

Обсуждение

Легко видеть, что в пункте II граф получается двудольным (смежные вершины могут быть только разной четности). Поскольку при нечетных N число вершин в долях получается разным, гамильтонова цикла в этом случае быть не может.
При четных N > 2 гамильтоновы циклы для малых значений N легко строятся. Поскольку с ростом N число гпмильтоновых циклов лавинообразно возрастает, очевидно (хотя и не доказано строго никем из участников :-D), что гамильтоновы циклы есть при всех четных N > 2.

Можно показать, что в пункте I при N > 9 для четных N в кратчайшем гамильтоновом цикле реализуется только схема обхода (1), а для нечетных - схема обхода (2). Поэтому при N > 9 кратчайший гамильтонов цикл определен однозначно. Таким образом, случай N = 9 является особенным. Только для него существует два различных кратчайших гамильтоновых цикла.

Алексей Волошин задался вопросом о нахождении не кратчайших, а наоборот длиннейших гамильтоновых циклов для пункта (1).
Очевидно, что эта длина не превосходит [N<sup>2</sup>/2] - длины наибольшего гамильтонова цикла в полном графе, в котором длина ребра из i в j равна |j-i| (см. A007590 в OEIS).
При 4 < N < 12 эта оценка точна. Однако, при N = 12 наибольшая длина гамильтонова цикла в графе из I равна 70, а не 72.

Сергей Половинкин рассмотрел графы, возникающие при комбинировании условий пунктов I и II: дорога из i в j существует, i+j - просто, но ее длина равна |j-i|.
Вот таблица зависимости длины кратчайшего гамильтонова цикла от N для этого типа графов.

^N^d(N)^
|4|6|
|6|14|
|8|18|
|10|20|
|12|28|
|14|48|
|16|40|
|18|52|
|20|58|

Бросается в глаза отсутствие монотонности. Общую формулу Сергею получить не удалось.

**Награды**

За правильное решение и некоторое обобщение задачи ММ158 Алексей Волошин и Сергей Половинкин получают по 8 призовых баллов. За верное решение задачи Виктор Филимоненков и Анатолий Казмерчук получают по 7 призовых баллов. Николай Дерюгин (допустивший ошибку для случая N=8) получает 6 призовых баллов. Автор задачи Олег Полубасов получает 7 призовых баллов.

**Эстетическая оценка задачи - 4.9 балла.**

//Разбор задачи ММ158 подготовил Владимир Лецко//


----