Задача со счастливым концом — утверждение о том, что любое множество из пяти точек на плоскости в общем положенииВ данном контексте общее положение означает, что никакие три точки не лежат на одной прямой. имеет подмножество из четырёх точек, которые являются вершинами выпуклого четырёхугольника.
История
Этот результат комбинаторной геометрии назван Палом Эрдёшем «задачей со счастливым концом», поскольку решение проблемы завершилось свадьбой Дьёрдя Секереша и Эстер Клейн. Известна также как «теорема Эрдёша — Секереша о выпуклых многоугольниках».
Обобщения результата на произвольное число точек являются предметом интереса математиков XX и XXI веков.
Доказательство Если не менее четырёх точек образуют выпуклую оболочку, в качестве выпуклого четырёхугольника можно выбрать любой набор из четырёх точек оболочки. В противном случае имеется треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырёхугольник.
Многоугольники с произвольным числом вершин Эрдёш и Секереш обобщили этот результат на произвольное число точек, что является оригинальным развитием теории Рамсея. Они также выдвинули «гипотезу Эрдёша — Секереша» — точную формулу для максимального числа вершин выпуклого многоугольника, обязательно существующего в множестве из заданного числа точек в общем положении.
В доказано следующее обобщение: для любого натурального , всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество точек, которые являются вершинами выпуклого многоугольника. Это доказательство появилось в той же статье, где доказывается теорема Эрдёша — Секереша о монотонных подпоследовательностях в числовых последовательностях.
Размер множества как функция числа вершин многоугольника Пусть означает минимальное , для которого любое множество из точек в общем положении содержит выпуклый -угольник. Известно, что: , очевидно. , доказала Эстер Секереш. , согласно , это первым доказал Э. Макаи; первое опубликованное доказательство появилось в . Множество из восьми точек, не содержащее выпуклый пятиугольник, на иллюстрации показывает, что ; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый пятиугольник. , это было доказано в . В работе реализован сокращённый компьютерный перебор возможных конфигураций из 17 точек. Значения неизвестны для .
Гипотеза Эрдёша — Секереша о минимальном числе точек Исходя из известных значений для , Эрдёш и Секереш предположили, что: для всех .
Эта гипотеза не доказана, но известны оценки сверху и снизу.
Оценки скорости роста f(N) Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством: ,
Однако наилучшая известная оценка сверху при не является близкой: , (использованы биномиальные коэффициенты).
Вариации и обобщения
Пустые многоугольники Интересен также вопрос о том, содержит ли достаточно большое множество точек в общем положении пустой выпуклый четырёхугольник, пятиугольник, и так далее. То есть многоугольник, не содержащий внутренних точек.
Если внутри четырёхугольника, существующего согласно теореме со счастливым концом, есть точка, то, соединив эту точку с двумя вершинами диагонали, мы получим два четырёхугольника, один из которых выпуклый и пустой. Таким образом, пять точек в общем положении содержат пустой выпуклый четырёхугольник, как видно на иллюстрации. Любые десять точек в общем положении содержит пустой выпуклый пятиугольник . Однако существуют сколь угодно большие множества точек в общем положении, которые не содержат пустой выпуклый семиугольник.
Таким образом, задача о пустых многоугольниках не является проблемой теории Рамсея и в принципе решена.
Вопрос о существовании пустого шестиугольника долгое время оставался открытым. Но сначала в и было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник, потом оценку сверху довели до f(9) (предположительно 129), а оценку снизу — до 30 точек.. И, наконец, в 2024 году получен окончательный результат — 30-точечная конфигурация обязательно содержит пустой шестиугольник.
Примечания
Литература
. . . Reprinted in: . . . . . . . . . . . . . . . .
Ссылки Happy ending problem and Ramsey-theoretic proof of the Erdős-Szekeres theorem on PlanetMath
Категория:Комбинаторная геометрия Категория:Теория Рамсея Категория:Планиметрия Категория:Многоугольники Категория:Математические задачи Категория:Пал Эрдёш