Перегляд вихідного коду сторінки Задача зі щасливим кінцем

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

== Історія ==
Цей результат [[Комбінаторна геометрія|комбінаторної геометрії]] названий [[Пал Ердеш|Палом Ердешем]] «задачею зі щасливим кінцем», оскільки розв'язування проблеми завершилося весіллям [[Дьєрдь Секереш|Дьєрдя Секереша]] і {{Нп|Естер Секереш|Естер Клейн|en|Esther Szekeres}} ({{Lang-hu|Eszter Klein}}<span>).</span> Відома також як ''«теорема Ердеша&nbsp;— Секереша про опуклі багатокутники».''

Узагальнення результату на довільне число точок є предметом інтересу математиків XX і XXI століть.

== Доведення ==
Якщо не менше чотирьох точок утворюють [[Опукла оболонка|опуклу оболонку]], як опуклий чотирикутник можна вибрати будь-який набір з чотирьох точок оболонки. В іншому випадку є трикутник і дві точки всередині нього. Пряма, що проходить через дві внутрішні точки, в силу загального положення точок не перетинає одну зі сторін трикутника. Вершини цієї сторони і дві внутрішні точки утворюють опуклий чотирикутник.

== Багатокутники з довільним числом вершин ==
Ердеш і Секереш узагальнили цей результат на довільне число точок, що є оригінальним розвитком [[Теорія Рамсея|теорії Рамсея]]. Вони також висунули «гіпотезу Ердеша&nbsp;— Секереша»&nbsp;— точну формулу для максимального числа вершин опуклого багатокутника, який обов'язково існує у множині з заданого числа точок у загальному положенні.
[[Файл:8-points-no-pentagon.svg|міні| Вісім точок у загальному положенні для яких немає опуклого п'ятикутника. ]]
В {{Harvard citation|Erdős|Szekeres|1935}} доведено таке узагальнення: для будь-якого натурального <math>N</math>, будь-яка досить велика множина точок у загальному положенні на площині має підмножину <math>N</math> точок, які є вершинами опуклого багатокутника. Це доведення з'явилося в тій самій статті, де доводиться [[Теорема Ердеша — Секереша|теорема Ердеша&nbsp;— Секереша]] про монотонні підпослідовності в числових послідовностях.

== Розмір множини як функція числа вершин багатокутника ==
Нехай <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>, згідно з {{Harvard citation|Erdős|Szekeres|1935}} це першим довів Е. Макао; перше опубліковане доведення з'явилося в {{Harvard citation|Kalbfleisch|Kalbfleisch|Stanton|1970}} Множина з восьми точок, що не містить опуклого п'ятикутника, на ілюстрації показує, що <math>f(5) > 8</math>; складніше довести, що будь-яка множина з дев'яти точок у загальному положенні містить опуклий п'ятикутник.
* <math>f(6) = 17</math>, це було доведено в {{Harvard citation|Szekeres|Peters|2006}}. У роботі реалізовано скорочений комп'ютерний перебір можливих конфігурацій з 17 точок.
* Значення <math>f(N)</math> невідомі для <math>N > 6</math>.

== Гіпотеза Ердеша&nbsp;— Секереша про мінімальне число точок ==
Виходячи з відомих значень <math>f(N)</math> для <math>N = 3, 4, 5</math>, Ердеш і Секереш припустили, що:

: <math> f(N) = 1 + 2^{N-2} </math> для всіх <math>N</math>.

Ця гіпотеза не доведена, але відомі оцінки зверху і знизу.

== Оцінки швидкості росту <math>f(N)</math> ==
Конструктивною побудовою автори гіпотези зуміли пізніше довести оцінку знизу, що збігається з гіпотетичною рівністю:

: <math>f(N) \geq 1 + 2^{N-2}</math>, {{Harvard citation|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>, {{Harvard citation|Tóth|Valtr|2005}}

(використано [[Біноміальний коефіцієнт|біноміальні коефіцієнти]]).

== Порожні багатокутники ==
Цікаве також питання про те, чи містить досить велика кількість точок у загальному положенні ''порожній'' опуклий чотирикутник, [[п'ятикутник]] і так далі. Тобто багатокутник, який не містить внутрішніх точок.

Якщо всередині чотирикутника, що існує відповідно до теореми зі щасливим кінцем, є точка, то, з'єднавши цю точку з двома вершинами [[Діагональ|діагоналі]], ми отримаємо два чотирикутники, один з яких опуклий і порожній. Таким чином, п'ять точок в загальному положенні містять порожній опуклий чотирикутник, як видно на ілюстрації. Будь-які десять точок в загальному положенні містять порожній опуклий п'ятикутник {{Harvard citation|Harborth|1978}}. Однак існують як завгодно великі множини точок у загальному положенні, які не містять порожнього опуклого [[Правильний семикутник|семикутника]]. {{Harvard citation|Horton|1983}}

Таким чином, задача про порожні багатокутники не є проблемою [[Теорія Рамсея|теорії Рамсея]] і в принципі розв'язана.

Питання про існування порожнього [[шестикутник]]а довгий час залишалося відкритим. Але в {{Harvard citation|Nicolás|2007}} і {{Harvard citation|Gerken|2008}} було доведено, що будь-яка досить велика множина точок у загальному положенні містить порожній шестикутник. Сьогодні відомо, що ця множина має містити не більше ''f''(9) (імовірно 129) і не менше 30 точок. {{Harvard citation|Overmars|2003}}

== Примітки ==
{{Reflist}}

== Література ==
{{refbegin|2}}
* {{citation
 | last1 = Chung | first1 = F.R.K. | author1-link = Фен Чанг
 | last2 = Graham | first2 = R.L. | author2-link = Рональд Грем
 | 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 = Пал Ердеш
 | last2 = Szekeres
 | first2 = G.
 | author2-link = Дьйордь Секереш
 | 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
 | accessdate = 28 лютого 2020
 | archive-date = 19 лютого 2019
 | archive-url = https://web.archive.org/web/20190219183414/http://www.numdam.org/item/?id=CM_1935__2__463_0
 }}.
* {{citation
 | last1 = Erdős | first1 = P. | author1-link = Пал Ердеш
 | last2 = Szekeres | first2 = G. | author2-link = Дьйордь Секереш
 | 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 = Пал Ердеш
 | 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 = Бранко Ґрюнбаум
 | edition = 2nd
 | editor1-last = Kaibel | editor1-first = Volker
 | editor2-last = Klee | editor2-first = Victor | editor2-link = Віктор Клі
 | editor3-last = Ziegler | editor3-first = Günter M. | editor3-link = Ґюнтер Ціґлер
 | isbn = 0-387-00424-6
 | publisher = [[Springer Science+Business Media|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 = Деніел Клейтман
 | 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
 | accessdate = 28 лютого 2020
 | archive-date = 8 грудня 2008
 | archive-url = https://web.archive.org/web/20081208054423/http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html
 }}.
* {{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 = Маркус Хендрік Овермарс
 | 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|deadlink=404}}.
* {{citation
 | last1 = Scheinerman | first1 = Edward R.
 | last2 = Wilf | first2 = Herbert S.
 | doi = 10.2307/2975158
 | issue = 10
 | journal = [[The 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 = Дьйордь Секереш
 | 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
 | accessdate = 28 лютого 2020
 | archive-date = 13 грудня 2019
 | archive-url = https://web.archive.org/web/20191213025301/http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html
 }}.
* {{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
 | accessdate = 28 лютого 2020
 | archive-date = 3 березня 2016
 | archive-url = https://web.archive.org/web/20160303173817/http://kam.mff.cuni.cz/~valtr/h.ps
 }}.
{{refend}}

== Посилання ==
* [http://planetmath.org/encyclopedia/HappyEndingProblem.html Happy ending problem] {{Webarchive|url=https://web.archive.org/web/20060925032614/http://planetmath.org/encyclopedia/HappyEndingProblem.html |date=25 вересня 2006 }} and [http://planetmath.org/encyclopedia/RamseyTheoreticProofOfTheErdHosSzekeresTheorem.html Ramsey-theoretic proof of the Erdős-Szekeres theorem] {{Webarchive|url=https://web.archive.org/web/20060925032736/http://planetmath.org/encyclopedia/RamseyTheoreticProofOfTheErdHosSzekeresTheorem.html |date=25 вересня 2006 }} on [[PlanetMath]]
* {{MathWorld|urlname=HappyEndProblem|title=Happy End Problem}}
[[Категорія:Планіметрія]]
[[Категорія:Теорія Ремзі]]
[[Категорія:Дискретна геометрія]]