Эта задача возникла в XX уже веке,
в те времена когда никого никакие парадоксы Бертрана не смущали,
потому что к тому времени уже была аксиоматика Колмогорова,
о которой мы сегодня пару слов скажем еще чуть позже.
Эта задача следующего содержания,
предложена она была, фактически, великим Эрдешем, которого мы здесь уже упоминали.
Ну, Эрдеша, наверное, и Секериша – мы их последователи.
Значит, задача такая.
Вот давайте рассмотрим
какое-нибудь множество точек X на плоскости
и будем считать, что всего у нас точек n штук.
То есть это конечное множество, состоящее из n элементов.
Вот возьмем какие-то n точек на плоскости.
Так, ну давайте я нарисую несколько точек,
чтобы было максимально понятно что происходит.
Давайте считать, что никакие три из этих точек не лежат на одной прямой,
потому что если какие-то три точки лежат на одной прямой – это такой неприятный
случай, который мы не хотим рассматривать вовсе.
Так, вот есть множество.
Давайте назовем треугольник, образованный
тремя точками из этого множества пустым, назовем треугольник пустым,
если внутрь этого треугольника других точек исходного множества не попадает.
Ну давайте так и напишем: треугольник Δ пустой,
если Δ...
да что ж такое, почему ж я рисую Ω?
мне надо не Ω, мне надо Δ, если Δ,
пересеченное с Х – это только множество его вершин.
...равняется множество его вершин.
Никаких новых точек внутрь Δ,
кроме вершин этого треугольника не попадает.
Тогда мы его называем пустым.
Тривиальной является задача отыскания максимального количества
пустых треугольников в множестве из n точек на плоскости.
То есть можно было бы спросить каково наибольшее максимальное количество
пустых треугольников в множестве из n точек на плоскости.
Но эта задача тривиальна.
Эта задача тривиальна, потому что мы можем взять вершины
какого-нибудь выпуклого n-угольника,
и видно, что здесь вообще
все треугольники, какие в принципе возникают – пустые.
Если взять вершины выпуклого n-угольника,
то все треугольники, которые там возникают, являются пустыми.
Ну очевидно, никаких внутрь точек они не поймают.
Ну то есть их будет cn³.
И это самое большое количество треугольников,
которое в принципе может возникнуть на n точках, это понятно.
То есть задача об отыскании максимального количества
пустых треугольников тривиальна.
А вот задача об отыскании минимального количества пустых треугольников
является одной из классических задач современной комбинаторной геометрии,
которая, сразу вам скажу, до конца до сих пор не решена.
Ну вот давайте введем такую величину f(n),
которая собственно и есть минимальное количество
пустых треугольников
в множестве из
n точек на плоскости.
И вот теперь давайте подумаем, как можно было бы, например,
доказывать какие-нибудь верхние оценки для величины f(n)?
То есть что можно было бы сделать для того, чтобы доказать,
что f(n) чего-то не превосходит?
А что значит f(n) чего-то не превосходит?
Ну это значит, что существует такое множество,
состоящее из n точек и расположенное на плоскости, в котором не больше,
чем столько пустых треугольников.
Значит f(n) не превосходит какого-нибудь
a тогда и только тогда,
когда существует подмножество X на плоскости
имеющее мощность a и такое, что в X...
... сейчас, почему...
имеющее мощность n, извините.
Глупость написал, прошу прощения, конечно имеющее мощность n.
...и такое что в X не больше a пустых треугольников.
Ну, конечно,
да, f(n) не превосходит a, если такое множество из n точек существует,
в котором не больше чем a пустых треугольников.