Задано несколько красных и несколько синих точек. Некоторые из них соединены отрезками. Назовём точку «особой», если более половины из соединённых с ней точек имеют цвет, отличный от её цвета. Если есть хотя бы одна особая точка, то выбираем любую особую точку и перекрашиваем в другой цвет. Докажите, что через конечное число шагов не останется ни одной особой точки.

   Решение

Темы:    [ Задачи с ограничениями ] [ Индукция (прочее) ] [ Теория графов (прочее) ]

Сложность: 5 Классы: 9,10,11

Прислать комментарий

Условие

В пространстве расположены 2n точек, никакие четыре из которых не лежат в одной плоскости. Проведены  n² + 1  отрезков с концами в этих точках. Докажите, что проведённые отрезки образуют
  а) хотя бы один треугольник;
  б) не менее n треугольников.

Решение

  а) Выберем точку, из которой выходят наибольшее число отрезков. Обозначим её через A₁, концы выходящих из нее отрезков – через B₁, ..., B_k,  остальные точки – через  A₂, ..., A_2n–k.  Если треугольников нет, то между точками  B₁, ..., B_k  нет отрезков, поэтому из каждой из них выходит не более  2n − k  отрезков. А поскольку из каждой точки A_i  (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 (не считая его сторон), через k_A, k_B, k_C соответственно. Если  k = k_A + k_B + k_C ≤ 3n − 2,  то для каких-то двух вершин треугольника, например A и B, общее число таких отрезков  k_A + k_B  не больше  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  точек, отличных от А, В, С, имеется n_j таких, из которых идёт j отрезков к вершинам A, B, C,  (j = 0, 1, 2, 3).  Тогда
n₁ + n₂ + n₃ ≤ n₀ + n₁ + n₂ + n₃ = 2n − 1,  n₁ + 2n₂ + 3n₃ = k ≥ 3n − 1,  следовательно,  t = n₂ + 3n₃ ≥ n₂ + 2n₃ ≥ (3n − 1) − (2n − 1) ≥ n.

Замечания

На Московской Математической Олимпиаде задача предлагалась для  n = 4.

Источники и прецеденты использования