Processing math: 100%

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


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

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

  1
3 года 11 месяца назад #

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

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

Вспомогательаня оценка: n150

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

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

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

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

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

Финальная оценка: n200

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

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

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

Значит, 2n301=k1299n3n600n200.

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

Обозначения V,A,B оставим теми же. Пусть X1,X2,...,X200 - вершины множества A, а Y1,Y2,...,Y99 - вершины множества B.

Соединим вершину Yi с вершинами X1,...,X200i для каждого 1i99

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

  0
3 года 1 месяца назад #

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

Ответ: 200.

Оценка.

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

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

В B всего 299n вершин, и среди их степеней должны встречаться хотя бы 2n301 различных чисел, откуда 2n301299n. Получается, что n200, что и требовалось.

Пример.

Примером будет двудольный граф с долями X1,X2,X200 и Y1,Y2,Y100.

Соединим Xi и Yj в том и только в том случае, когда i+j101. Тогда степени вершин X1,X2,,X100,Y1,Y2,Y100 пробегают значения от 1 до 200, а треугольников нет в силу двудольности.