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

Цей результат комбінаторної геометрії названий Палом Ердешем «задачею зі щасливим кінцем», оскільки розв'язування проблеми завершилося весіллям Дьєрдя Секереша і Естер Клейн (угор. Eszter Klein). Відома також як «теорема Ердеша — Секереша про опуклі багатокутники».

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

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

Ердеш і Секереш узагальнили цей результат на довільне число точок, що є оригінальним розвитком теорії Рамсея. Вони також висунули «гіпотезу Ердеша — Секереша» — точну формулу для максимального числа вершин опуклого багатокутника, який обов'язково існує у множині з заданого числа точок у загальному положенні.

Вісім точок у загальному положенні для яких немає опуклого п'ятикутника.

В (Erdős та Szekeres, 1935) доведено таке узагальнення: для будь-якого натурального ${\displaystyle N}$, будь-яка досить велика множина точок у загальному положенні на площині має підмножину ${\displaystyle N}$ точок, які є вершинами опуклого багатокутника. Це доведення з'явилося в тій самій статті, де доводиться теорема Ердеша — Секереша про монотонні підпослідовності в числових послідовностях.

Нехай ${\displaystyle f(N)}$ позначає мінімальне ${\displaystyle M}$, Для якого будь-яка множина з ${\displaystyle M}$ точок у загальному положенні містить опуклий ${\displaystyle N}$-кутник. Відомо що:

• ${\displaystyle f(3)=3}$, очевидно.
• ${\displaystyle f(4)=5}$, довела Естер Секереш.
• ${\displaystyle f(5)=9}$, згідно з (Erdős та Szekeres, 1935) це першим довів Е. Макао; перше опубліковане доведення з'явилося в (Kalbfleisch, Kalbfleisch та Stanton, 1970) Множина з восьми точок, що не містить опуклого п'ятикутника, на ілюстрації показує, що ${\displaystyle f(5)>8}$; складніше довести, що будь-яка множина з дев'яти точок у загальному положенні містить опуклий п'ятикутник.
• ${\displaystyle f(6)=17}$, це було доведено в (Szekeres та Peters, 2006). У роботі реалізовано скорочений комп'ютерний перебір можливих конфігурацій з 17 точок.
• Значення ${\displaystyle f(N)}$ невідомі для ${\displaystyle N>6}$.

Виходячи з відомих значень ${\displaystyle f(N)}$ для ${\displaystyle N=3,4,5}$, Ердеш і Секереш припустили, що:

${\displaystyle f(N)=1+2^{N-2}}$ для всіх ${\displaystyle N}$.

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

Конструктивною побудовою автори гіпотези зуміли пізніше довести оцінку знизу, що збігається з гіпотетичною рівністю:

${\displaystyle f(N)\geq 1+2^{N-2}}$, (Erdős та Szekeres, 1961)

Проте найкраща відома оцінка зверху при ${\displaystyle N\geq 7}$ не є близькою:

${\displaystyle 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)

• Happy ending problem and Ramsey-theoretic proof of the Erdős-Szekeres theorem on PlanetMath
• Weisstein, Eric W. Happy End Problem(англ.) на сайті Wolfram MathWorld.