Question

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

Answer 1

 Если каждая пара городов соединена не более чем одной дорогой, и любой путь по дорогам между двумя обычными городами проходит хотя бы через один областной центр, то
- все областные центры соединены не более чем 1-й дорогой и
- от каждого города идет одна дорога к одному из областных центров.
 Т.о. имеется 270 дорог ведущих к областным центрам и одна дорога соединяющая 30 областных центров.

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