Определи действие, с которого можно вычислить модуль - вопрос №15785327 от zheckachernev 12.10.2021 13:50

Question

Математика: Определи действие, с которого можно вычислить модуль суммы

zheckachernev · Answer

Пусть всего 2n=100 точек. Рассмотрим граф на этих вершинах. Рассмотрим вершину (пусть это вершина ) с наибольшей степенью. Пусть эта степень равна . Заметим, что у вершин, имеющих связь с нет ребер к другим вершинам, связанным с (иначе получился бы треугольник). Поэтому степень этих вершин не больше, чем 2n-u . Степени оставшихся не превосходят . Поэтому сумма степеней не превосходит u(2n-u)+(2n-u)u=2u(2n-u) . Количество ребер не превосходит $2u(2n-u)/2=u(2n-u)\leq (\frac{u+2n-u}{2})^2=n^2=2500$ (последнее неравенство — следствие из н-ва между ср. арифм. и ср. геометр.)

С другой стороны, несложно привести пример: рассмотрим двудольный граф (две равные доли по 50 вершин) и проведем всевозможные ребра (их будет 50*50=2500).

Если же проведено более 2500 ребер, то образуется хотя бы один треугольник (на самом деле их будет хотя бы 50).

ответ: 2500