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