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

Обычные города с обычными не соединены, значит, могут быть только дороги между областными центрами и дороги между обычными городами и областными центрами;

Максимальное количество дорог между областными центрами 30 • 29 / 2 - число сочетаний из 30 по 2;

Каждый из обычных городов может быть соединен только с областными центрами, их 30,

максимально он будет соединен со всеми тридцатью, это еще 270 • 30 дорог;

Максимальное количество дорог будет:

30 • 29 / 2 + 270 • 30 = 8535 дорог;

Ответ: Наибольшее количество дорог может быть 8535;