В некоторой стране 275 городов, из которых 25 — областные центры. Некоторые города соединены между собой дорогами (но не более чем одной для каждой пары городов), причем любой путь по дорогам между двумя обычными городами, если он есть, проходит хотя бы через один областной центр. Какое наибольшее количество дорог могло быть в этой стране?
More Questions From This User See All
Answers & Comments
Максимальное число таких дорог будет тогда, когда каждый областной город будет связан с любым обычным.
Областных городов 25. Обычных - 275-25=250. Число пар "областной город" - "обычный город" равно 25*250=6250.
Между областными городами также есть дороги. Максимальное число дорог будет в том случае, если каждый областной город будет связан со всеми остальными. Таких дорог будет 25*24/2=25*12=300.
Т.о., всего дорог в стране будет 6250+300=6550.
Ответ: 6550 дорог