Задача со счастливым концом
Задача со счастливым концом — утверждение о том, что любое множество из пяти точек на плоскости в общем положении[1] имеет подмножество из четырёх точек, которые являются вершинами выпуклого четырёхугольника.
История
Этот результат комбинаторной геометрии назван Палом Эрдёшем «задачей со счастливым концом», поскольку решение проблемы завершилось свадьбой Дьёрдя Секереша и Эстер Клейн (венг. Eszter Klein). Известна также как «теорема Эрдёша — Секереша о выпуклых многоугольниках».
Обобщения результата на произвольное число точек являются предметом интереса математиков XX и XXI веков.
Доказательство
Если не менее четырёх точек образуют выпуклую оболочку, в качестве выпуклого четырёхугольника можно выбрать любой набор из четырёх точек оболочки. В противном случае имеется треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырёхугольник.
Многоугольники с произвольным числом вершин
Эрдёш и Секереш обобщили этот результат на произвольное число точек, что является оригинальным развитием теории Рамсея. Они также выдвинули «гипотезу Эрдёша — Секереша» — точную формулу для максимального числа вершин выпуклого многоугольника, обязательно существующего в множестве из заданного числа точек в общем положении.
В (Erdős & Szekeres 1935) доказано следующее обобщение: для любого натурального [math]\displaystyle{ N }[/math], всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество [math]\displaystyle{ N }[/math] точек, которые являются вершинами выпуклого многоугольника. Это доказательство появилось в той же статье, где доказывается теорема Эрдёша — Секереша о монотонных подпоследовательностях в числовых последовательностях.
Размер множества как функция числа вершин многоугольника
Пусть [math]\displaystyle{ f(N) }[/math] означает минимальное [math]\displaystyle{ M }[/math], для которого любое множество из [math]\displaystyle{ M }[/math] точек в общем положении содержит выпуклый [math]\displaystyle{ N }[/math]-угольник. Известно, что:
- [math]\displaystyle{ f(3) = 3 }[/math], очевидно.
- [math]\displaystyle{ f(4) = 5 }[/math], доказала Эстер Секереш.
- [math]\displaystyle{ f(5) = 9 }[/math], согласно (Erdős & Szekeres 1935), это первым доказал Э. Макаи; первое опубликованное доказательство появилось в (Kalbfleisch, Kalbfleisch & Stanton 1970). Множество из восьми точек, не содержащее выпуклый пятиугольник, на иллюстрации показывает, что [math]\displaystyle{ f(5) \gt 8 }[/math]; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый пятиугольник.
- [math]\displaystyle{ f(6) = 17 }[/math], это было доказано в (Szekeres & Peters 2006). В работе реализован сокращённый компьютерный перебор возможных конфигураций из 17 точек.
- Значения [math]\displaystyle{ f(N) }[/math] неизвестны для [math]\displaystyle{ N \gt 6 }[/math].
Гипотеза Эрдёша — Секереша о минимальном числе точек
Исходя из известных значений [math]\displaystyle{ f(N) }[/math] для [math]\displaystyle{ N = 3, 4, 5 }[/math], Эрдёш и Секереш предположили, что:
- [math]\displaystyle{ f(N) = 1 + 2^{N-2} }[/math] для всех [math]\displaystyle{ N }[/math].
Эта гипотеза не доказана, но известны оценки сверху и снизу.
Оценки скорости роста f(N)
Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством:
- [math]\displaystyle{ f(N) \geq 1 + 2^{N-2} }[/math], (Erdős & Szekeres 1961)
Однако наилучшая известная оценка сверху при [math]\displaystyle{ N \ge 7 }[/math] не является близкой:
- [math]\displaystyle{ f(N) \leq {2N-5 \choose N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right) }[/math], (Tóth & Valtr 2005)
(использованы биномиальные коэффициенты).
Пустые многоугольники
Интересен также вопрос о том, содержит ли достаточно большое множество точек в общем положении пустой выпуклый четырёхугольник, пятиугольник, и так далее. То есть многоугольник, не содержащий внутренних точек.
Если внутри четырёхугольника, существующего согласно теореме со счастливым концом, есть точка, то, соединив эту точку с двумя вершинами диагонали, мы получим два четырёхугольника, один из которых выпуклый и пустой. Таким образом, пять точек в общем положении содержат пустой выпуклый четырёхугольник, как видно на иллюстрации. Любые десять точек в общем положении содержит пустой выпуклый пятиугольник (Harborth 1978). Однако существуют сколь угодно большие множества точек в общем положении, которые не содержат пустой выпуклый семиугольник.(Horton 1983)
Таким образом, задача о пустых многоугольниках не является проблемой теории Рамсея и в принципе решена.
Вопрос о существовании пустого шестиугольника долгое время оставался открытым. Но в (Nicolás 2007) и (Gerken 2008) было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более f(9) (предположительно 129) и не менее 30 точек.(Overmars 2003).
Примечания
- ↑ В данном контексте общее положение означает, что никакие три точки не лежат на одной прямой.
Литература
- Chung, F.R.K. & Graham, R.L. (1998), Forced convex n-gons in the plane, Discrete and Computational Geometry Т. 19 (3): 367–371, DOI 10.1007/PL00009353.
- Erdős, P. & Szekeres, G. (1935), A combinatorial problem in geometry, Compositio Math Т. 2: 463–470, <http://www.numdam.org/item?id=CM_1935__2__463_0>.
- Erdős, P. & Szekeres, G. (1961), On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. Т. 3–4: 53–62. Reprinted in: Erdős, P. (1973), Spencer, J., ed., The Art of Counting: Selected Writings, Cambridge, MA: MIT Press, с. 680–689.
- Gerken, Tobias (2008), Empty convex hexagons in planar point sets, Discrete and Computational Geometry Т. 39 (1–3): 239–272, DOI 10.1007/s00454-007-9018-x.
- Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor & Ziegler, Günter M., eds., Convex Polytopes, vol. 221 (2nd ed.), Graduate Texts in Mathematics, Springer-Verlag, ISBN 0-387-00424-6.
- Harborth, Heiko (1978), Konvexe Fünfecke in ebenen Punktmengen, Elem. Math. Т. 33 (5): 116–118.
- Horton, J. D. (1983), Sets with no empty convex 7-gons, Canadian Mathematical Bulletin Т. 26 (4): 482–484, DOI 10.4153/CMB-1983-077-8.
- Kalbfleisch, J.D.; Kalbfleisch, J.G. & Stanton, R.G. (1970), A combinatorial problem on convex regions, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, vol. 1, Congressus Numerantium, Baton Rouge, La.: Louisiana State Univ., с. 180–188.
- Kleitman, D.J. & Pachter, L. (1998), Finding convex sets among points in the plane, Discrete and Computational Geometry Т. 19 (3): 405–410, DOI 10.1007/PL00009358.
- Morris, W. & Soltan, V. (2000), The Erdős-Szekeres problem on points in convex position—A survey, Bulletin of the American Mathematical Society Т. 37 (04): 437–458, doi:10.1090/S0273-0979-00-00877-6, <http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html>.
- Nicolás, Carlos M. (2007), The empty hexagon theorem, Discrete and Computational Geometry Т. 38 (2): 389–397, DOI 10.1007/s00454-007-1343-6.
- Overmars, M. (2003), Finding sets of points without empty convex 6-gons, Discrete and Computational Geometry Т. 29 (1): 153–158, DOI 10.1007/s00454-002-2829-x.
- Peterson, Ivars (2000), Planes of Budapest, MAA Online, <http://www.maa.org/mathland/mathtrek_10_3_00.html>.
- Scheinerman, Edward R. & Wilf, Herbert S. (1994), The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability, American Mathematical Monthly (Mathematical Association of America) . — Т. 101 (10): 939–943, DOI 10.2307/2975158.
- Szekeres, G. & Peters, L. (2006), Computer solution to the 17-point Erdős-Szekeres problem, ANZIAM Journal Т. 48 (02): 151–164, doi:10.1017/S144618110000300X, <http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html> Архивная копия от 13 декабря 2019 на Wayback Machine.
- Tóth, G. & Valtr, P. (1998), Note on the Erdős-Szekeres theorem, Discrete and Computational Geometry Т. 19 (3): 457–459, DOI 10.1007/PL00009363.
- Tóth, G. & Valtr, P. (2005), The Erdős-Szekeres theorem: upper bounds and related results, Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications, no. 52, с. 557–568.
- Valtr, P. (2006), On the empty hexagons, <http://kam.mff.cuni.cz/~valtr/h.ps>.
Ссылки
- Happy ending problem Архивная копия от 25 сентября 2006 на Wayback Machine and Ramsey-theoretic proof of the Erdős-Szekeres theorem on PlanetMath
- Weisstein, Eric W. Happy End Problem (англ.) на сайте Wolfram MathWorld.