В стране 2017 городов, некоторые из них соединены дорогами. Назовем город <>, если из него выходит не больше 7 дорог. Оказалась, что у любой дороги хоть одним из концов является провинциальный город. Какое наибольшее количество дорог может быть в этой стране?

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

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

В стране может существовать три типа дорог:

между "провинциальными" городами; дороги между "провинциальным" городом и обыкновенным городом; дороги между обыкновенными городами - не существуют;

Чтобы определить какое наибольшее количество дорог может быть в этой стране, рассмотрим возможности их проведения.

У любой дороги хоть одним из концов является "провинциальный" город. Из каждого "провинциального" города выходит только 7 дорог, значит, если соединить между собой дорогами два "провинциальных" города, то это уменьшит количество дорог на одну. Поэтому, будем соединять дорогами только "провинциальный" город с обыкновенным.

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

Чтобы получить максимальное количество дорог, надо каждый "провинциальный" город соединить с обыкновенным. Значит, минимальное необходимое количество обыкновенных городов должно быть 7, чтобы из каждого "провинциального" города выходило по 7 дорог, тогда:

Количество "провинциальных" городов: 2017 - 7 = 2010;

Количество дорог, выходящих из "провинциальных" городов: 2010 x 7 = 14070;

Это и есть максимальное количество дорог.

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

Чтобы получить максимальное количество дорог, надо каждый город соединить с обыкновенным. Если соединить два города между собой, то это уменьшит количество дорог на одну, так как из каждого города может выходить только 7 дорог. Значит, минимальное необходимое количество обыкновенных городов должно быть 7, чтобы из каждого города выходило по 7 дорог. Количество городов: 2017 - 7 = 2010; Количество дорог, выходящих из городов: 2010 x 7 = 14070; Это и есть максимальное количество дорог; Ответ: Наибольшее количество дорог, которое может быть в этой стране 14070;