В качестве ответа введите натуральное число. Никаких иных символов, кроме используемых для записи числа (в частности, пробелов), быть не должно. Пример: 3 На первом острове 14…
В качестве ответа введите натуральное число. Никаких иных символов, кроме используемых для записи числа (в частности, пробелов), быть не должно. Пример: 3 На первом острове 14 городов, а на втором острове 17 городов. Кроме того, рядом с этими островами есть материк, на котором также есть города. Между некоторыми городами есть дороги, при этом любые два города соединены не более чем одной дорогой. Каждая дорога соединяет ровно два различных города. Жители этих двух островов решили построить 500 дорог. a) Какое наибольшее количество дорог можно построить между городами первого острова? Укажите ТОЛЬКО число. За этот вопрос вы можете получить 2 балла 6) Какое наименьшее количество дором должно соединять город на любом из этих двух островов с городом на материке? Укажите ТОЛЬКО число. За этот вопрос вы можете получить 3 балла
Для решения задачи рассмотрим оба вопроса по порядку.
Дано:
- Первый остров: 14 городов
- Второй остров: 17 городов
- Не указано количество городов на материке (пусть на материке \(m\))
- Всего построено 500 дорог, при этом любые две дороги соединяют разные города, и между двумя городами может быть не более одной дороги.
a) Максимальное число дорог между городами первого острова (14 городов)
Максимальное количество дорог между городами одного острова — это полное соединение всех его городов (клика).
Количество дорог в полном графе с \(n\) вершинами — это \(\frac{n(n-1)}{2}\).
Для первого острова с 14 городами:
\[ \text{максимум} = \frac{14 \times 13}{2} = \frac{182}{2} = 91 \]
Ответ для пункта а): 91
b) Наименьшее количество дорог, соединяющих любой город любого из островов с материком
Общее число дорог: 500
В том числе дороги внутри островов:
- Максимум внутри первого: 91
- Максимум внутри второго: \(\frac{17 \times 16}{2} = 136\)
Тогда минимально возможное число дорог, соединяющих города на островах с материком, — это обеспечить соединение городов островов с материком так, чтобы сумма всех дорог была равна 500.
Чтобы минимизировать число дорог, соединяющих любой конкретный город острова с материком, нужно максимально "убрать" дороги внутри островов.
Лемма:
Минимальный общий объём дорог, соединяющих острова с материком, при условии, что внутри островов реализованы их максимумы — это:
\[ \text{минимум} = 500 - (\text{Максимум внутри островов}) \]
- Максимум внутри обоих островов:
\[ 91 + 136 = 227 \]
- Остаётся:
\[ 500 - 227 = 273 \]
Общее число дорог, соединяющих оба острова с материком, нефиксировано по городам; требуется найти минимальное число дорог, соединяющих хотя бы один город с материком.
Для получения минимальной суммы дорог, соединяющих хотя бы один город с материком, нужно равномерно распределить эти дороги по городам. максимум — это ситуация, когда один город подключен к материка полностью.
В худшем случае, один город связан с материком всеми этими дорогами:
Тогда минимальное число дорог, прилегающих к одному городу, равно:
\[ \boxed{ \text{Общая связь с материком} / (\text{число городов}) } \]
- Итак, если общее число дорог, соединяющих остров и материк — 273, и мы делим их по всем городам, чтобы минимизировать число, необходимое для каждого конкретного города, то:
\[ \text{минимальное число} = \left\lceil \frac{273}{14 + 17} \right\rceil = \left\lceil \frac{273}{31} \right\rceil \]
- Вычислим:
\[ 273/31 \approx 8.81 \Rightarrow \left\lceil 8.81 \right\rceil = 9 \]
Ответ для пункта б): 9
Итоговые цифры:
- а) 91
- б) 9
Переводя в формат, ответ должен быть:
919
