ВсОШ 2025, 10 класс, задача 4
На плоскости отмечены точек, никакие три из которых не лежат на одной прямой, и проведены все отрезки между ними. Гриша поставил на каждом проведённом отрезке вещественное число, по модулю не превосходящее , и для каждой шестёрки отмеченных точек посчитал сумму чисел на всех отрезках, соединяющих их. Оказалось, что каждая такая сумма по модулю не меньше числа , при этом среди таких сумм есть как положительная, так и отрицательная. При каком наибольшем это возможно?
Ответ
Ответ. .
Решение. Рассмотрим граф, вершинами которого являются отмеченные точки, а рёбрами — проведённые отрезки.
Оценка. Докажем оценку . Условие гласит, что в нашем полном графе есть как шестёрки вершин, сумма на рёбрах между которыми положительна, так и шестёрки, сумма на рёбрах между которыми отрицательна. Тогда найдутся две шестёрки, отличающиеся заменой только одной вершины, такие, что у одной из них сумма положительна, у другой отрицательна. В самом деле, возьмём шестёрку с положительной суммой и будем превращать её в шестёрку с отрицательной, меняя вершины по одной: на каком-то шаге произошло изменение знака, шестёрки, которые были до и после этого шага, — искомая пара.
Далее работаем с полным подграфом на множестве из семи вершин — объединении вышеописанной пары шестёрок. Рассмотрим все семь шестёрок, которые можно получить выбрасыванием одной вершины из . Пусть среди них с отрицательными суммами — получающиеся выбрасыванием вершин (будем называть эти вершины -вершинами, а соответствующие шестёрки — -шестёрками), и с положительными суммами — получающиеся выбрасыванием вершин (будем называть эти вершины -вершинами, а соответствующие шестёрки — -шестёрками).
Рёбра между двумя -вершинами будем называть -рёбрами, между двумя -вершинами — -рёбрами, а рёбра, соединяющие -вершину с -вершиной, — -рёбрами. Из старой расстановки чисел на рёбрах, соединяющих вершины множества , получим новую расстановку, заменив все числа на -рёбрах на число , равное их среднему арифметическому, и аналогично заменив все числа на -рёбрах на их среднее арифметическое , а все числа на -рёбрах на их среднее арифметическое . Очевидно, , , , так как все старые числа по модулю не превосходят .
Лемма. Подграф с новыми числами на рёбрах удовлетворяет условию с той же константой .
Доказательство. Заметим, что для каждого -ребра есть одно и то же количество -шестёрок, в которые входят оба его конца. И наоборот, для любой -шестёрки среди рёбер между её вершинами есть одно и то же количество -рёбер. То же верно для -рёбер и для -рёбер. Значит, сумма чисел на рёбрах в -шестёрке в новой расстановке есть среднее сумм по всем -шестёркам в старой расстановке, то есть среднее нескольких чисел, не больших ; значит, . Аналогичное утверждение верно для сумм в -шестёрках. Лемма доказана.
Далее изучаем новую расстановку. Рассмотрим случаи.
Случай . Иными словами, есть ровно одна -шестёрка, на которой пятнадцать -рёбер, и шесть -шестёрок, на каждой из которых десять -рёбер и пять -рёбер. Имеем систему неравенств:
Умножим первое на , сложим со вторым, умноженным на , получим , откуда .
Случай . Теперь у нас две -вершины и пять -вершин, то есть на -шестёрке есть десять -рёбер и пять -рёбер, а на -шестёрке — шесть -рёбер, восемь -рёбер и одно -ребро. Имеем
Исключая , получаем , значит, .
Случай . Аналогично предыдущему, имеем
Избавляясь на этот раз от , получаем , откуда .
Случаи сводятся к рассмотренным умножением всех чисел на , что ведёт к замене . Итак, оценка доказана.
Пример. Любое число вершин от двух до объявим вершинами типа , остальные — вершинами типа . На всех рёбрах между двумя вершинами типа напишем число , на всех остальных — число . Тогда, если в шестёрке вершин хотя бы пять -вершин, то сумма в ней не больше , а иначе — не меньше .