Областная олимпиада по математике, 2020 год, 11 класс
Комментарий/решение:
Задача на рассмотрение локальных свойств конструкции.
Будем пользоваться терминами теории графов
Вспомогательаня оценка: n≥150
Доказательство (догадаться можно с помощью Теоремы Турана):
Пусть A и B - две равные доли графа из 300 вершин. Для начала соединим между собой каждую вершину доли A с каждой вершиной доли B.
Далее можно удалять ребра у вершин доли A так, чтобы все вершины имели степени 1, 2, ..., 150.
Данная конструкция удовлетворяет условию.
Теперь можем считать, что n>299−n
Финальная оценка: n≤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≤299−n⇔3n≤600⇒n≤200.
Пример на n=200:
Обозначения V,A,B оставим теми же. Пусть X1,X2,...,X200 - вершины множества A, а Y1,Y2,...,Y99 - вершины множества B.
Соединим вершину Yi с вершинами X1,...,X200−i для каждого 1≤i≤99
Нетрудно убедиться, что данная конструкция удовлетворяет условию.
Это решение от Ereb.15 в его же обозначениях, написанное чуть более понятным языком.
Ответ: 200.
Оценка.
Введем граф. Пусть v — вершина степени n, A и B — соответственно множества соединенных и не соединенных с v вершин.
Вершины в A между собой не соединены (иначе образуется треугольник c участием v), поэтому их степени не превосходят 300−|A|=300−n. Следовательно, в B обязательно должны быть вершины со степенями 301−n,302−n,…,n−1, чтобы все степени встречались.
В B всего 299−n вершин, и среди их степеней должны встречаться хотя бы 2n−301 различных чисел, откуда 2n−301≤299−n. Получается, что n≤200, что и требовалось.
Пример.
Примером будет двудольный граф с долями X1,X2,…X200 и Y1,Y2,…Y100.
Соединим Xi и Yj в том и только в том случае, когда i+j≥101. Тогда степени вершин X1,X2,…,X100,Y1,Y2,…Y100 пробегают значения от 1 до 200, а треугольников нет в силу двудольности.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.