Конечно, можно пытаться как-то явно сконструировать такое множество, то есть прямо там пытаться в координатах описать точки этого множества и потом доказывать, что в этом множестве пустых треугольников не больше, чем нужная нам величина. Но вот это, представьте себе, работает очень плохо. А гораздо лучше работает вероятностный метод. Что значит вероятностный метод? Опять вот, возвращаясь к нашим, к нашим раскраскам гиперграфам. Там нам нужно было доказывать существование какой-то раскраски. И мы брали случайную раскраску и доказывали, что это случайная раскраска с положительной вероятностью обладает нужным нам свойством. Ну значит и здесь, наверное, нужно взять случайное подмножество из n точек на плоскости и доказывать, что с положительной вероятностью в этом случайном подмножестве не больше, чем нужное нам количество пустых треугольников. Ну уж насколько маленьким сможем взять a при этом, настолько и хорошо. То есть нам нужно вроде бы как случайное множество из n точек. Хе, но это ведь совсем не понятно что значит. Даже случайная хорда могла быть определена по-разному, а что такое случайное множество из n точек? Тоже не понятно. Можно, например, взять квадрат со стороной 1 на плоскости, с которого мы сегодня начинали: Коля, Вася, встреча, да? Можно взять квадрат на плоскости, и из него как-нибудь там независимо, скажем, согласно геометрической вероятности извлечь n случайных точек. Это, конечно, можно. После чего надо будет считать вероятность того, что в этом случайном множестве не слишком много пустых треугольников, и если эта вероятность окажется положительной, то мы докажем существование такого X мощности n, в котором не больше, чем нужное нам количество пустых треугольников. А можно взять вместо круга, ой, извините, квадрата, например, круг на плоскости. И в нем, согласно геометрической вероятности, выбирать случайные точки. Вот оказывается, что все искусство получения наилучшей оценки для вот этого a оно именно к тому и сводится: как правильно определить случайность. То есть откуда эти случайные точки выбирать так, чтобы потом с наибольшей вероятностью, с наиболее, так сказать, положительной вероятностью, – наша-то цель доказать, что вероятность положительная – вот так, чтобы потом с наибольшей вероятностью, чтобы она все-таки оказалась положительной, с наибольшей вероятностью пустых треугольников было бы поменьше. Количество пустых треугольников было бы как можно меньше. Это целое искусство – правильно определить случайность множества X, состоящего из n точек. Давайте я не буду вдаваться в подробности доказательства, потому что оно там требует довольных хитрых рассужений с подсчетом каких-то интегралов, не хочу вам морочить голову, но саму конструкцию нарисую. Одну из лучших, которая дает в итоге одну из лучших оценок для величины a. Конструкция такая. Берем такую, что называется, расческу, условно говоря. Здесь 1, дальше 2, 3, и так далее, вот здесь n. И это все отрезочки длины единица. Вот берем такую, Бог знает откуда, с какого потолка взявшуюся конструкцию, но вот это именно и есть искусство выбора геометрической вероятности правильной. Дальше, берем случайную точку x1 на первом зубце «расчески», берем случайную точку x2, естественно независимо от x1, на втором зубце «расчески», дальше случайную точку x3 и, наконец, случайную точку xn на последнем зубце. Вот получается такой набор из n случайных точек. Давайте X большое – это и будет {x1, ..., xn}. Набор из n случайных точек, он, естественно, случаен сам по себе. Вероятность попадания этого конкретного набора внутрь какого-то набора подмножеств зубцов «расчески» тоже легко посчитать. Но вот оказывается, что если теперь в таком определении случайности множества из n точек на плоскости посчитать вероятность того, что в X не больше ну, скажем, 2,1n² пустых треугольников, то вот она окажется положительной. То есть существует действительно конкретное множество точек, расположенных каждая по отдельности на своем зубце «расчески», такое, что в этом множестве точек не больше чем 2,1n² пустых треугольников. Ну я здесь написал 2,1 потому, что на самом деле я с таким же успехом могу здесь написать 2,01, 2,001, и каждый раз вероятность будет больше нуля. Но чего я не могу сделать, это заменить вот это число в точности двойкой. То есть если в рамках этой конструкции попытаться заменить каждое из вот этих чисел просто ровно двойкой, тогда ничего не получится. То есть можно сказать так: если мы фиксируем произвольное ε положительное и хотим, чтобы в случайном множестве X, которое мы выбрали с помощью вот такой вот геометрической вероятности, было не больше, чем (2 + ε) на n² пустых треугольников, то вот эта вероятность больше нуля. Ну и значит такой X существует. Но убрать ε, заменить его на ноль все-таки в этом рассуждении нам не удается. Это не означает, что не существует более хитрого определения случайного множества, которое даст лучший результат, но вот в рамках этого рассуждения, если его провести до конца, вот получается такая штука. Так, товарищи. Но в чем пафос-то? А пафос вот в чем. Видите, максимальное количество пустых треугольников – это C из n по 3. Но эта величина, которая, как мы знаем, ведет себя примерно как n³/6. То есть максимальное количество пустых треугольников – это величина порядка n³. А минимальное количество пустых треугольников – это величина, которая, как мы видим, заведомо не превосходит чего-то порядка n², то есть гораздо меньше. Но это еще не пафос. Дело в том, что есть следующая теорема, которую я тоже не собираюсь здесь доказывать, она не имеет отношения к нашей вероятностной тематике. Вот эта имела, а эта не имеет. Но мне просто хочется, чтобы вы уж до конца представляли себе ситуацию с этой наукой. А ситуация такая. Оказывается, что f(n) ≥ (1 – ε) * n². Это тоже можно доказать. То есть не бывает на плоскости множества из n точек, не бывает на плоскости множества из n точек, в которых было бы меньше, чем столько пустых треугольников. Иными словами, вот этот результат почти точный. Он всего лишь в 2 плюс какая-то мелочь раз отличается от нижней оценки. Вот эта вероятностная технология, правильный выбор случайностей позволяет практически точно отыскать величину f(n). Ну и вот сейчас проблема состоит в том, чтобы найти прямо асимптотику для этого f(n). То есть все-таки хочется найти правильную константу. Придумали более хитрые конструкции, нежели та, которую я сейчас описал. Известны оценки что-то типа 1,6 * n², но по прежнему все-таки зазор в константу раз присутствует, и вот люди не знают, как это аккуратно посчитать. То есть тут есть до сих весьма интересная и полезная нужная деятельность. Такая вот забавная наука.
