Задача
На окружности имеется 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 соответствуют "коротким" дугам.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь