50 БАЛЛОВ! В государстве 10 городов, некоторые пары которых соединены беспосадочными...

Question

50 БАЛЛОВ!
В государстве 10 городов, некоторые пары которых соединены
беспосадочными авиалиниями так, что из любого города можно долететь
до любого другого (возможно, с пересадками). Расстоянием между
городами А и Б назовем минимальное количество перелётов, за которое
можно долететь из А в Б. Министерство транспорта открыло новую
авиалинию между двумя городами, расстояние между которыми до этого
было наибольшим. Может ли после этого расстояние между некоторыми
двумя городами оказаться большим 5?

Answer 1

Нет, не может. Если все города соединены между собой их можно выстроить цепочкой (или будет несколько более коротких цепей). После этого мы соединяем два конца этой цепи. Это два самых удаленных города - один в начале цепи, другой в конце.) Теперь по цепи можно двигаться в по кольцу в прямом и обратном направлении. Тогда если в прямом направлении будет больше 5 городов, то в обратном направлении будет меньше пяти городов. Если цепей две или более, то замыкается самая длинная цепь, а короткая цепь будет из пяти или менее пяти городов (т.к. всего городов 10.)