Решение задачи 309

Условие:

Путешественник выходит из своего родного города и отправляется в самый дальний от него город страны, затем — в город, самый дальний от этого города, и так далее. Расстояния между всеми городами различны. Докажите, что если путешественник не вернулся в родной город после второго перехода, то он никогда в него не вернётся.

Решение:

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

Пусть длина этого цикла равна n, n>2.

Пусть a_k -- самое длинное ребро в цикле, оно соединяет вершины k и k+1. Но тогда из вершины k+1 путешественник должен был пойти в вершину k, а не в вершину k+2, противоречие.