В некотором государстве города соединены дорогами. Длина любой дороги меньше 500 км и из любого города в любой другой можно попасть, проехав по дорогам менее 500 км. Когда одну дорогу закрыли на ремонт, выяснилось, что из любого города можно проехать в любой другой по оставшимся дорогам. Докажите, что это можно сделать, проехав не более 1500 км.
Будем обозначать города буквами $A$, $B$, $C$, $D$, $\ldots$. Прежде всего заметим, что:
если какой-то путь $A$—$\ldots$—$B$—$\ldots$—$C$—$\ldots$ — кратчайший между городами $A$ и $C$, то часть его, например, от $A$ до $B$ — кратчайший путь между соответствующими городами;
кратчайший путь не проходит по одной дороге дважды.
Допустим теперь, что закрыли дорогу, соединяющую города $A$ и $B$; обозначим её через $AB$. Поделим все города на две группы: к первой группе отнесём город $A$ и те города, кратчайший путь из которых в город $A$ не проходил по дороге $AB$, а ко второй — все остальные. Нужно считать, что город $B$ окажется во второй группе — иначе во второй группе не будет вообще ни одного города; ведь если $AB$ — не кратчайший путь из $A$ и $B$, то ни один из кратчайших путей не может проходить по дороге $AB$, т. е. дорога $AB$ тогда — бесполезная.
Пусть $M$ и $N$ — города, кратчайший путь между которыми составляет теперь больше 500 км. Значит, раньше кратчайший путь между $M$ и $N$ проходил по дороге $AB$. Но тогда кратчайший путь в город $A$ из одного из этих городов проходил по дороге $AB$, а из другого — нет (см. замечание в начале решения); следовательно, города $M$ и $N$ принадлежат разным группам. Рассуждая от противного, получаем, что любые два города, принадлежащие одной и той же группе, могут быть соединены путём длины меньше 500 км.
Рис. 1Рис. 2
Поскольку из города $A$ по-прежнему можно проехать в город $B$, то найдутся два города $C$ и $D$ такие, что $C$ принадлежит первой группе, а $D$ — второй, и город $C$ соединён дорогой с $D$. Теперь понятно, как из любого города $M$ первой группы попасть в любой город $N$ второй группы, проехав меньше 1500 км: нужно из $M$ поехать вначале в город $C$ (этот путь меньше 500 км, так как $M$ и $C$ принадлежат одной и той же группе), затем — из $C$ в $D$ (длина дороги $CD$ меньше 500 км по условию), и, наконец, из города $D$ — в город $N$ (города $D$ и $N$ — из одной группы, поэтому путь из $D$ в $N$ снова меньше 500 км) — см. рисунок 1.
Оценку 1500 км нельзя улучшить. Действительно, если четыре города $A$, $B$, $C$ и $D$ расположены так, как показано на рисунке 2 ($ABCD$ — трапеция такая, что при продолжении её боковых сторон получается равносторонний треугольник), то, закрыв дорогу $AB$, получим, что длина кратчайшего пути между $A$ и $B$ равна $(500+2a)~\text{км}$, где $a$ можно сделать сколь угодно близким к 500.
