Question

В некоторой стране есть 2017 городов, некоторые из которых соединены друг с другом дорогами (каждые два города соединяет не более одной дороги). Известно, что из каждого города напрямую можно добраться ровно до M городов. Чему может равняться M? Выберите из списка возможные значения: 46 15 2 1000 2017 2016 1 3 1999

Answer 1

2016, так как городов 2017, а он сам выезжает из 1 города, этот город не считается)

Answer 2

Предположим, есть 2017 городов, некоторые из которых соединены друг с другом дорогами так, что каждые два города соединены не более чем одной дорогой. Задача заключается в определении значения M - количества городов, до которых можно добраться из каждого города напрямую.

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

Согласно теореме о рукопожатиях для графов, сумма степеней всех вершин графа равна удвоенному количеству его рёбер. В данном случае сумма степеней вершин (количество городов, до которых можно добраться из каждого города) будет равна удвоенному числу рёбер (дорог), потому что каждая дорога связывает два города.

Формула для суммы степеней вершин графа: \[ \sum \text{степени вершин} = 2 \times \text{число рёбер} \]

Общее количество дорог, соединяющих города, будет равно сумме степеней вершин. Таким образом, сумма степеней вершин равна \(2 \times 2017\), так как каждая дорога вносит в сумму две степени (по одной для каждого города, которому она инцидентна).

Теперь, чтобы найти M (количество городов, до которых можно добраться из каждого города напрямую), нужно разделить эту сумму на количество городов и округлить до ближайшего целого числа.

\[ M = \frac{\text{Сумма степеней вершин}}{\text{Количество городов}} = \frac{2 \times 2017}{2017} = 2 \]

Таким образом, значение M равно 2.