|
|
 |
Условие
В стране некоторые пары городов соединены дорогами, которые не пересекаются вне городов. В каждом городе установлена табличка, на которой указана минимальная длина маршрута, выходящего из этого города и проходящего по всем остальным городам страны (маршрут может проходить по некоторым городам больше одного раза и не обязан возвращаться в исходный город). Докажите, что любые два числа на табличках отличаются не более чем в полтора раза.
Решение
Рассмотрим самый короткий маршрут l, проходящий по всем городам. Пусть он начинается в городе A, заканчивается в городе B, а его длина равна N. Тогда числа на табличках в городах A и B равны N, а все остальные не меньше N. Пусть C – один из оставшихся городов. Он лежит на данном маршруте, поэтому длина пути от C до одного из городов A или B не больше N/2 (без ограничения общности – до A).
Рассмотрим маршрут, который выходит из C, доходит кратчайшим образом до A, а затем повторяет маршрут l. Он проходит через все города, и его длина не превосходит
N/2 + N = 3N/2. Следовательно, число на табличке в городе C не больше 3N/2.
Таким образом, все числа на табличках принадлежат отрезку [N, 3N/2], откуда и следует требуемое.
