|
||||||||||||||||||||||||||||||||||||||
|
СодержаниеММ158Задача ММ158 предложена Олегом Полубасовым Конкурсная задача ММ158 (ТГ-4) (7 баллов)
I. Города занумерованы от 1 до N. Дорога, непосредственно соединяющая города i и j, существует, если и только если |i-j| - простое число. Длина дороги равна |i-j|.
Найти зависимость длины кратчайшего гамильтонова цикла от величины N. Решение
Решение:
I. При малых N кратчайший гамильтонов цикл находим прямым перебором:
Для четных N «защелка» выглядит аналогично.
Докажем теперь, что этот гамильтонов путь минимален. II. Длина гамильтонова пути a1-a2-a3-…-aN-1-aN-a1 в таком графе равна (a1+a2) + (a2+a3) + … + (aN-1+aN) + (aN+a1) = 2( 1 + 2 + … N-1 + N) = N(N+1). Обсуждение Обсуждение Легко видеть, что в пункте II граф получается двудольным (смежные вершины могут быть только разной четности). Поскольку при нечетных N число вершин в долях получается разным, гамильтонова цикла в этом случае быть не может. При четных N > 2 гамильтоновы циклы для малых значений N легко строятся. Поскольку с ростом N число гпмильтоновых циклов лавинообразно возрастает, очевидно (хотя и не доказано строго никем из участников ), что гамильтоновы циклы есть при всех четных N > 2. Можно показать, что в пункте I при N > 9 для четных N в кратчайшем гамильтоновом цикле реализуется только схема обхода (1), а для нечетных - схема обхода (2). Поэтому при N > 9 кратчайший гамильтонов цикл определен однозначно. Таким образом, случай N = 9 является особенным. Только для него существует два различных кратчайших гамильтоновых цикла. Алексей Волошин задался вопросом о нахождении не кратчайших, а наоборот длиннейших гамильтоновых циклов для пункта (1). Очевидно, что эта длина не превосходит [N2/2] - длины наибольшего гамильтонова цикла в полном графе, в котором длина ребра из i в j равна |j-i| (см. A007590 в OEIS). При 4 < N < 12 эта оценка точна. Однако, при N = 12 наибольшая длина гамильтонова цикла в графе из I равна 70, а не 72. Сергей Половинкин рассмотрел графы, возникающие при комбинировании условий пунктов I и II: дорога из i в j существует, i+j - просто, но ее длина равна |j-i|. Вот таблица зависимости длины кратчайшего гамильтонова цикла от N для этого типа графов.
Бросается в глаза отсутствие монотонности. Общую формулу Сергею получить не удалось. Награды За правильное решение и некоторое обобщение задачи ММ158 Алексей Волошин и Сергей Половинкин получают по 8 призовых баллов. За верное решение задачи Виктор Филимоненков и Анатолий Казмерчук получают по 7 призовых баллов. Николай Дерюгин (допустивший ошибку для случая N=8) получает 6 призовых баллов. Автор задачи Олег Полубасов получает 7 призовых баллов. Эстетическая оценка задачи - 4.9 балла. Разбор задачи ММ158 подготовил Владимир Лецко
|
|||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||
|