Внекоторой стране 300 городов, из которых 30 — областные центры. некоторые города соединены между собой дорогами (но не более чем одной для каждой пары городов), причем любой путь по дорогам между двумя обычными , если он есть, проходит хотя бы через один областной центр. какое наибольшее количество дорог могло быть в этой стране?
- все областные центры соединены не более чем 1-й дорогой и
- от каждого города идет одна дорога к одному из областных центров.
Т.о. имеется 270 дорог ведущих к областным центрам и одна дорога соединяющая 30 областных центров.
Разные сочетания этих дорог дают 269+268+...+1=270*269/2=36315 различных путей между различными парами городов. (произвольно выбранный 1-й город связан с 269 городами; следующий выбранный из оставшихся связан с 268 оставшимися и т.д.). Все коммуникации между областными центрами это части одной дороги соединяющей все центры.