========= 158 ========== ММ158 (ТГ-4) (7 баллов)
I. Города занумерованы от 1 до N. Дорога, непосредственно соединяющая города i и j, существует, если и только если
![$|i-j|$ $|i-j|$](https://dxdy-02.korotkov.co.uk/f/9/5/c/95cff71cbdadc292ece04ca083f654cb82.png)
- простое число. Длина дороги равна
![$|i-j|$ $|i-j|$](https://dxdy-02.korotkov.co.uk/f/9/5/c/95cff71cbdadc292ece04ca083f654cb82.png)
.
Найти зависимость длины кратчайшего гамильтонова цикла от величины N.
II. Заменим в I
![$|i-j|$ $|i-j|$](https://dxdy-02.korotkov.co.uk/f/9/5/c/95cff71cbdadc292ece04ca083f654cb82.png)
нат
![$i+j$ $i+j$](https://dxdy-02.korotkov.co.uk/f/9/d/9/9d95bc12c0590e2aa9cea1b95166891982.png)
.
Найти зависимость длины кратчайшего гамильтонова цикла от величины 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 построим цикл длины следующим способом:
![Изображение](http://img-fotki.yandex.ru/get/6102/26550112.b/0_62794_730a99bd_L.jpg)
На картинке приведен цикл для нечетного N. Для четных 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_1-a_2-a_3-\dots-a_{N-1}-a_N-a_1$ $a_1-a_2-a_3-\dots-a_{N-1}-a_N-a_1$](https://dxdy-01.korotkov.co.uk/f/0/b/0/0b03905a08582f266ea1f4217eb1469e82.png)
в таком графе равна
![$(a_1+a_2) + (a_2+a_3) + \dots + (a_{N-1}+a_N) + (a_N+a_1) = 2( 1 + 2 + \dots + N-1 + N) = N(N+1).$ $(a_1+a_2) + (a_2+a_3) + \dots + (a_{N-1}+a_N) + (a_N+a_1) = 2( 1 + 2 + \dots + N-1 + N) = N(N+1).$](https://dxdy-01.korotkov.co.uk/f/c/f/6/cf6d8755bbed5c8e4f7618b167e0315f82.png)
Ответ:
I.
При N < 5 гамильтонова цикла нет;
при N = 5 длина кратчайшего гамильтонова цикла равна 12;
при N = 6 длина кратчайшего гамильтонова цикла равна 16;
при N > 6 длина кратчайшего гамильтонова цикла равна 2N+6;
II.
Если гамильтонов цикл существует, его длина равна N(N+1).
ОбсуждениеЛегко видеть, что в пункте II граф получется двудольным (смежные вершины могут быть только разной четности). Поскольку при нечетных N число вершин в долях получается разным, гамильтонова цикла в этом случае быть не может.
При четных N > 2 гамильтоновы циклы для малых значений N легко строятся. Поскольку с ростом N число гпмильтоновых циклов лавинообразно возрастает, очевидно (хотя и не доказано строго никем из участников
![Smile :-)](./images/smilies/icon_smile.gif)
), что гамильтоновы циклы есть при всех четных N > 2.
Можно показать, что в пункте I при N > 9 для четных N в кратчайшем гамильтоновом цикле реализуется только схема обхода (1), а для нечетных - схема обхода (2). Поэтому при N > 9 кратчайший гамильтонов цикл определен однозначно. Таким образом, случай N = 9 является особенным. Только для него существует два различных кратчайших гамильтоновых цикла.
Алексей Волошин задался вопросом о нахождении не кратчайших, а наоборот длиннейших гамильтоновых циклов для пункта (1).
Очевидно, что эта длина не превосходит
![$\left{\lfloor{N^2}2\rfloor$ $\left{\lfloor{N^2}2\rfloor$](https://dxdy-02.korotkov.co.uk/f/5/1/0/510901052438a0e7595423318cf9cc7682.png)
- длины наибольшего гамильтонова цикла в полном графе, в котором длина ребра из i в j равна
![$|j-i|$ $|j-i|$](https://dxdy-02.korotkov.co.uk/f/d/f/7/df7221ed6bf37a1dd34c61027164a6f582.png)
(см. A007590 в OEIS).
При 4 < N < 12 эта оценка точна. Однако, при N = 12 наибольшая длина гамильтонова цикла в графе из I равна 70, а не 72.
Сергей Половинкин рассмотрел графы, возникающие при комбинировании условий пунктов I и II: дорога из i в j существует, i+j - просто, но ее длина равна
![$|j-i|$ $|j-i|$](https://dxdy-02.korotkov.co.uk/f/d/f/7/df7221ed6bf37a1dd34c61027164a6f582.png)
.
Вот таблица зависимости длины кратчайшего гамильтонова цикла от N для этого типа графов.
![$$\displaystyle \begin{array}{|c|c|}
\hline
N & d(N) \\
\hline
4 & 6 \\
6 & 14 \\
8 & 18 \\
10 & 20 \\
12 & 28 \\
14 & 48 \\
16 & 40 \\
18 & 52 \\
20 & 58 \\
\hline
\end{array}$$ $$\displaystyle \begin{array}{|c|c|}
\hline
N & d(N) \\
\hline
4 & 6 \\
6 & 14 \\
8 & 18 \\
10 & 20 \\
12 & 28 \\
14 & 48 \\
16 & 40 \\
18 & 52 \\
20 & 58 \\
\hline
\end{array}$$](https://dxdy-04.korotkov.co.uk/f/7/3/2/732b57531182cfc66d92a8ab5417585482.png)
Бросается в глаза отсутствие монотонности. Общую формулу Сергею получить не удалось.
НаградыЗа правильное решение и некоторое обобщение задачи ММ158 Алексей Волошин и Сергей Половинкин получают по 8 призовых баллов. За верное решение задачи Виктор Филимоненков и Анатолий Казмерчук получают по 7 призовых баллов. Николай Дерюгин (допустивший ошибку для случая N=8) получает 6 призовых баллов. Автор задачи Олег Полубасов получает 7 призовых баллов.
Эстетическая оценка задачи - 4.9 балла.Разбор задачи ММ158 подготовил Владимир Лецко