ВСОШ 2026, 9 класс, задача 10

Ответ. .

Решение 1. Введём граф, вершины которого будут соответствовать людям; две вершины соединены синим ребром, если соответствующие работники знакомы, и красным иначе. Тогда из каждой вершины выходят ровно синих рёбер — назовём множество их вторых концов окрестностью вершины , и в каждом множестве есть две вершины, соединённые красным ребром. Требуется же выяснить, при каком наибольшем обязательно найдётся вершина такая, что на вершинах множества есть хотя бы красных рёбер.

Пример. Покажем сначала, что при требуемая вершина найдётся не всегда. Рассмотрим вершины, разобьём их на пары и вершины каждой пары соединим красным ребром. Все остальные пары вершин соединим синими рёбрами. Тогда окрестность каждой вершины состоит из пар, и на них есть ровно красных рёбер. Таким образом, условие выполнено, но ни в одной окрестности нет красного ребра.

Оценка. Осталось показать, что при требуемая окрестность всегда найдётся. Предположим противное. Рассмотрим произвольную вершину . В множестве найдутся две вершины и , соединённые красным ребром. Тогда из выходит синее ребро в какую-то вершину, не лежащую в — обозначим её через . Итак, вершины и соединены красным ребром, но множества и пересекаются — хотя бы по .

Положим ; пусть — количество вершин в , тогда . Обозначим через множество всех вершин в , не лежащих в , а через множество всех вершин в , не лежащих в ; тогда в и по вершин. Пусть ; тогда число вершин в равно . Пусть есть всего красных рёбер, соединяющих вершины друг с другом, красных рёбер, соединяющих с , и красных рёбер, соединяющих с .

Из каждой вершины множества идут синие рёбра в , в и ещё максимум синих рёбер в ; значит, из идут не менее красных рёбер в . Просуммировав эти количества по всем вершинам множества , мы учтём каждое из красных рёбер, соединяющих вершины друг с другом, дважды, а каждое из красных рёбер, соединяющих с вершинами из , по разу, то есть получим оценку . С другой стороны, на множестве есть хотя бы красных рёбер, а на множестве — хотя бы красных рёбер; по нашему предположению, оба этих количества не превосходят , поэтому

Но это неравенство неверно, поскольку

Решение 2. Приведём другое доказательство того, что при требуемая окрестность найдётся. Опять же предположим противное. Воспользуемся следующими двумя нехитрыми соображениями.

Лемма 1. Пусть у вершины есть ровно вершин в , с которыми она соединена красным ребром. Тогда соединена синими рёбрами ровно с вершинами, отличными от и не лежащими в .

Доказательство. Вершина соединена синими рёбрами с и ровно с вершинами в . Значит, количество остальных вершин, с которыми она соединена синими рёбрами, равно . □

Лемма 2. Пусть у вершины есть вершин в , с которыми она соединена красными рёбрами. Тогда в есть как минимум вершин, каждая из которых соединена со всеми остальными вершинами в синими рёбрами.

Доказательство. Если это не так, то из вершины выходит красных рёбер в другие вершины , и ещё минимум из других вершин в выходит хотя бы по одному красному ребру в вершины . Значит, общее количество красных рёбер между вершинами множества не меньше , то есть их хотя бы . Это противоречит нашему предположению. □

Перейдём к решению. Рассмотрим произвольную вершину . Выберем вершину , из которой выходит наибольшее количество красных рёбер в другие вершины из (тогда ). Обозначим через множество вершин, соединённых с синим ребром, а с — красным; по лемме , в ровно вершин.

В множестве содержится вершина ; при этом она соединена с вершинами из красными рёбрами — а именно, с вершинами из . По лемме , в есть вершин, каждая из которых соединена синими рёбрами со всеми вершинами из (отличными от неё); обозначим через множество этих вершин. В частности, не лежит в (ибо из выходят красные рёбра в ), и все вершины из соединены синими рёбрами с , то есть содержится в .

Рассмотрим теперь какую-нибудь вершину из , соединённую с красным ребром. Любая вершина соединена синими рёбрами со всеми другими вершинами из и с самой — здесь уже перечислены все синих рёбер, выходящих из неё. Значит, соединена с красным ребром. Но тогда из выходит красных ребра в вершины из — а именно, в и во все вершины из . Это противоречит выбору ; значит, наше исходное предположение неверно, что мы и хотели доказать.

Замечание. Существуют и другие способы доказать оценку.

Например, опять же в предположении противного, можно выбрать наибольшее , при котором найдутся вершины и такие, что соединена с вершинами из красными рёбрами (тогда ). Опять же обозначим через множество вершин из , не лежащих в ; тогда . Пусть ; тогда из леммы можно вывести, что из вершин множества выходит суммарно не более синих рёбер в вершины из . Значит, количество красных рёбер между и не меньше, чем ; нетрудно показать, что , и потому в найдётся вершина, соединённая более чем с вершинами из красными рёбрами. Это противоречит выбору , ибо все эти вершины лежат в .