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

Пусть провинциальных городов x, а дорог - k

тогда k ≤ 7x

тогда остальных 2017 - x

дорог из остальных ≥ (2017 - x) * 8

т. к. из непровинциальных до каждого провинциального выходит дорога, то

k ≥ 2017 - x

т. е. всего дорог ≥ 2017 - x + (2017 - x) * 8 = (2017 - x) * 9 - будет максимально при наименьшем x

2017 - x ≤ k ≤ 7x

2017 - x ≤ 7x

2017 ≤ 8x

x ≥ 252,125

x ≥ 253

наименьший x = 253

значит дорог: (2017 - 253) * 9 = 15876 (дорог)

Ответ: 15876 дорог