Дискретная непрерывность

Рассмотрим граф, вершинами которого являются отмеченные точки, а рёбрами — проведённые отрезки.

Оценка. Докажем оценку Условие гласит, что в нашем полном графе есть как шестёрки вершин, сумма на рёбрах между которыми положительна, так и шестёрки, сумма на рёбрах между которыми отрицательна. Тогда найдутся две шестёрки, отличающиеся заменой только одной вершины, такие, что у одной из них сумма положительна, у другой отрицательна. В самом деле, возьмём шестёрку с положительной суммой, и будем превращать её в шестёрку с отрицательной суммой, меняя вершины по одной, — на каком-то шаге произошло изменение знака, шестёрки, которые были до и после этого шага – искомая пара.

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

Из изначальной расстановки чисел на рёбрах, соединяющих вершины множества получим новую расстановку, заменив все числа на -рёбрах на число равное их среднему арифметическому, и аналогично заменив все числа на -рёбрах на их среднее арифметическое а все числа на -рёбрах на их среднее арифметическое Очевидно, так как все старые числа по модулю не превосходят 1.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Подграф с новыми числами на рёбрах удовлетворяет условию с той же константой

Доказательство леммы. Заметим, что для каждого -рёбра есть одно и то же количество -шестёрок, в которые входят оба его конца. И наоборот, для любой -шестёрки среди 15 рёбер между её вершинами есть одно и то же количество -рёбер. То же верно для -рёбер и для -рёбер. Значит, сумма чисел на рёбрах в -шестёрке в новой расстановке есть среднее сумм по всем -шестёркам в старой расстановке, то есть среднее нескольких чисел, не больших – значит, Аналогичное утверждение верно для сумм в -шестёрках. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Далее изучаем новую расстановку. Рассмотрим случаи.

Случай Иными словами, есть ровно одна -шестёрка, на которой пятнадцать -рёбер, и шесть -шестёрок, на каждой из которых десять -рёбер и пять -рёбер. Имеем систему неравенств:

Умножим первое на сложим со вторым, умноженным на 3, получим откуда

Случай Теперь у нас две -вершины и пять -вершин, то есть на -шестёрке есть десять -рёбер и пять -рёбер, а на -шестёрке – шесть -рёбер, восемь -рёбер и одно -ребро. Имеем

Исключая получаем

значит,

Случай Аналогично предыдущему, имеем

Избавляясь на этот раз от получаем откуда

Случаи сводятся к рассмотренным умножением всех чисел на что ведёт к замене Итак, оценка доказана.

Пример. Любое число вершин от двух до 999995 объявим вершинами типа остальные – вершинами типа На всех рёбрах между двумя вершинами типа напишем число на всех остальных – число 1. Тогда, если в шестёрке вершин хотя бы пять -вершин, то сумма в ней не больше а иначе – не меньше