2014-06-08
В пространстве даны $2n$ различных точек $A_{1}, A_{2}, \cdots, A_{2n} (n > 1)$. Никакие три из них не лежат на одной прямой. Пусть М - множество из $(n^{2} + 1)$ отрезков, концами которых являются данные точки. Доказать, что существует хотя бы один треугольник с вершинами в некоторых точках $A_{r}, A_{s}, A_{t}$, все стороны которого принадлежат множеству М. Доказать, что если число элементов множества М не превосходит $n^{2}$, то такого треугольника может и не существовать.
Решение:
Докажем индукцией по $n \in \mathbf{N}$, что если в графе с $2n$ вершинами никакие три ребра не образуют треугольника, то число ребер не превосходит $n^{2}$. Для $n = 1$ число ребер всегда не превосходит $1 = n^{2}$. Пусть утверждение доказано для числа $n$. Докажем его для числа $n + 1$. Пусть имеется граф с $2(n + 1)$ вершинами, никакие три ребра которого не образуют треугольник. Выберем две вершины, соединенные ребром (если в графе нет ни одного ребра, то все доказано). Тогда каждая из оставшихся $2n$ вершин соединена ребром не более чем с одной из выбранных вершин. Эти $2n$ вершин соединены между собой, по предположению индукции, не более чем $n^{2}$ ребрами. Тогда общее число ребер не превосходит $n^{2} + 2n + 1 = (n + 1)^{2}$. Утверждение доказано. Наконец, если $2n$ вершин разделить на два множества по $n$ вершин, а затем любые две вершины, лежащие в разных множествах, соединить ребрами, то получится граф с $n^{2}$ ребрами, не содержащий ни одного треугольника.