На плоскости дано n>4 точек, никакие три из которых не лежат на одной прямой. Докажите, что существует не менее n(n-1)(n-2)(n-3)/120 различных выпуклых четырехугольников с вершинами в этих точках.
Сначала докажем, что если выбрать любые пять точек, то существует выпуклый четырехугольник c вершинами в них. Если выпуклой оболочкой этих пяти точек будет пятиугольник или четырёхугольник, то очевидно, что существует. Пусть выпуклая оболочка этих точек — треугольник. Тогда две точки лежат внутри этого треугольника. Прямая, проходящая через них пересекается две стороны треугольника (потому что никакие три точки не лежат на одной прямой). Возьмём эти две точки и две вершины, соединяющие стороны, которую эта прямая не пересекает. Получился искомый выпуклый четырёхугольник. Теперь заметим, что найденный четырёхугольник может быть искомым не более чем для (n-4) пятёрок точек. Итак, пятёрки точек можно выбрать n(n-1)(n-2)(n-3)(n-4)/120 способами, а каждый четырёхугольник будет посчитан не более (n-4) раз. Задача решена!
Итак, из пяти точек общего положения всегда можно выбрать выпуклый четырёхугольник. Оказывается, что из девяти точек всегда можно выбрать выпуклый пятиугольник, а из семнадцати — выпуклый шестиугольник. Гипотеза Эрдёша-Секереша говорит о том, что из 2^(n-2)+1 точки можно выбрать выпуклый n-угольник. Но, насколько я понимаю, сейчас никто не понимает, как её доказывать.
Впрочем, те же Эрдёш и Секереш еще до войны доказали, что если на плоскость кинуть достаточно много точек общего положения, то выпуклый n-угольник найдётся. Но это уже совсем другая история!
