Архипелаг состоит из N⩾9 островов. Любые два острова соединены не более чем одним мостом. Известно, что с каждого острова ведет не более чем 5 мостов, а среди любых 9 островов обязательно есть два, соединенные мостом. Какое наибольшее значение может принимать N?

Задача сводится к определению максимального количества островов $N$ в архипелаге, чтобы выполнялись все условия задачи:

1. Любые два острова соединены не более чем одним мостом.
2. Каждый остров соединён не более чем с 5 другими островами (максимальная степень вершины графа — 5).
3. Среди любых 9 островов найдётся хотя бы одна пара островов, соединённых мостом.

Рассмотрим, как эти условия влияют на построение графа (где вершины представляют острова, а рёбра — мосты):

1. Условие ограничения степеней вершин

Ограничение в 5 мостов на один остров означает, что каждый остров может быть связан максимум с пятью другими островами. Это типичный случай задачи на ограничение степени вершин в графе. Таким образом, каждый остров имеет степень не выше 5, что ограничивает плотность графа.

2. Условие о наличии рёбер среди любой подгруппы из 9 островов

Это условие — ключевое, и оно ограничивает максимальное значение $N$. Условие говорит, что среди любых 9 островов найдётся хотя бы одна пара соединённых мостом. В терминах теории графов это означает, что граф должен быть достаточно плотным, чтобы среди любых 9 вершин нашлось хотя бы одно ребро.

Поиск максимального значения $N$

Чтобы найти наибольшее возможное значение $N$, нужно понять, при каком $N$ можно построить граф с указанными ограничениями. Можно исследовать, как построить граф, который бы отвечал всем условиям, постепенно увеличивая количество вершин и проверяя выполнимость условий.

1. Для $N = 9$: Построить граф, в котором любые 9 вершин содержат хотя бы одно ребро, достаточно просто. Простейшая структура — это не полный, но достаточно связанный граф, где некоторые вершины соединены рёбрами, но максимальная степень каждой вершины не превышает 5. Такой граф построить возможно.

2. Для $N = 10$ и больше: Проверим, можно ли добавить вершины, сохраняя условия задачи. При $N = 10$ становится сложнее, поскольку любое добавление вершины должно сохранять ограничение на степень вершин, а также условие наличия рёбер среди любых 9 вершин.

Для чисел, превышающих 10, возникают сложности с выполнением второго условия, и построение графа, удовлетворяющего всем условиям, становится невозможным. Аналогичные рассуждения применимы и к случаям $N = 11$, $N = 12$ и т.д.

Вывод

Путём анализа становится ясно, что максимальное значение, при котором можно построить граф, удовлетворяющий всем условиям, — это $N = 10$.