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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

значит,

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

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

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

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

Рассмотрим произвольную окружность, разобьём её на дуги, пропорциональные весам кусков сыра. Тогда любой проведённый диаметр соответствует разрезанию не более чем двух кусков сыра (концы диаметра пересекают дуги в местах разреза), что кучки из кусков по обе стороны диаметра имеют равные массы. Осталось доказать, что один из таких диаметров даст также факт, что кучки по обе его стороны имеют одинаковую стоимость. Зафиксируем диаметр и прокрутим его по часовой стрелке на заметим что разность стоимостей куч сыра слева и справа от диаметра непрерывно изменялась и стала противоположной, значит, в некоторый момент она принимала значение что и требовалось.

Пусть Марина как-то покрасила кубики, а Катя как-то сложила из них куб. Пусть на поверхности куба синих и красных граней. Используя идею так называемой дискретной непрерывности, покажем, что Катя может постепенно привести куб к нужному ей виду. Заметим, что каждый из 8 кубиков можно повернуть так, чтобы все его грани, которые были снаружи, оказались внутри, и наоборот. Если сделать это со всеми восемью кубиками, то на поверхности окажутся как раз все те грани, которые изначально были внутри, то есть синих и красных. Заметим теперь, что каждый кубик можно поворачивать постепенно - так, чтобы за один ход две внешних грани оставались на месте и лишь третья заменялась на противоположную. При таком повороте количество синих граней на поверхности меняется не более, чем на Итак, изначально синих квадратов было в конце стало а при каждом действии менялось не более, чем на Поскольку число находится между и то в какой-то момент их было ровно

Давайте попробуем доказать, что в какой-то момент у квадратного трёхчлена будут целые корни. Для этого угадаем один из них. Если сумма коэффициентов многочлена равна 0, то есть корень У начального многочлена сумма коэффициентов равна 3, а у конечного сумма коэффициентов равна -199, при этом за одно действие ровно один из коэффициентов меняется на 1, значит, сумма коэффициентов меняется на 1. Но если она была положительной, а потом стала отрицательной, то в какой-то момент обязательно была равна 0. То есть в какой-то момент у нас был трёхчлен , один из корней которого равен 1! А по теореме Виета второй корень равен — тоже целому числу у трёхчлена 2 целых корня!