|
|
 |
Условие
В некотором государстве города соединены дорогами. Длина каждой дороги меньше 500 км, и из каждого города в любой другой можно попасть, проехав по дорогам меньше 500 км. Когда одна дорога оказалась закрытой на ремонт, выяснилось, что из каждого города можно проехать по оставшимся дорогам в любой другой. Доказать, что при этом можно проехать меньше 1500 км.
Решение
Заметим, что:
1) если какой-то путь A – ... – B – ... – C – кратчайший между городами A и C, то часть его, например, от A до B – кратчайший путь между соответствующими городами;
2) кратчайший путь не проходит по одной дороге дважды.
Допустим, что закрыли дорогу, соединяющую города A и B; обозначим её через AB. Поделим все города на две группы: к первой группе отнесём город A и те города, кратчайший путь из которых в город A не проходил по дороге AB, а ко второй – все остальные. Можно считать, что город B оказался во второй группе (иначе во второй группе не будет вообще ни одного города: ведь если AB – не кратчайший путь из A в B, то ни один из кратчайших путей не может проходить по дороге AB).
Пусть M и N – города, кратчайший путь между которыми составляет теперь больше 500 км. Значит, раньше кратчайший путь между M и N проходил по дороге AB. Но тогда кратчайший путь в город A из одного из этих городов проходил по дороге AB, а из другого – нет (см. выше); следовательно, города M и N принадлежат разным группам. Отсюда следует, что любые два города, принадлежащие одной группе, могут быть соединены путём длины меньше 500 км.
Поскольку из города A по-прежнему можно проехать в город B, то найдутся такие города C и D, что C принадлежит первой группе, а D – второй, и город C соединен дорогой с D. Теперь понятно, как из любого города M первой группы попасть в любой город N второй группы, проехав меньше 1500 км: нужно из M поехать вначале в город C (этот путь меньше 500 км), затем – из C в D (длина дороги CD меньше 500 км), и, наконец, из города D – в город N (путь из D в N снова меньше 500 км).
