|
|
 |
Условие
В пространстве расположены 2n точек, никакие четыре из которых не лежат в одной плоскости. Проведены n² + 1 отрезков с концами в этих точках. Докажите, что проведённые отрезки образуют
а) хотя бы один треугольник;
б) не менее n треугольников.
Решение
а) Выберем точку, из которой выходят наибольшее число отрезков. Обозначим её через A1, концы выходящих из нее отрезков – через B1, ..., Bk, остальные точки – через A2, ..., A2n–k. Если треугольников нет, то между точками B1, ..., Bk нет отрезков, поэтому из каждой из них выходит не более 2n − k отрезков. А поскольку из каждой точки Ai (i = 1, ..., 2n − k) выходит не более k отрезков, общее число отрезков не превосходит
½ (k(2n − k) + (2n − k)k) = k(2n − k) ≤ n². Противоречие.
б) Проведём доказательство индукцией по n.
База. При n = 2 (4 точки и 5 отрезков) утверждение проверяется непосредственно.
Шаг индукции. Пусть имеется 2n + 2 точки и (n + 1)² + 1 отрезков. Согласно а) проведённые отрезки образуют хотя бы один треугольник ABC. Нужно еще n треугольников. Обозначим количества отрезков, выходящих из вершин треугольника ABC (не считая его сторон), через kA, kB, kC соответственно. Если k = kA + kB + kC ≤ 3n − 2, то для каких-то двух вершин треугольника, например A и B, общее число таких отрезков kA + kB не больше 2n − 2. Выбросим эти точки и все выходящие из них отрезки (вместе со сторонами треугольника ABC). Мы получим набор из точек, соединённых не менее чeм
(n + 1)² + 1 − (2n − 2) − 3 = n² + 1 отрезками, которые по предположению индукции образуют не менее n треугольников.
Если же k ≥ 3n − 1 и k рассматриваемых нами отрезков образуют со сторонами AB, BC и CA t треугольников, то t ≥ n. В самом деле, пусть среди
2n + 2 − 3 = 2n − 1 точек, отличных от А, В, С, имеется nj таких, из которых идёт j отрезков к вершинам A, B, C, (j = 0, 1, 2, 3). Тогда
n1 + n2 + n3 ≤ n0 + n1 + n2 + n3 = 2n − 1, n1 + 2n2 + 3n3 = k ≥ 3n − 1, следовательно, t = n2 + 3n3 ≥ n2 + 2n3 ≥ (3n − 1) − (2n − 1) ≥ n.
Замечания
На Московской Математической Олимпиаде задача предлагалась для n = 4.
