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

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

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

Этот результат комбинаторной геометрии назван Палом Эрдёшем «задачей со счастливым концом» поскольку решение проблемы завершилось свадьбой Дьёрдя Секереша и Эстер Клейн (венг. Eszter Klein). Известна также как «теорема Эрдёша — Секереша о выпуклых многоугольниках».

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

Доказательство[править | править вики-текст]

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

Многоугольники с произвольным числом вершин[править | править вики-текст]

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

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

В (Erdős & Szekeres 1935) доказано следующее обобщение: для любого натурального N, всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество N точек, которые являются вершинами выпуклого многоугольника. Это доказательство появилось в той же статье, где доказывается теорема Эрдёша — Секереша о монотонных подпоследовательностях в числовых последовательностях.

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

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

  • f(3) = 3, очевидно.
  • f(4) = 5, доказала Эстер Секереш.
  • f(5) = 9, согласно (Erdős & Szekeres 1935), это первым доказал Э. Макаи; первое опубликованное доказательство появилось в (Kalbfleisch, Kalbfleisch & Stanton 1970). Множество из восьми точек не содержащее выпуклый пятиугольник на иллюстрации показывает, что f(5) > 8; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый многоугольник.
  • f(6) = 17, это было доказано в (Szekeres & Peters 2006). В работе реализован сокращённый компьютерный перебор возможных конфигураций из 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}, (Erdős & Szekeres 1961)

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

f(N) \leq {2N-5 \choose N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right), (Tóth & Valtr 2005)

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

Пустые многоугольники[править | править вики-текст]

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

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

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

Вопрос о существовании пустого шестиугольника долгое время оставался открытым. Но в (Nicolás 2007) и (Gerken 2008) } было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более f(9) (предположительно 129) и не менее 30 точек.(Overmars 2003).

Примечания[править | править вики-текст]

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

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]