Задача со счастливым концом

Задача со счастливым концом — утверждение о том, что любое множество из пяти точек на плоскости в общем положении^[1] имеет подмножество из четырёх точек, которые являются вершинами выпуклого четырёхугольника.

История

Этот результат комбинаторной геометрии назван Палом Эрдёшем «задачей со счастливым концом», поскольку решение проблемы завершилось свадьбой Дьёрдя Секереша и Шаблон:Нп2. Известна также как «теорема Эрдёша — Секереша о выпуклых многоугольниках».

Обобщения результата на произвольное число точек являются предметом интереса математиков XX и XXI веков.

Доказательство

Если не менее четырёх точек образуют выпуклую оболочку, в качестве выпуклого четырёхугольника можно выбрать любой набор из четырёх точек оболочки. В противном случае имеется треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырёхугольник.

Многоугольники с произвольным числом вершин

Эрдёш и Секереш обобщили этот результат на произвольное число точек, что является оригинальным развитием теории Рамсея. Они также выдвинули «гипотезу Эрдёша — Секереша» — точную формулу для максимального числа вершин выпуклого многоугольника, обязательно существующего в множестве из заданного числа точек в общем положении.

Восемь точек в общем положении для которых нет выпуклого пятиугольника.

В Шаблон:Harv доказано следующее обобщение: для любого натурального $N$ , всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество $N$ точек, которые являются вершинами выпуклого многоугольника. Это доказательство появилось в той же статье, где доказывается теорема Эрдёша — Секереша о монотонных подпоследовательностях в числовых последовательностях.

Размер множества как функция числа вершин многоугольника

Пусть $f (N)$ означает минимальное $M$ , для которого любое множество из $M$ точек в общем положении содержит выпуклый $N$ -угольник. Известно, что:

$f (3) = 3$ , очевидно.
$f (4) = 5$ , доказала Эстер Секереш.
$f (5) = 9$ , согласно Шаблон:Harv, это первым доказал Э. Макаи; первое опубликованное доказательство появилось в Шаблон:Harv. Множество из восьми точек, не содержащее выпуклый пятиугольник, на иллюстрации показывает, что $f (5) > 8$ ; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый пятиугольник.
$f (6) = 17$ , это было доказано в Шаблон:Harv. В работе реализован сокращённый компьютерный перебор возможных конфигураций из 17 точек.
Значения $f (N)$ неизвестны для $N > 6$ .

Гипотеза Эрдёша — Секереша о минимальном числе точек

Исходя из известных значений $f (N)$ для $N = 3, 4, 5$ , Эрдёш и Секереш предположили, что:

f (N) = 1 + 2^{N - 2}

для всех

N

.

Эта гипотеза не доказана, но известны оценки сверху и снизу.

Оценки скорости роста f(N)

Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством:

f (N) \geq 1 + 2^{N - 2}

, Шаблон:Harv

Однако наилучшая известная оценка сверху при $N \geq 7$ не является близкой:

f (N) \leq (\binom{2 N - 5}{N - 2}) + 1 = O (\frac{4^{N}}{\sqrt{N}})

, Шаблон:Harv

(использованы биномиальные коэффициенты).

Вариации и обобщения

Пустые многоугольники

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

Если внутри четырёхугольника, существующего согласно теореме со счастливым концом, есть точка, то, соединив эту точку с двумя вершинами диагонали, мы получим два четырёхугольника, один из которых выпуклый и пустой. Таким образом, пять точек в общем положении содержат пустой выпуклый четырёхугольник, как видно на иллюстрации. Любые десять точек в общем положении содержит пустой выпуклый пятиугольник Шаблон:Harv. Однако существуют сколь угодно большие множества точек в общем положении, которые не содержат пустой выпуклый семиугольник.Шаблон:Harv

Таким образом, задача о пустых многоугольниках не является проблемой теории Рамсея и в принципе решена.

Вопрос о существовании пустого шестиугольника долгое время оставался открытым. Но сначала в Шаблон:Harv и Шаблон:Harv было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник, потом оценку сверху довели до f(9) (предположительно 129), а оценку снизу — до 30 точек.Шаблон:Harv. И, наконец, в 2024 году получен окончательный результат — 30-точечная конфигурация обязательно содержит пустой шестиугольник.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

↑ В данном контексте общее положение означает, что никакие три точки не лежат на одной прямой.

[1] В данном контексте общее положение означает, что никакие три точки не лежат на одной прямой.

[1]

Задача со счастливым концом

Содержание

История

Доказательство

Многоугольники с произвольным числом вершин

Размер множества как функция числа вершин многоугольника

Гипотеза Эрдёша — Секереша о минимальном числе точек

Оценки скорости роста f(N)

Вариации и обобщения

Примечания

Литература

Ссылки

Навигация

Задача со счастливым концом

История

Доказательство

Многоугольники с произвольным числом вершин

Размер множества как функция числа вершин многоугольника

Гипотеза Эрдёша — Секереша о минимальном числе точек

Оценки скорости роста f(N)

Вариации и обобщения

Примечания

Литература

Ссылки

Навигация

Поиск