Условие
В стране несколько городов, попарные расстояния между которыми различны.
Путешественник отправился из города А в самый удаленный от него город Б,
оттуда - в самый удаленный от него город С и т.д. Докажите, что
если С не совпадает с А, то путешественник никогда не вернется в А.
Подсказка
Каждое следующее путешествие не короче предыдущего.
Решение
Предположим, что на втором шаге путешественник не возвратился в А,
т.е. город С отличен от города А.
Тогда маршрут от А до Б короче маршрута из Б в С
(поскольку С - наиболее удаленный от Б город).
В дальнейшем каждый следующий маршрут будет не короче предыдущего,
так как каждый раз мы в качестве следующего пункта назначения выбираем
наиболее удаленный город.
Пусть на некотором шаге путешетвенник все же вернулся в город А, выйдя из
некоторого города Х. По доказанному, маршрут от Х до А длиннее
маршрута от А до Б, а это противоречит тому, что Б - наиболее удаленный от А
город.
Источники и прецеденты использования
