Высшая проба 2026, 10 класс, задача 5
(20 баллов) Дано натуральное число . Архипелаг Дракона состоит из островов. Между островами действуют паромные переправы трёх различных транспортных компаний, каждая из которых владеет ровно различными паромами. Каждый паром осуществляет одностороннюю переправу с одного острова на другой; для всякой упорядоченной пары островов и всякой компании существует не более одного парома от к , принадлежащего данной компании. Назовём остров зацикленным посредством компании , если существует нетривиальный маршрут, использующий только паромы этой компании, который начинается и заканчивается в . Найдите наименьшее , при котором обязательно найдётся остров, зацикленный посредством всех трёх компаний.
Ответ. .
Решение. Пример. Построим ориентированный граф, в котором вершины соответствуют островам, ребро соответствует парому от к , и каждое ребро окрасим в один из трёх цветов, соответствующих компании (для каждой упорядоченной пары островов может быть до трёх рёбер разных цветов). Докажем вспомогательное утверждение.
Лемма. Пусть есть ориентированный граф на вершинах с рёбрами и известно, что не более его вершин лежат на каких-то ориентированных циклах. Тогда
Доказательство леммы. Зафиксируем две вершины . Если хотя бы одна из них не лежит ни на одном цикле, то не более одного ребра или может быть, поэтому таких «односторонних» рёбер не может быть больше . Если же обе вершины лежат на цикле, то в дополнение к посчитанному может добавиться не более рёбер, откуда
Лемма доказана.
Как следствие, если число рёбер превосходит , то количество вершин, лежащих на цикле, строго больше . Пусть , . Тогда в случае
найдётся хотя бы вершин, лежащих на цикле. В нашем случае это означает, что граф паромов каждой компании имеет не менее циклических вершин (то есть лежащих на цикле). При этом всего вершин . Покажем, что тогда найдётся общая для всех циклическая вершина.
Мы имеем три подмножества мощности не менее каждое в множестве вершин мощности . Тогда мощность дополнения каждого из них не более . Но тогда мощность объединения дополнений
и
Таким образом, найдётся не менее трёх островов, зацикленных посредством всех трёх компаний, при
Оценка. Покажем, что при
нельзя гарантировать наличие даже одного острова, зацикленного всеми тремя компаниями. Разобьём острова на три части по островов в каждой и построим переправы так: для первой компании пустим односторонние паромы между всеми парами островов (в произвольных направлениях), а все пары островов вне соединим дополнительно между собой одним экземпляром парома, дополняющего каждую переправу до противоположной; аналогично сделаем для второй и третьей компании с частями и соответственно. Тогда каждая компания владеет ровно
паромами. Тем не менее каждый остров зациклен лишь посредством двух компаний: каждый остров из - второй и третьей, из - третьей и первой, из - первой и второй.
Понятно, что и для всякого меньшего этот же пример с произвольно удалёнными паромами даёт контрпример к утверждению. Таким образом, ни для какого меньшего гарантировать требуемое нельзя, что завершает оценку
Верное решение.
Записан ответ(вместо) при полностью верном решении.
Оценка на.
Доказывалась неверная оценка, отличная от верной более чем на.
Решение не соответствует ни одному из критериев выше.