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

Для решения этой задачи требуется выяснить, какие дороги существуют в стране и между какими городами.

Какие существуют дороги

В этой стране могут быть следующие виды дорог:

дороги между областными центрами - существуют; дороги между областными центрами и обычными городами - существуют; дороги между обычными городами - отсутствуют.

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

Расчет количества дорог

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

10 · 9 / 2 - число сочетаний из 10 по 2;

Каждый из обычных городов может быть соединен только с областными центрами, которых десять, максимально он будет соединен со всеми десятью, это еще 190 · 10 дорог;

Максимальное количество дорог получится если сложить все дороги, которые имеются между областными центрами и все дороги соединяющие обычные города с областными центрами:

10 · 9 / 2 + 190 · 10 = 1945 дорог;

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

Между обычными городами дорог по условию нет, значит все дороги соединяют либо обычный город с областным центром, либо два областных центра. Если мы проведем все дороги таких видов, то условие, очевидно, выполнено.

Дороги, соединяющие город с областным центром:

190 x 10 = 1900 дорог;

Дороги, соединяющие два областных центра:

10 x 9/2 = 45 дорог;

Наибольшее количество дорог в стране:

1900 + 45 = 1945 дорог;

Ответ: Наибольшее количество дорог в этой стране могло быть 1945;