В некоторой стране 275 городов, из которых 25 — областные центры. Некоторые города...

Question

В некоторой стране 275 городов, из которых 25 — областные центры. Некоторые города соединены между собой дорогами (но не более чем одной для каждой пары городов), причем любой путь по дорогам между двумя обычными городами, если он есть, проходит хотя бы через один областной центр. Какое наибольшее количество дорог могло быть в этой стране?

Answer 1

Фраза, что любой путь по дорогам между обычными городами, проходит через областной центр, говорит о том, что два любых не областных города не связаны между собой дорогой. То есть любая дорога из не областного города ведет в областной город.
Максимальное число таких дорог будет тогда, когда каждый областной город будет связан с любым обычным.
Областных городов 25. Обычных - 275-25=250. Число пар "областной город" - "обычный город" равно 25*250=6250.
Между областными городами также есть дороги. Максимальное число дорог будет в том случае, если каждый областной город будет связан со всеми остальными. Таких дорог будет 25*24/2=25*12=300.
Т.о., всего дорог в стране будет 6250+300=6550.

Ответ: 6550 дорог