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

[[Файл:Happy-End-problem.svg|thumb|300px|Задача со счастливым концом: любое множество из пяти точек содержит вершины выпуклого четырёхугольника.]]
'''Задача со счастливым концом''' — утверждение о том, что любое множество из пяти точек на плоскости в [[Общее положение|общем положении]]<ref>В данном контексте общее положение означает, что никакие три точки не лежат на одной прямой.</ref> имеет подмножество из четырёх точек, которые являются вершинами [[Выпуклый многоугольник|выпуклого]] [[Четырёхугольник|четырёхугольника]].

==История==

Этот результат [[Комбинаторная геометрия|комбинаторной геометрии]] назван [[Эрдёш, Пал|Палом Эрдёшем]] «задачей со счастливым концом», поскольку решение проблемы завершилось свадьбой [[Секереш, Дьёрдь|Дьёрдя Секереша]] и {{нп2|Секереш, Эстер|Эстер Клейн|hu|Szekeres Eszter|Eszter Klein}}. 
Известна также как «''теорема Эрдёша — Секереша о выпуклых многоугольниках''».

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

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

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

[[Файл:8-points-no-pentagon.svg|thumb|Восемь точек в общем положении для которых нет выпуклого пятиугольника.]]
В {{harv|Erdős|Szekeres|1935}} доказано следующее обобщение: для любого натурального <math>N</math>, всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество <math>N</math> точек, которые являются вершинами выпуклого многоугольника. Это доказательство появилось в той же статье, где доказывается [[Теорема Эрдёша — Секереша|теорема Эрдёша — Секереша]] о монотонных подпоследовательностях в числовых последовательностях.

== Размер множества как функция числа вершин многоугольника ==
Пусть <math>f(N)</math> означает минимальное <math>M</math>, для которого любое множество из <math>M</math> точек в общем положении содержит выпуклый <math>N</math>-угольник. Известно, что:
* <math>f(3) = 3</math>, очевидно.
* <math>f(4) = 5</math>, доказала Эстер Секереш.
* <math>f(5) = 9</math>, согласно {{harv|Erdős|Szekeres|1935}}, это первым доказал Э. Макаи; первое опубликованное доказательство появилось в {{harv|Kalbfleisch|Kalbfleisch|Stanton|1970}}. Множество из восьми точек, не содержащее выпуклый пятиугольник, на иллюстрации показывает, что <math>f(5) > 8</math>; сложнее доказать, что любое множество из девяти точек в общем положении содержит выпуклый пятиугольник.
* <math>f(6) = 17</math>, это было доказано в {{harv|Szekeres|Peters|2006}}. В работе реализован сокращённый компьютерный перебор возможных конфигураций из 17 точек.
* Значения <math>f(N)</math> неизвестны для <math>N > 6</math>.

== Гипотеза Эрдёша — Секереша о минимальном числе точек ==
Исходя из известных значений <math>f(N)</math> для <math>N = 3, 4, 5</math>, Эрдёш и Секереш предположили, что:
: <math> f(N) = 1 + 2^{N-2} </math> для всех <math>N</math>.

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

== Оценки скорости роста f(N) ==
Конструктивным построением авторы гипотезы сумели позднее доказать оценку снизу, совпадающую с гипотетическим равенством:
: <math>f(N) \geq 1 + 2^{N-2}</math>, {{harv|Erdős|Szekeres|1961}}

Однако наилучшая известная оценка сверху при <math>N \ge 7</math> не является близкой:
: <math>f(N) \leq {2N-5 \choose N-2} + 1 = O\left(\frac{4^N}{\sqrt N}\right)</math>, {{harv|Tóth|Valtr|2005}}
(использованы [[биномиальные коэффициенты]]).

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

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

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

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

