Задача зі щасливим кінцем — твердження про те, що будь-яка множина з п'яти точок на площині в загальному положенніВ даному контексті загальне положення означає, що ніякі три точки не лежать на одній прямій. має підмножину з чотирьох точок, які є вершинами опуклого чотирикутника.
Історія Цей результат комбінаторної геометрії названий Палом Ердешем «задачею зі щасливим кінцем», оскільки розв'язування проблеми завершилося весіллям Дьйордь Секереш і (). Відома також як «теорема Ердеша — Секереша про опуклі багатокутники».
Узагальнення результату на довільне число точок є предметом інтересу математиків XX і XXI століть.
Доведення Якщо не менше чотирьох точок утворюють опуклу оболонку, як опуклий чотирикутник можна вибрати будь-який набір з чотирьох точок оболонки. В іншому випадку є трикутник і дві точки всередині нього. Пряма, що проходить через дві внутрішні точки, в силу загального положення точок не перетинає одну зі сторін трикутника. Вершини цієї сторони і дві внутрішні точки утворюють опуклий чотирикутник.
Багатокутники з довільним числом вершин Ердеш і Секереш узагальнили цей результат на довільне число точок, що є оригінальним розвитком теорії Рамсея. Вони також висунули «гіпотезу Ердеша — Секереша» — точну формулу для максимального числа вершин опуклого багатокутника, який обов'язково існує у множині з заданого числа точок у загальному положенні.
В доведено таке узагальнення: для будь-якого натурального , будь-яка досить велика множина точок у загальному положенні на площині має підмножину точок, які є вершинами опуклого багатокутника. Це доведення з'явилося в тій самій статті, де доводиться теорема Ердеша — Секереша про монотонні підпослідовності в числових послідовностях.
Розмір множини як функція числа вершин багатокутника Нехай позначає мінімальне , Для якого будь-яка множина з точок у загальному положенні містить опуклий -кутник. Відомо що:
, очевидно. , довела Естер Секереш. , згідно з це першим довів Е. Макао; перше опубліковане доведення з'явилося в Множина з восьми точок, що не містить опуклого п'ятикутника, на ілюстрації показує, що ; складніше довести, що будь-яка множина з дев'яти точок у загальному положенні містить опуклий п'ятикутник. , це було доведено в . У роботі реалізовано скорочений комп'ютерний перебір можливих конфігурацій з 17 точок. Значення невідомі для .
Гіпотеза Ердеша — Секереша про мінімальне число точок Виходячи з відомих значень для , Ердеш і Секереш припустили, що:
для всіх .
Ця гіпотеза не доведена, але відомі оцінки зверху і знизу.
Оцінки швидкості росту Конструктивною побудовою автори гіпотези зуміли пізніше довести оцінку знизу, що збігається з гіпотетичною рівністю:
,
Проте найкраща відома оцінка зверху при не є близькою:
,
(використано біноміальні коефіцієнти).
Порожні багатокутники Цікаве також питання про те, чи містить досить велика кількість точок у загальному положенні порожній опуклий чотирикутник, п'ятикутник і так далі. Тобто багатокутник, який не містить внутрішніх точок.
Якщо всередині чотирикутника, що існує відповідно до теореми зі щасливим кінцем, є точка, то, з'єднавши цю точку з двома вершинами діагоналі, ми отримаємо два чотирикутники, один з яких опуклий і порожній. Таким чином, п'ять точок в загальному положенні містять порожній опуклий чотирикутник, як видно на ілюстрації. Будь-які десять точок в загальному положенні містять порожній опуклий п'ятикутник . Однак існують як завгодно великі множини точок у загальному положенні, які не містять порожнього опуклого семикутника.
Таким чином, задача про порожні багатокутники не є проблемою теорії Рамсея і в принципі розв'язана.
Питання про існування порожнього шестикутника довгий час залишалося відкритим. Але в і було доведено, що будь-яка досить велика множина точок у загальному положенні містить порожній шестикутник. Сьогодні відомо, що ця множина має містити не більше f(9) (імовірно 129) і не менше 30 точок.
Примітки
Література
. . . Reprinted in: . . . . . . . . . . . . . . . .
Посилання Happy ending problem and Ramsey-theoretic proof of the Erdős-Szekeres theorem on PlanetMath