В пространстве расположено $2n$ ($n\ge 2$) точек (так, что никакие 4 не лежат в одной плоскости) и проведено $n^2+1$ отрезков с концами в этих точках. Докажите, что проведённые отрезки образуют
а) Выберем точку, из которой выходит наибольшее число отрезков. Обозначим её через $A_1$, концы выходящих из неё отрезков — через $B_1$, $\ldots$, $B_k$, остальные точки — через $A_2$, $\ldots$, $A_{2n-k}$. Если треугольников нет, то между точками $B_1$, $\ldots$, $B_k$ нет отрезков, поэтому из каждой из них выходит не более $2n-k$ отрезков. А поскольку из каждой точки $A_i$, $i=1$, $\ldots$, $2n-k$, выходит не более $k$ отрезков, общее число отрезков не превосходит
$$
\dfrac12(k(2n-k)+(2n-k)k)=k(2n-k)\le n^2.
$$
Но число данных отрезков равно $n^2+1$, поэтому они образуют хотя бы один треугольник.
Для $n^2$ отрезков утверждение задачи, как видно из рисунка, неверно.
б) Проведём доказательство индукцией по $n$. При $n=2$ (для 4 точек и 5 отрезков) утверждение проверяется непосредственно. Докажем его для $2(n+1)$ точек, считая его верным для $2n$ точек.
Согласно пункту а), проведённые отрезки образуют хотя бы один треугольник $ABC$. Нужно ещё по крайней мере $n$ треугольников. Обозначим количества отрезков, выходящих из вершин треугольника $ABC$ (не считая его сторон), через $k_A$, $k_B$, $k_C$ соответственно.
Если $k=k_A+k_B+k_C\le 3n-2$, то для каких-то двух вершин треугольника, например $A$ и $B$, общее число таких отрезков $k_A+k_B$ не больше $2n-2$. Выбросим эти точки и все выходящие из них отрезки (вместе со сторонами треугольника $ABC$). Мы получим набор из точек, соединённых не менее чем $(n+1)^2+1-(2n-2)-3=n^2+1$ отрезками, которые по предположению индукции образуют не менее $n$ треугольников.
Если же $k\ge3n-1$ и $k$ рассматриваемых нами отрезков образуют со сторонами $AB$, $BC$ и $CA$ $t$ треугольников, то $t\ge n$. В самом деле, пусть среди $2n+2-3=2n-1$ точек, отличных от $A$, $B$, $C$, имеется $n_j$ таких, из которых идёт $j$ отрезков к вершинам $A$, $B$, $C$ ($j=0$, 1, 2, 3). Тогда
$$
\begin{gather*}
n_1+n_2+n_3\le n_0+n_1+n_2+n_3=2n-1,\\
n_1+2n_2+3n_3=k\ge 3n-1,
\end{gather*}
$$
следовательно, $t=n_2+3n_3\ge n_2+2n_3\ge (3n-1)-(2n-1)\ge n$.
