|
|
 |
Условие
На окружности имеется 21 точка.
Докажите, что среди дуг, имеющих концами эти точки, найдётся не меньше ста
таких, угловая мера которых не превышает 120°.
Решение 1
По индукции докажем утверждение для 2n + 1 точки и n² дуг. База n = 0.
Шаг индукции. Пусть имеется 2n + 3 точки. Рассмотрим "длинную" (более 120°) дугу AB с концами в этих точках (если таких нет, то "коротких" дуг более чем достаточно). Пусть С – произвольная из оставшихся точек. По крайней мере одна из дуг AС, BС не превосходит 120°. Итак, имеется не менее 2n + 1 "короткой" дуги с концами в точках A и B. Плюс (согласно предположению индукции) n² дуг с концами в других точках. Итого, не менее
n² + 2n + 1 = (n + 1)² коротких дуг.
Решение 2
Докажем, что в графе с n вершинами и без треугольников число ребер не превышает n2/4. Рассмотрим вершину A наибольшей степени m. Вершины, соседние с A, между собой не соединены. Каждая из остальных n – m – 1 вершин соединена не более чем с m. Итого, не более
m + m(n – m – 1) = m(n – m) ≤ n²/4 ребер.
Проведём в нашей окружности хорды, соответствующие "длинным" дугам. Мы получим граф без треугольников. В нем не более 21²/4, то есть не более 110 рёбер. А всего хорд – 210, то есть не менее 100 соответствуют "коротким" дугам.
Замечания
1. Улучшить результат нельзя. Расположив 11 точек в окрестности "южного полюса" и 10 точек в окрестности "северного", получим ровно 100 коротких дуг.
2. Утверждение о графе без треугольников можно доказать и по индукции аналогично решению 1.
3. 8 баллов.
