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

Наибольшее количество дорог в стране составляет 14070. Пусть $n=2017$ — общее количество городов. Разделим города на две группы:

1. Провинциальные города ( $P$): города, из которых выходит не более 7 дорог ( $d\left(v\right)\le 7$). Пусть их количество равно $p$. Непровинциальные города ( $S$): города, из которых выходит более 7 дорог ( $d\left(v\right)\ge 8$). Пусть их количество равно $s$.

По условию $p+s=2017$. Также известно, что у любой дороги хотя бы один конец — провинциальный город. Это означает, что между городами из группы $S$ дорог нет (группа $S$ является независимым множеством). ️ Шаг 1: Оценка общего количества дорог Пусть $E$ — общее количество дорог. Каждая дорога либо соединяет два провинциальных города ( $E_{pp}$), либо провинциальный и непровинциальный ( $E_{ps}$). Сумма степеней провинциальных городов: $\sum _{v\in P}d\left(v\right)=2E_{pp}+E_{ps}$Так как для любого $v\in P$ выполняется $d\left(v\right)\le 7$, то: $2E_{pp}+E_{ps}\le 7p$Общее количество дорог $E=E_{pp}+E_{ps}$. Выразим $E$ через сумму степеней: $E=\frac{(2E_{pp}+E_{ps})+E_{ps}}{2}\le \frac{7p+E_{ps}}{2}$ Чтобы максимизировать $E$, нужно максимизировать $E_{ps}$ и $p$. Однако $E_{ps}$ — это также количество концов дорог, входящих в города группы $S$. Так как в каждый город из $S$ может входить не более $p$ дорог (по одной от каждого города из $P$), то $E_{ps}\le s\cdot p$. Также из условия $d\left(v\right)\le 7$ для $v\in P$ следует, что от каждого города из $P$ в сторону $S$ идет не более 7 дорог, т.е. $E_{ps}\le 7p$. ️ Шаг 2: Нахождение максимума Рассмотрим два случая для $E_{ps}$:

1. Если $s<7$, то $E_{ps}\le s\cdot p$. Тогда $E\le \frac{7p+sp}{2}=\frac{(7+s)(2017-s)}{2}$ . Если $s\ge 7$, то $E_{ps}\le 7p$. Тогда $E\le \frac{7p+7p}{2}=7p=7(2017-s)$ .

Проверим значения для малых $s$:

• При $s=1$: $E\le \frac{8\cdot 2016}{2}=8064$ . При $s=6$: $E\le \frac{13\cdot 2011}{2}=13071,5⟹13071$ . При $s=7$: $E\le 7\cdot (2017-7)=7\cdot 2010=14070$. При $s=8$: $E\le 7\cdot (2017-8)=14063$ (значение убывает).

Наибольшее значение достигается при $s=7$. В этом случае каждый провинциальный город имеет ровно 7 дорог, и все они ведут в 7 непровинциальных городов. При этом условия задачи соблюдены: степени городов из $S$ равны 2010 (что $>7$), а степени городов из $P$ равны 7. Ответ: В стране может быть максимум 14070 дорог. Укажите, требуется ли построить пример графа для этой задачи или рассмотреть случай с другим количеством городов?