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