Условие начинается с пяти точек. Их разрешено поставить на плоскости как угодно, но никакие три не должны лежать на одной прямой. Нужно доказать, что среди пяти точек обязательно найдутся четыре, которые образуют выпуклый четырёхугольник.
Выпуклость здесь важна. Если взять четыре произвольные точки, одна из них может оказаться внутри треугольника, построенного по трём остальным. Тогда все четыре точки нельзя использовать как вершины выпуклого четырёхугольника. Поэтому для четырёх точек нужная фигура не гарантирована.
Пятая точка полностью меняет задачу. Как бы ни расположить пять точек при соблюдении исходного условия, подходящая четвёрка обязательно найдётся. Кляйн предложила короткое геометрическое доказательство, которое удобно представить с помощью натянутой резинки.
Пусть вместо точек из листа выступают пять небольших штырьков. Натянем вокруг них резинку и отпустим. Резинка прижмётся к самым внешним штырькам и очертит выпуклую оболочку набора точек. Внутрь граница прогибаться не сможет, потому что натяжение удерживает её на внешних точках.
Возможны три случая. Резинка коснётся пяти, четырёх или трёх штырьков. Только двух касаний быть не может: тогда все точки пришлось бы расположить на одной прямой, что запрещено условием.
При четырёх касаниях задача уже решена. Эти точки на границе образуют выпуклый четырёхугольник, а пятая лежит внутри. Если резинка охватывает все пять точек, получается выпуклый пятиугольник. Достаточно убрать любую вершину, и четыре оставшиеся точки сохранят выпуклое положение.
Сложнее разобрать случай, когда наружу выходят только три точки. Они образуют треугольник, внутри которого находятся ещё две. Нужно доказать, что две внутренние точки вместе с двумя вершинами большого треугольника всё равно позволяют получить выпуклый четырёхугольник.
Проведём прямую через обе внутренние точки и продолжим её в обе стороны. Прямая разделит плоскость на две полуплоскости. По меньшей мере две из трёх вершин внешнего треугольника окажутся с одной стороны от проведённой линии. Возьмём эти две вершины и обе внутренние точки.
Четыре выбранные точки находятся в выпуклом положении. Для четырёх точек помешать этому может только одна конфигурация: одна точка должна попасть внутрь треугольника, образованного тремя другими. С внешними вершинами этого произойти не может, поскольку они лежат на границе выпуклой оболочки всего набора. Две внутренние точки разделены проведённой через них прямой относительно треугольников, которые можно составить с внешней парой, поэтому ни одна из внутренних точек не оказывается запертой внутри треугольника из остальных трёх. В результате все четыре становятся вершинами выпуклого четырёхугольника.
После решения задачи для пяти точек возник естественный следующий вопрос. Сколько точек потребуется, чтобы гарантировать выпуклый пятиугольник? А шестиугольник? Существует ли конечное число точек, которое неизбежно заставит появиться выпуклый многоугольник с любым заранее заданным количеством вершин?
Последний вопрос в 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 точек в выпуклом положении, гипотеза записывается так: f
= 2^(n−2) + 1. Здесь важно различать доказанную нижнюю границу и саму гипотезу. В 1960 году Эрдёш и Секереш доказали, что f
не может быть меньше 2^(n−2) + 1. Они также предположили, что нижняя граница всегда даёт точный ответ. Для n = 4, 5 и 6 формула совпадает с известными значениями, но для больших n общего доказательства пока нет. Первые результаты давали намного более высокую верхнюю границу. Работа 1935 года показала , что достаточно C(2n−4, n−2) + 1 точек, где C обозначает биномиальный коэффициент. При больших n эта величина растёт примерно как 4^n с поправкой на более медленный множитель. Нижняя граница при этом растёт примерно как 2^n, поэтому между двумя оценками долго сохранялся огромный разрыв.
В 2016 году удалось заметно сократить этот разрыв. Эндрю Сук доказал асимптотическую оценку f
= 2^(n+o). Запись o означает добавку, которая растёт медленнее самого n. Результат показывает, что показатель степени в основном растёт как n, а не как 2n, как следовало из старой верхней оценки порядка 4^n. Формула приблизила известную верхнюю границу к предполагаемому ответу 2^(n−2) + 1, но не доказала гипотезу для каждого конкретного n. Поэтому точные ответы после шестиугольника остаются неизвестными. Математики знают минимальные значения для четырёх, пяти и шести вершин, умеют строить конфигурации, задающие нижнюю границу для общего случая, и получили почти совпадающий с ней асимптотический порядок роста. Однако равенство f
= 2^(n−2) + 1 для всех n по-прежнему требует доказательства. За решение задачи Эрдёш назначил премию в $500, которая до сих пор не присуждена.