Вопрос о существовании пустого [[Шестиугольник|шестиугольника]] долгое время оставался открытым.
Но сначала в {{harv|Nicolás|2007}} и {{harv|Gerken|2008}} было доказано, что всякое достаточно большое множество точек в общем положении содержит пустой шестиугольник, потом оценку сверху довели до ''f''(9) (предположительно 129), а оценку снизу — до 30 точек.{{harv|Overmars|2003}}.
И, наконец, в 2024 году получен окончательный результат — 30-точечная конфигурация обязательно содержит пустой шестиугольник.

== Примечания ==
{{примечания}}

== Литература ==
{{refbegin|2}}
* {{citation
 | last1 = Chung | first1 = F.R.K. | author1-link = Fan Chung
 | last2 = Graham | first2 = R.L. | author2-link = Ronald Graham
 | doi = 10.1007/PL00009353
 | journal = Discrete and Computational Geometry
 | pages = 367–371
 | issue = 3
 | title = Forced convex n-gons in the plane
 | volume = 19
 | year = 1998}}.
* {{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Szekeres | first2 = G. | author2-link = George Szekeres
 | journal = Compositio Math
 | pages = 463–470
 | title = A combinatorial problem in geometry
 | url = http://www.numdam.org/item?id=CM_1935__2__463_0
 | volume = 2
 | year = 1935}}.
* {{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Szekeres | first2 = G. | author2-link = George Szekeres
 | journal = Ann. Univ. Sci. Budapest. Eötvös Sect. Math.
 | pages = 53–62
 | title = On some extremum problems in elementary geometry
 | volume = 3–4
 | year = 1961}}. Reprinted in: {{citation
 | last = Erdős | first = P. | author-link = Paul Erdős
 | editor-last = Spencer | editor-first = J.
 | location = Cambridge, MA
 | pages = 680–689
 | publisher = MIT Press
 | title = The Art of Counting: Selected Writings
 | year = 1973}}.
* {{citation
 | last = Gerken | first = Tobias
 | doi = 10.1007/s00454-007-9018-x
 | issue = 1–3
 | journal = Discrete and Computational Geometry
 | pages = 239–272
 | title = Empty convex hexagons in planar point sets
 | volume = 39
 | year = 2008}}.
* {{citation
 | last = Grünbaum | first = Branko | authorlink = Branko Grünbaum
 | edition = 2nd
 | editor1-last = Kaibel | editor1-first = Volker
 | editor2-last = Klee | editor2-first = Victor | editor2-link = Victor Klee
 | editor3-last = Ziegler | editor3-first = Günter M. | editor3-link = Günter M. Ziegler
 | isbn = 0-387-00424-6
 | publisher = [[Springer-Verlag]]
 | series = Graduate Texts in Mathematics
 | title = Convex Polytopes
 | volume = 221
 | year = 2003}}.
* {{citation
 | last = Harborth | first = Heiko
 | issue = 5
 | journal = Elem. Math.
 | pages = 116–118
 | title = Konvexe Fünfecke in ebenen Punktmengen
 | volume = 33
 | year = 1978}}.
* {{citation
 | doi = 10.4153/CMB-1983-077-8
 | last = Horton | first = J. D.
 | issue = 4
 | journal = [[Canadian Mathematical Bulletin]]
 | pages = 482–484
 | title = Sets with no empty convex 7-gons
 | volume = 26
 | year = 1983}}.
* {{citation
 | last1 = Kalbfleisch | first1 = J.D.
 | last2 = Kalbfleisch | first2 = J.G.
 | last3 = Stanton | first3 = R.G.
 | title = Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing
 | publisher = Louisiana State Univ.
 | location = Baton Rouge, La.
 | series = Congressus Numerantium
 | pages = 180–188
 | contribution = A combinatorial problem on convex regions
 | volume = 1
 | year = 1970}}.
* {{citation
 | last1 = Kleitman | first1 = D.J. | author1-link = Daniel Kleitman
 | last2 = Pachter | first2 = L.
 | doi = 10.1007/PL00009358
 | journal = Discrete and Computational Geometry
 | pages = 405–410
 | issue = 3
 | title = Finding convex sets among points in the plane
 | volume = 19
 | year = 1998}}.
