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

Ответ. .

Решение. Положим . Поставим в соответствие каждому математику вершину и соединим ребром вершины, соответствующие друзьям. Мы получили граф, обладающий таким свойством: степени любых двух соседних (т.е. соединенных ребром) вершин отличаются ровно на . Пусть и — множества вершин и рёбер этого графа, тогда . Нам нужно найти максимальное (т.е. максимальное количество рёбер в таком графе).

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

Оценка. Докажем, что . Обозначим через множество вершин степени . По условию, ребро может соединять только две вершины из и (при некотором ). Пусть — максимальная степень вершины (т.е. и ).

) Если , то степень каждой вершины в графе не больше , поэтому

откуда .

) Пусть . Возьмем вершину . Она соединена с вершинами, каждая из которых лежит в . Отсюда . Возьмем вершину . Она соединена с вершинами (каждая из которых лежит в или в ). Значит,

противоречие.

) Остается рассмотреть случай . Каждое ребро соединяет вершину из множества

с вершиной из множества

Поэтому равно количеству ребер, исходящих из , следовательно, . А также равно количеству ребер, исходящих из , откуда .

Если , то в силу первого неравенства . Иначе , но тогда , и в силу второго неравенства .

Итак, во всех случаях доказана оценка .

Замечание. В оценке случай может быть разобран так же, как случай .