На плоскости даны $n$ точек $A_1$, $\ldots$, $A_n$, никакие три из которых не лежат на одной прямой. Какое наибольшее число отрезков с концами в этих точках можно провести так, чтобы не получилось ни одного треугольника с вершинами в этих точках?
Проведём максимальное число отрезков с концами в точках $A_1$, $\ldots$, $A_n$. Получим некоторый граф с вершинами в этих точках. Отрезки с концами в вершинах графа будем называть рёбрами графа. Оценим число рёбер в нашем графе.
Назовём степенью вершины в графе число выходящих из неё рёбер. Пусть $k$ — максимальная степень вершины в графе, и пусть некоторая вершина $A_i$ соединена с $k$ вершинами $A_{j_1}$, $\ldots$, $A_{j_k}$ графа (рис. 1). Тогда степень любой вершины из множества $\{A_{j_1},{\ldots},A_{j_k}\}$ не превосходит $n-k$ ($n$ — число вершин графа), поскольку любые вершины из этого множества уже не могут быть соединены ребром (в нашем графе никакие три ребра не образуют треугольника — с вершинами в вершинах графа). Так как $k$ — максимальная степень вершины в графе, степень каждой из оставшихся $n-k$ вершин не превосходит $k$. Поэтому сумма степеней всех вершин графа не превосходит $k\cdot(n-k)+(n-k)\cdot k=2k(n-k)$. Но легко видеть, что сумма степеней всех вершин графа равна удвоенному количеству его рёбер. Следовательно, количество рёбер графа не больше $k(n-k)\le\left(\dfrac{k+(n-k)}2\right)^2=\dfrac{n^2}4$ (мы воспользовались теоремой о среднем арифметическом и среднем геометрическом). Учитывая, что количество рёбер графа — число целое, мы получаем, что рёбер в нашем графе нe больше чем $\left[\dfrac{n^2}4\right]$ (здесь $[x]$ означает целую часть числа $x$ — наибольшее целое число, не превосходящее $x$).
Рис. 1Рис. 2
Укажем теперь способ построения графа без треугольников с $n$ вершинами, число рёбер которого в точности равно $\left[\dfrac{n^2}4\right]$.
Разобьём множество точек $A_1$, $\ldots$, $A_n$ на два: $\left[\dfrac n2\right]$ точек в одном множестве и $n-\left[\dfrac n2\right]$ — в другом. Соединив все точки первого множества с точками второго (как на рисунке 2, где $n=5$), мы получим граф, у которого не будет ни одного треугольника с вершинами в точках $A_1$, $\ldots$, $A_n$. Число рёбер в этом графе, очевидно, равно $\left[\dfrac n2\right]\left(n-\left[\dfrac n2\right]\right)$. Если $n$ — чётное, то $$
\left[\dfrac n2\right]\left(n-\left[\dfrac n2\right]\right)=\dfrac{n^2}4=
\left[\dfrac{n^2}4\right].
$$
Если $n$ — нечётное, то $$
\left[\dfrac n2\right]\left(n-\left[\dfrac n2\right]\right)=
\dfrac{n-1}2\left(n-\dfrac{n-1}2\right)=\dfrac{n^2-1}4=\left[\dfrac{n^2}4\right]‚
$$
что и требовалось доказать.
Итак, ответ в задаче: максимальное число отрезков равно $\left[\dfrac{n^2}4\right]$ (этот результат в теории графов называют теоремой Турана).
