В стране 2017 городов, некоторые из них соединены дорогами. Назовем город...

Question

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

Answer 1

Пусть провинциальных городов 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 дорог