Question

9. В стране есть несколько городов. Сумасшедший путешественник едет из города А в самый далёкий от него город B. Затем едет в самый далёкий от в город Си т.д. Докажите, что если город С не совпадает с городом А, то путешественник никогда не вернётся обратно в город А. 10 Масошо

Answer 1

Предположим, что на втором шаге путешественник не возвратился в А, т.е. город С отличен от города А. Тогда маршрут от А до B короче маршрута из B в С (поскольку С — наиболее удаленный от B город). В дальнейшем каждый следующий маршрут будет не короче предыдущего, так как каждый раз мы в качестве следующего пункта назначения выбираем наиболее удаленный город. Пусть на некотором шаге путешетвенник все же вернулся в город А, выйдя из некоторого города Х. По доказанному, маршрут от Х до А длиннее маршрута от А до B, а это противоречит тому, что B — наиболее удаленный от А город.

Answer 2

Давайте докажем данное утверждение.

Пусть у нас есть n городов, и путешественник начинает свое путешествие в городе A. По условию, он всегда едет в самый далекий от текущего местоположения город.

Предположим, что путешественник вернется обратно в город A. Это означает, что он посетит все остальные города перед тем, как вернуться в A.

Обозначим города в порядке, в котором их посетит путешественник: A, X1, X2, ..., Xk, B, Y1, Y2, ..., Ym, C, Z1, Z2, ..., Zp, ...

Где:

• X1, X2, ..., Xk - города, которые он посетит на пути к B (k может быть равно 0, если B сразу самый далекий от A).
• B - самый далекий от A город.
• Y1, Y2, ..., Ym - города, которые он посетит на пути к C (m может быть равно 0, если C сразу самый далекий от B).
• C - самый далекий от B город.
• Z1, Z2, ..., Zp - города, которые он посетит после C (p может быть равно 0, если C сразу самый далекий от B).

Теперь давайте рассмотрим, какой город будет самым далеким от C. Это будет один из городов, которые он посетит после C, то есть Z1, Z2, ..., Zp.

Теперь давайте предположим, что он вернется обратно в город A после посещения всех городов, включая Z1, Z2, ..., Zp. Это означает, что A снова станет самым далеким от текущего местоположения.

Однако мы знаем, что город Z1, Z2, ..., Zp был выбран как самый далекий от C. Это означает, что A не может быть самым далеким городом от текущего местоположения, так как Z1, Z2, ..., Zp находятся дальше от C, чем A.

Таким образом, предположение о том, что путешественник вернется обратно в город A, невозможно. Путешественник будет двигаться только вперед и не вернется обратно в A, если город C не совпадает с городом A.