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

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

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

Історія

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

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

Доведення

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

Багатокутники з довільним числом вершин

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

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

В Шаблон:Harvard citation доведено таке узагальнення: для будь-якого натурального $N$, будь-яка досить велика множина точок у загальному положенні на площині має підмножину $N$ точок, які є вершинами опуклого багатокутника. Це доведення з'явилося в тій самій статті, де доводиться теорема Ердеша — Секереша про монотонні підпослідовності в числових послідовностях.

Розмір множини як функція числа вершин багатокутника

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

• $f(3)=3$, очевидно.
• $f(4)=5$, довела Естер Секереш.
• $f(5)=9$, згідно з Шаблон:Harvard citation це першим довів Е. Макао; перше опубліковане доведення з'явилося в Шаблон:Harvard citation Множина з восьми точок, що не містить опуклого п'ятикутника, на ілюстрації показує, що $f(5)>8$; складніше довести, що будь-яка множина з дев'яти точок у загальному положенні містить опуклий п'ятикутник.
• $f(6)=17$, це було доведено в Шаблон:Harvard citation. У роботі реалізовано скорочений комп'ютерний перебір можливих конфігурацій з 17 точок.
• Значення $f(N)$ невідомі для $N>6$.

Гіпотеза Ердеша — Секереша про мінімальне число точок

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

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

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

Оцінки швидкості росту $f(N)$

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

$f(N)\ge 1+2^{N-2}$, Шаблон:Harvard citation

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

$f(N)\le (\genfrac{}{}{0ex}{}{2N-5}{N-2})+1=O\left(\frac{4^N}{\sqrt{N}}\right)$, Шаблон:Harvard citation

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

Порожні багатокутники

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

Якщо всередині чотирикутника, що існує відповідно до теореми зі щасливим кінцем, є точка, то, з'єднавши цю точку з двома вершинами діагоналі, ми отримаємо два чотирикутники, один з яких опуклий і порожній. Таким чином, п'ять точок в загальному положенні містять порожній опуклий чотирикутник, як видно на ілюстрації. Будь-які десять точок в загальному положенні містять порожній опуклий п'ятикутник Шаблон:Harvard citation. Однак існують як завгодно великі множини точок у загальному положенні, які не містять порожнього опуклого семикутника. Шаблон:Harvard citation

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

Питання про існування порожнього шестикутника довгий час залишалося відкритим. Але в Шаблон:Harvard citation і Шаблон:Harvard citation було доведено, що будь-яка досить велика множина точок у загальному положенні містить порожній шестикутник. Сьогодні відомо, що ця множина має містити не більше f(9) (імовірно 129) і не менше 30 точок. Шаблон:Harvard citation

Література

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation. Reprinted in: Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.

Посилання

• Happy ending problem Шаблон:Webarchive and Ramsey-theoretic proof of the Erdős-Szekeres theorem Шаблон:Webarchive on PlanetMath
• Шаблон:MathWorld