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

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

Історія

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

, Шаблон:Harvard citation

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

f (N) \leq (\binom{2 N - 5}{N - 2}) + 1 = O (\frac{4^{N}}{\sqrt{N}})

, Шаблон:Harvard citation

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

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

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

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

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

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

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

Посилання

↑ В даному контексті загальне положення означає, що ніякі три точки не лежать на одній прямій.

[1] В даному контексті загальне положення означає, що ніякі три точки не лежать на одній прямій.

[1]

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

Зміст

Історія

Доведення

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

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

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

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

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

Примітки

Література

Посилання

Навігаційне меню

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

Історія

Доведення

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

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

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

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

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

Примітки

Література

Посилання

Навігаційне меню

Пошук

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