Описание: За разгадку задачи о счастливом конце обещают $500, но награда всё ещё не нашла своего гения...
В начале 1930-х годов молодые учёные математики в Будапеште организовывали регулярные встречи для обсуждения сложных задач. В этом кружке работали Пол Эрдёш, Джордж Секереш и Эстер Кляйн. Кляйн предложила коллегам интересную геометрическую задачу с точками. Этот, казалось бы, простой вопрос стал началом многолетнего исследования, которое продолжается почти столетие.
Суть задачи: на плоскости расставлены пять точек в произвольном порядке, при условии что никакие три не лежат на одной линии. Требуется доказать, что среди них обязательно найдутся четыре точки, образующие выпуклый четырёхугольник.
Выпуклость играет ключевую роль. Если взять произвольные четыре точки, одна из них может оказаться внутри треугольника, образованного тремя другими. В этом случае все четыре точки не смогут служить вершинами выпуклого четырёхугольника. Поэтому гарантировать такую фигуру для четырёх точек невозможно.
Добавление пятой точки кардинально меняет ситуацию. Независимо от расположения пяти точек (при соблюдении исходного условия), подходящие четыре всегда существуют. Кляйн предложила наглядное геометрическое доказательство с использованием образа натянутой резинки.
Представим точки как штырьки на листе. Натянув вокруг них резинку и отпустив, она прижмётся к самым внешним штырькам, образуя выпуклую оболочку. Натяжение не позволит ей прогнуться внутрь.
Возможны три сценария: резинка коснётся пяти, четырёх или трёх штырьков. Двух касаний быть не может, так как это означал бы расположение всех точек на одной прямой, что запрещено условиями.
Если резинка касается четырёх точек, задача уже решена: эти точки образуют выпуклый четырёхугольник, а пятая лежит внутри. При охвате всех пяти точек получается выпуклый пятиугольник. Убрав любую вершину, четыре оставшиеся сохранят выпуклое расположение.
Сложнее анализировать случай, когда резинка касается только трёх точек. Они образуют треугольник, а две остальные точки находятся внутри. Необходимо доказать, что две внутренние точки вместе с двумя вершинами треугольника всё равно позволяют образовать выпуклый четырёхугольник.
Проведём прямую через обе внутренние точки. Эта прямая разбивает плоскость на две части. По крайней мере две вершины внешнего треугольника окажутся по одну сторону от этой линии. Выбрав эти две вершины и обе внутренние точки, получаем четыре точки в выпуклом положении.
Почему это работает? Одна из четырёх точек попадает внутрь треугольника, образованного остальными тремя, только при определённой конфигурации. Внешние вершины находятся на границе выпуклой оболочки всего набора, поэтому внутри они оказаться не могут. Две внутренние точки разделены проведённой через них прямой, так что ни одна из них не оказывается запёртой. В результате все четыре становятся вершинами выпуклого четырёхугольника.
Решив задачу для пяти точек, математики задались естественным вопросом: сколько точек нужно для гарантии выпуклого пятиугольника? Шестиугольника? Существует ли конечное число для любого количества вершин?
В 1935 году Эрдёш и Секереш ответили на этот вопрос. Они доказали, что для каждого натурального числа n существует конечное количество точек, при превышении которого выпуклый n-угольник неизбежен, если никакие три точки не лежат на одной прямой. Иными словами, при достаточно большом наборе невозможно избежать нужной выпуклой конфигурации.
Задача получила название "happy ending problem" (задача о счастливом конце). Это название, придуманное Эрдёшем, отсылает к биографии авторов. Эстер Кляйн и Джордж Секереш познакомились на этих встречах, сблизились и поженились в 1937 году.
Их история продолжилась на фоне войны и преследования евреев. Супруги эмигрировали и пережили военные годы в Шанхае как беженцы, где родился их первый сын. В 1948 году семья переехала в Австралию, где Секереш развивал свою математическую деятельность, а Эстер преподавала геометрические задачи.
Головоломка оказалась связана с более общей идеей. Эрдёш и Секереш применили теорему Фрэнка Рамсея. Это привело к развитию теории Рамсея — раздела комбинаторики, который исследует неизбежное появление упорядоченных структур в достаточно больших наборах.
Основную идею легко объяснить на примере вечеринки. Имеется группа людей, где каждая пара либо знакома, либо нет. На маленькой вечеринке можно подобрать гостей так, чтобы не было ни крупной группы взаимных знакомых, ни крупной группы незнакомцев.
Но с ростом числа гостей свобода сокращается. Начиная с определённого размера, обязательно найдётся группа участников, либо все знающих друг друга, либо все друг друга не знающих. Требуемая гарантированная группа больше — приглашаем больше людей.
Задача Эрдёша-Секереша работает по аналогичному принципу. Точки можно размещать без видимого порядка, однако после определённого количества появится группа в выпуклом положении. Теория Рамсея изучает именно такие ситуации, когда расширение системы делает определённые структуры неизбежными независимо от расположения элементов.
Основная сложность начинается после доказательства существования порога. Теорема гарантирует появление нужной конфигурации при достаточно большом количестве элементов, но не всегда указывает минимальное число. Для задачи Эрдёша-Секереша поиск точных границ оказался намного труднее, чем доказательство самого существования границы.
Для четырёхугольника минимальный порог составляет пять точек. Четырёх недостаточно, а среди любых пяти точек в общем положении всегда найдутся четыре в выпуклом положении.
Для пятиугольника минимальное число равно девяти. Существуют восьмиточечные конфигурации без выпуклого пятиугольника, но девять гарантируют его. По данным базы задач Эрдёша, результат f(5) = 9 получили Пал Туран и Эндре Макаи.
Следующий случай был намного сложнее. Для выпуклого шестиугольника точный ответ удалось найти только с помощью компьютера. Джордж Секереш и Линдси Питерс проанализировали конфигурации и установили, что 17 точек в общем положении всегда содержат шесть в выпуклом положении. При 16 точках можно найти расположение без выпуклого шестиугольника. Это исследование проведено в 2006 году и опубликовано после смерти Секереша.
Числа 5, 9 и 17 образуют замечательную последовательность: 5 = 2² + 1, 9 = 2³ + 1, 17 = 2⁴ + 1.
Эрдёш и Секереш выдвинули предположение, что закономерность продолжается для любого количества вершин. Если f(n) обозначает минимальное число точек, гарантирующих n точек в выпуклом положении, гипотеза имеет вид:
f(n) = 2^(n−2) + 1
Важно различать доказанную нижнюю границу и саму гипотезу. В 1960 году Эрдёш и Секереш доказали, что f(n) не может быть меньше 2^(n−2) + 1. Они также предположили, что эта нижняя граница является точным ответом. Для n = 4, 5 и 6 формула совпадает с известными значениями, но для больших n общего доказательства нет.
Ранние результаты давали намного более высокие верхние оценки. Работа 1935 года показала, что достаточно C(2n−4, n−2) + 1 точек (где C — биномиальный коэффициент). При больших n эта величина растёт примерно как 4^n. Нижняя граница растёт как 2^n, поэтому между оценками долго оставался огромный разрыв.
В 2016 году удалось значительно сократить этот разрыв. Эндрю Сук доказал асимптотическую оценку f(n) = 2^(n+o(n)). Символ o(n) обозначает добавку, растущую медленнее самого n. Результат показывает, что показатель степени растёт примерно как n, а не как 2n. Формула приблизила верхнюю границу к предполагаемому ответу 2^(n−2) + 1, но полностью гипотезу не доказала.
Поэтому точные ответы для случаев с большим числом вершин остаются неизвестными. Математики знают минимальные значения для четырёх, пяти и шести вершин, умеют строить конфигурации, определяющие нижнюю границу, и получили асимптотический порядок роста, почти совпадающий с гипотезой. Однако доказательство равенства f(n) = 2^(n−2) + 1 для всех n по-прежнему остаётся открытым вопросом. Эрдёш назначил премию в $500 за решение, которая до сих пор не присуждена.
