Рассмотрим условие задачи подробно и шаг за шагом:
Дано:
- На первом острове 13 городов.
- На втором острове 16 городов.
- Есть материк, у которого также есть города (числитель их неизвестен, но он не важен для решения задачи).
- Между некоторыми городами есть дороги.
- Каждые две разные города соединены не более чем одной дорогой.
- Между двумя городами соединена ровно одна дорога или её нет.
- Жители островов решили построить всего 450 новых дорог.
- Необходимо определить максимальное возможное число дорог, которые можно построить между городами первого острова.
Шаг 1: Что из себя представляют возможные дороги?
Все города могут быть связаны дорожками:
- Внутри каждого острова (между городами одного острова).
- Между городами первого острова и города другого острова, или материка.
- Между городами второго острова и материка.
- Между городами материка самого по себе.
Нас интересует максимальное число дорог внутри первого острова.
Шаг 2: Общие ограничения
- Общее число новых дорог — 450.
- Дорог внутри первого острова — это неограниченный по условию несколько (теоретическая граница — число всех возможных пар в 13 городах).
Максимальное число дорог между городами первого острова, без ограничений, — это число всех пар городов:
[
\binom{13}{2} = \frac{13 \times 12}{2} = 78
]
То есть, внутри первого острова максимум можно соединить все города между собой — это полное графа (K_{13}).
Шаг 3: Как максимально использовать 450 дорог?
Допустим, мы хотим максимизировать число дорог внутри первого острова.
Если внутри первого острова уже есть все возможные 78 дорог, то остальные дороги (450 – 78 = 372) могут быть построены между:
- Городами первого и второго островов,
- Городами первого острова и материка,
- Городами второго острова и материка,
- Городами материка и материка (если считать материк как множество городов).
При этом в задаче нет ограничения на соединения между другими группами городов и материком, кроме общего лимита 450 дорог.
Шаг 4: Максимальное внутреннее число дорог в первом острове
Значит, чтобы максимизировать количество дорог внутри первого острова, разумно построить полностью все возможные дороги внутри этого острова:
[
\boxed{78}
]
и при этом максимально использовать остальные 372 дороги для соединений с другими группами.
Это — оптимальный подход, поскольку:
- Еще раз повторим: внутри первого острова не может быть больше 78 дорог.
- Полное соединение внутри острова даёт максимальное внутреннее число дорог, а оставшиеся дороги можно использовать для соединений с другими группами (второй остров и материк).
Ответ:
Наибольшее возможное количество дорог, которые можно построить внутри города первого острова, равно 78.