* {{citation
 | last1 = Morris | first1 = W.
 | last2 = Soltan | first2 = V.
 | doi = 10.1090/S0273-0979-00-00877-6
 | journal = Bulletin of the American Mathematical Society
 | pages = 437–458
 | title = The Erdős-Szekeres problem on points in convex position—A survey
 | issue = 04
 | url = http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html
 | volume = 37
 | year = 2000}}.
* {{citation
 | last = Nicolás | first = Carlos M.
 | doi = 10.1007/s00454-007-1343-6
 | issue = 2
 | journal = Discrete and Computational Geometry
 | pages = 389–397
 | title = The empty hexagon theorem
 | volume = 38
 | year = 2007}}.
* {{citation
 | last = Overmars | first = M. | author-link = Mark Overmars
 | doi = 10.1007/s00454-002-2829-x
 | journal = Discrete and Computational Geometry
 | pages = 153–158
 | title = Finding sets of points without empty convex 6-gons
 | issue = 1
 | volume = 29
 | year = 2003}}.
* {{citation
 | last = Peterson | first = Ivars
 | journal = MAA Online
 | title = Planes of Budapest
 | url = http://www.maa.org/mathland/mathtrek_10_3_00.html
 | year = 2000|archiveurl=https://web.archive.org/web/20010121105100/http://www.maa.org/mathland/mathtrek_10_3_00.html|archivedate=2001-01-21|url-status=dead}}.
* {{citation
 | last1 = Scheinerman | first1 = Edward R.
 | last2 = Wilf | first2 = Herbert S.
 | doi = 10.2307/2975158
 | issue = 10
 | journal = [[American Mathematical Monthly]]
 | pages = 939–943
 | title = The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability
 | volume = 101
 | year = 1994
 | publisher = Mathematical Association of America
 | jstor = 2975158}}.
* {{citation
 | last1 = Szekeres
 | first1 = G.
 | author1-link = George Szekeres
 | last2 = Peters
 | first2 = L.
 | doi = 10.1017/S144618110000300X
 | journal = [[ANZIAM Journal]]
 | pages = 151–164
 | title = Computer solution to the 17-point Erdős-Szekeres problem
 | issue = 02
 | url = http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html
 | volume = 48
 | year = 2006
 }} {{Wayback|url=http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html |date=20191213025301 }}.
* {{citation
 | last1 = Tóth | first1 = G.
 | last2 = Valtr | first2 = P.
 | doi = 10.1007/PL00009363
 | journal = Discrete and Computational Geometry
 | pages = 457–459
 | title = Note on the Erdős-Szekeres theorem
 | issue = 3
 | volume = 19
 | year = 1998}}.
* {{citation
 | last1 = Tóth | first1 = G.
 | last2 = Valtr | first2 = P.
 | contribution = The Erdős-Szekeres theorem: upper bounds and related results
 | pages = 557–568
 | publisher = Mathematical Sciences Research Institute Publications, no. 52
 | title = Combinatorial and computational geometry
 | year = 2005}}.
* {{citation
 | last = Valtr | first = P.
 | title = On the empty hexagons
 | url = http://kam.mff.cuni.cz/~valtr/h.ps
 | year = 2006}}.
{{refend}}

== Ссылки ==
* [http://planetmath.org/encyclopedia/HappyEndingProblem.html Happy ending problem] {{Wayback|url=http://planetmath.org/encyclopedia/HappyEndingProblem.html |date=20060925032614 }} and [http://planetmath.org/encyclopedia/RamseyTheoreticProofOfTheErdHosSzekeresTheorem.html Ramsey-theoretic proof of the Erdős-Szekeres theorem] on [[PlanetMath]]
* {{mathworld | urlname = HappyEndProblem | title = Happy End Problem}}

[[Категория:Комбинаторная геометрия]]
[[Категория:Теория Рамсея]]
[[Категория:Планиметрия]]
[[Категория:Пал Эрдёш]]