Задача зі щасливим кінцем

Задача зі щасливим кінцем: будь-яка множина з п'яти точок містить вершини опуклого чотирикутника.

Задача зі щасливим кінцем — твердження про те, що будь-яка множина з п'яти точок на площині в загальному положенні має підмножину з чотирьох точок, які є вершинами опуклого чотирикутника.

Історія

Цей результат комбінаторної геометрії названий Палом Ердешем «задачею зі щасливим кінцем», оскільки розв'язування проблеми завершилося весіллям Дьєрдя Секереша і Естер Клейн (угор. 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\geq 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)

Література

• 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, архів оригіналу за 19 лютого 2019, процитовано 28 лютого 2020.
• 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. (ред.), 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. (ред.), Convex Polytopes, Graduate Texts in Mathematics, т. 221 (вид. 2nd), 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, Congressus Numerantium, т. 1, 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, архів оригіналу за 8 грудня 2008, процитовано 28 лютого 2020.
• 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, архів оригіналу за 21 січня 2001 {{citation}}: Недійсний |deadlink=404 (довідка).
• Scheinerman, Edward R.; Wilf, Herbert S. (1994), The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability, The American Mathematical Monthly, Mathematical Association of America, 101 (10): 939—943, doi:10.2307/2975158, JSTOR 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, архів оригіналу за 13 грудня 2019, процитовано 28 лютого 2020.
• 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, архів оригіналу за 3 березня 2016, процитовано 28 лютого 2020.

Посилання

• Happy ending problem [Архівовано 25 вересня 2006 у Wayback Machine.] and Ramsey-theoretic proof of the Erdős-Szekeres theorem [Архівовано 25 вересня 2006 у Wayback Machine.] on PlanetMath
• Weisstein, Eric W. Happy End Problem(англ.) на сайті Wolfram MathWorld.