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

Question

Михаил Сорокин

Геометрия

24 декабря, 08:11

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

+2

Ответы (1)

Знаешь ответ на этот вопрос?

Анастасия Медведева · Answer 1

6550

Пример: соединим дорогой каждые 2 облцентра и каждую пару вида "облцентр и обычный город". Дорог между облцентрами будет 25*24/2=300 (каждый из 25 облцентров соединён с каждым из 24 оставшихся, делим пополам, потому что мы посчитали каждую дорогу дважды). Обычных городов 250, дорог между облцентрами и обычными городами 25*250=6250, всего 6550.

Больше быть не может, т. к. дорога не может соединять 2 обычных города (нарушится условие), а все остальные возможные дороги посчитаны в примере.