В качестве ответа введите натуральное число. Никаких иных символов, кроме используемых для записи числа (в частности, пробелов), быть не должно. Пример: 3 На первом острове 15 городов, а на втором острове 18 городов. Кроме того, рядом с этими островами есть материк, на котором также есть города. Между некоторыми городами есть дороги, при этом любые два города соединены не более чем одной дорогой. Каждая дорога соединяет ровно два различных города. Жители этих двух островов решили построить 540 дорог. а) Какое наибольшее количество дорог можно построить между городами первого острова? Укажите ТОЛЬКО число.

Дано: - Городов на первом острове — 15 - Городов на втором острове — 18 - Всего дорог между двумя островами — 540 Задача: найти максимум возможных дорог между городами первого острова. --- **Шаг 1: Построение модели** Обозначим: - \(A\) — число дорог внутри первого острова, соединяющих его города между собой. - \(B\) — число дорог внутри второго острова. - \(C\) — число дорог, соединяющих города первого и второго островов. Всего дорог: \[ A + B + C = 540 \] Нам нужно максимизировать \(A\). --- **Шаг 2: Механизм ограничения** - Максимальное число дорог внутри первого острова (полностью соединенного графа из 15 городов): \[ \binom{15}{2} = \frac{15 \times 14}{2} = 105 \] - Аналогично, внутри второго острова: \[ \binom{18}{2} = \frac{18 \times 17}{2} = 153 \] - Число дорог между городами разных островов \(\ C \) не имеет верхней границы, кроме как ограниченной общей суммой: \[ A + B + C = 540 \] Чтобы максимально увеличить \(A\), необходимо минимизировать \(B + C\), но при этом исходя из ограничений: - \(A \leq 105\) (максимум внутри первого острова). - \(B \leq 153\) Поскольку при максимизации \(A\) нужно, чтобы сумма \(B + C\) была минимальной. --- **Шаг 3: Минимизация \(B + C\)** Поскольку \(B\) не может превышать 153, выбираем минимальное \(B\): - Пусть \(B = 0\), тогда: \[ A + C = 540 \] Так как \(A \leq 105\), тогда: \[ C = 540 - A \] Но \(C\), как количество дорог между двумя островами, должно быть неотрицательным: \[ C \geq 0 \Rightarrow 540 - A \geq 0 \Rightarrow A \leq 540 \] Но \(A \leq 105\), потому что внутри первого острова не может быть больше возможных соединений. - Проверка, если взять \(A = 105\): Тогда: \[ C = 540 - 105 = 435 \] Это допустимо. В таком случае: - Внутри первого острова — максимально возможное число дорог. - Между островами — 435 дорог, что меньше максимально возможных \(15 \times 18 = 270\) (если соединять все города обоих островов полностью). Но видим, что 435 больше, чем максимально возможное число дорог между двумя группами: максимум \(15 \times 18 = 270\). Тогда, в реальности, количество дорог между двумя островами не может превысить 270. Следовательно, \(C \leq 270\). Итак, чтобы соблюсти ограничения: - \(A \leq 105\) (максимум внутри первого острова). - \(C \leq 270\). Чтобы максимально увеличить \(A\), нужно взять \(A = 105\), при этом сумму \(B + C \leq 540 - 105 = 435\). Но поскольку \(C \leq 270\), то: \[ B \geq 435 - 270 = 165 \] Но \(B \leq 153\), что не допускает такой ситуации. Следовательно, при \(A = 105\), \(B\) должно быть равно максимуму (153), тогда: \[ C = 540 - (A + B) = 540 - (105 + 153) = 540 - 258 = 282 \] Но \(C \leq 270\), значит такое невозможно. Следующие попробуем уменьшить \(A\). --- **Шаг 4: Вычисление максимально возможного \(A\) с учетом ограничений** Обозначим \(A\) — искомое максимальное число дорог внутри первого острова. - Максимум внутри острова: 105. - Максимум межостровных дорог: \(15 \times 18 = 270\). Если \(A\) максимально равно 105, то: \[ C_{\text{макс}} = 270 \] Тогда: \[ B = 540 - (A + C) = 540 - (105 + 270) = 165 \] Но \(B \leq 153\), а не 165, значит невозможно. Уменьшим \(A\): - Пусть \(A = 105\), тогда \(C \leq 270\): \[ B = 540 - (105 + C) \] Чтобы \(B \leq 153\): \[ 540 - (105 + C) \leq 153 \] \[ 540 - 105 - C \leq 153 \] \[ 435 - C \leq 153 \] \[ -C \leq 153 - 435 = -282 \] \[ C \geq 282 \] Но \(C \leq 270\), поэтому невозможно выполнить \(C \geq 282\). Следовательно, при \(A=105\) — невозможно. Попробуем уменьшить \(A\): - Пусть \(A=104\): Тогда: \[ C \leq 270 \] \(B = 540 - (104 + C)\) Чтобы \(B \leq 153\): \[ 540 - (104 + C) \leq 153 \] \[ 436 - C \leq 153 \] \[ -C \leq -283 \] \[ C \geq 283 \] Всё ещё невозможно, так как \(C \leq 270\). Аналогично для \(A=103\): \[ 540 - (103 + C) \leq 153 \] \[ 437 - C \leq 153 \] \[ -C \leq -284 \] \[ C \geq 284 \] И снова не подходит. --- **Шаг 5: Итоговое решение** Переходим к условию, что минимальное \(A\) для достижения максимума — это когда все остальные параметры задаются по максимуму, что не противоречит ограничениям. - Максимум внутри первого острова: 105. - При этом, чтобы не выходить за пределы, \(C\) максимум равен 270, а \(B\), соответственно, минимален. Проверяем для \(A=105\): \[ C \leq 270, B = 540 - A - C = 540 - 105 - C = 435 - C \] Чтобы \(B \leq 153\): \[ 435 - C \leq 153 \] \[ -C \leq 153 - 435 = -282 \] \[ C \geq 282 \] Но \(C \leq 270\), так что не подходит. Тогда уменьшаем \(A\) по шагам и ищем подходящий пример. --- **Шаг 6: Итоговая проверка** Для максимального внутриостровного числа дорог: - Максимум внутри первого острова — \(105\), так как полное соединение — всего 105. - В итоге, чтобы соблюсти все ограничения, лучше всего взять: \[ A=105 \] и при этом: \[ C=0,\quad B=540 - 105 - 0=435 \] Но \(B \leq 153\), где явно не подходит. Поскольку \(B=435\) — невозможно, нужно снизить \(A\), чтобы \(B \leq 153\): \[ B = 540 - A - C \leq 153 \] При минимальном \(C=0\): \[ 540 - A \leq 153 \] \[ A \geq 540 - 153 = 387 \] Но \(A \leq 105\), противоречие — значит, невозможно одновременно иметь очень большие \(A\) и малые \(B\); при этом \(A\) не может превышать 105. **Следовательно, максимальное внутреннее число дорог \(\boxed{105}\).** --- **Ответ:** **(105)**