Областная олимпиада по математике, 2020 год, 11 класс

В колледже учатся 300 студентов. Любые два студента либо знают друг друга, либо не знают друг друга, и нет трех студентов, знающих друг друга. Известно, что каждый студент знает не более $n$ других студентов и для каждого $m$ $(1\le m \le n)$ существует студент, знающий ровно $m$ других студентов. Найдите наибольшее возможное значение $n$.

Комментарий/решение

Задача на рассмотрение локальных свойств конструкции.

Будем пользоваться терминами теории графов

Вспомогательаня оценка: $n \geq 150$

Доказательство (догадаться можно с помощью Теоремы Турана):

Пусть $A$ и $B$ - две равные доли графа из 300 вершин. Для начала соединим между собой каждую вершину доли $A$ с каждой вершиной доли $B$.

Далее можно удалять ребра у вершин доли $A$ так, чтобы все вершины имели степени 1, 2, ..., 150.

Данная конструкция удовлетворяет условию.

Теперь можем считать, что $n > 299 - n$

Финальная оценка: $n \leq 200$

Доказательство:

По условию есть вершина $V$ степени $n$, тогда пусть $A$ - множество смежных с ней вершин, а $B$ - множество остальных вершин. (Т.е. тех, что не в $А$ и не являются $V$)

Скажем, что $k$ такое наибольшее число, что $n-k > 299-n$, т.е $k = 2n - 300$. Тогда в $B$ обязательно должны быть вершины со степенями $n-1, n-2, ..., n-k+1$. (Иначе найдется треугольник состоящий из двух вершин множества $A$ и вершины $V$).

Значит, $2n - 301 = k-1 \leq 299 - n \Leftrightarrow 3n \leq 600 \Rightarrow n \leq 200$.

Пример на $n = 200$:

Обозначения $V, A, B$ оставим теми же. Пусть $X_1, X_2, ..., X_{200}$ - вершины множества $A$, а $Y_1, Y_2, ..., Y_{99}$ - вершины множества $B$.

Соединим вершину $Y_i$ с вершинами $X_1, ..., X_{200-i}$ для каждого $1 \leq i \leq 99$

Нетрудно убедиться, что данная конструкция удовлетворяет условию.

Это решение от Ereb.15 в его же обозначениях, написанное чуть более понятным языком.

Ответ: 200.

Оценка.

Введем граф. Пусть $v$ — вершина степени $n$, $A$ и $B$ — соответственно множества соединенных и не соединенных с $v$ вершин.

Вершины в $A$ между собой не соединены (иначе образуется треугольник c участием $v$), поэтому их степени не превосходят $300-|A|=300-n$. Следовательно, в $B$ обязательно должны быть вершины со степенями $301-n,\; 302-n, \ldots, n-1$, чтобы все степени встречались.

В $B$ всего $299-n$ вершин, и среди их степеней должны встречаться хотя бы $2n-301$ различных чисел, откуда $2n-301\leq 299-n$. Получается, что $n\leq 200$, что и требовалось.

Пример.

Примером будет двудольный граф с долями $X_1,\; X_2,\ldots X_{200}$ и $Y_1,\; Y_2,\ldots Y_{100}$.

Соединим $X_i$ и $Y_j$ в том и только в том случае, когда $i+j\geq 101$. Тогда степени вершин $X_1, X_2,\ldots, X_{100}, Y_1, Y_2,\ldots Y_{100}$ пробегают значения от $1$ до $200$, а треугольников нет в силу двудольности.