Question

В стране есть несколько городов, соединённых дорогами. Город называется захолустным, если из него выходит только одна дорога, и узловым, если из него выходит не менее трёх дорог. Известно, что в этой стране 101101101 захолустный город. При каком наименьшем количестве узловых городов можно заведомо утверждать, что в стране найдутся несколько городов, связанных циклическим маршрутом?

Answer 1

Ответ:

3 узловых города

Пошаговое объяснение:

Есть города, соединенные дорогами.

В некоторые города ведёт 1 дорога, это захолустные.

Всего их 1.0110.1101 = 256+64+32+8+4+1 = 365.

Ещё есть города, из которых выходит 3 дороги или больше.

Это узловые города. Надеюсь, это понятно.

Вопрос: какое минимальное количество узловых городов в стране?

Решение: Минимальное количество узловых городов равно 3.

На рисунке показан план этого города.

Есть треугольник из 3 узловых городов, из каждого выходит много дорог.

Две дороги ведут к двум другим узловым городам, а остальные дороги ведут к захолустным городам. И всего таких захолустных дорог 365.

На рисунке показано по 3 таких дороги, выходящих из каждого узлового города к захолустным.

Answer 2

Рассмотрим граф, в котором вершины соответствуют городам, а рёбра — дорогам. Тогда каждый захолустный город имеет степень 1, а каждый узловой город имеет степень не менее 3. Пусть всего в стране $n$ городов. Тогда количество рёбер в графе равно $r = \frac{1}{2}\sum_{i=1}^n \operatorname{deg}(i)$, где $\operatorname{deg}(i)$ — степень $i$-й вершины. По условию задачи, количество захолустных городов равно $101101101$, что означает, что $\sum_{i=1}^n [\operatorname{deg}(i) = 1] = 101101101$. Искомое наименьшее количество узловых городов равно количеству циклов в графе, каждый из которых содержит не менее 2 вершин.

Применим теорему Эйлера: $r = \frac{1}{2}\sum_{i=1}^n \operatorname{deg}(i) = \frac{1}{2}(n - k + 101101101)$, где $k$ — количество компонент связности в графе. Если в графе нет циклов, то $r \le n-1$, иначе $r \ge n$. Подставляя эти неравенства в выражение для $r$, получаем:

$$\frac{1}{2}(n - k + 101101101) \le n-1 \quad \Rightarrow \quad k \ge 101101101 - n + 1$$

$$\frac{1}{2}(n - k + 101101101) \ge n \quad \Rightarrow \quad k \le 101101101 - n - 1$$

Таким образом, для того чтобы в графе были циклы, необходимо, чтобы число компонент связности $k$ было не больше $101101101 - n - 1$ и не меньше $101101101 - n + 1$. Найдём минимальное значение $n$, удовлетворяющее этому условию.

$101101101 - n + 1 \le 101101101 - n - 1 \quad \Rightarrow \quad n \ge \frac{101101101}{2} + 1$

Таким образом, наименьшее количество узловых городов, которые гарантированно образуют циклы, равно $101101101 - n + 1 \ge 101101101 - \frac{101101101}{2} = 50550550$. Ответ: $\boxed{50550550}$.