ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 115509
Темы:    [ Теория графов (прочее) ]
[ Принцип крайнего (прочее) ]
[ Перестройки ]
[ Доказательство от противного ]
[ Правильный (равносторонний) треугольник ]
Сложность: 5+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

На плоскости отметили 4n точек, после чего соединили отрезками все пары точек, расстояние между которыми равно 1 см. Оказалось, что среди любых  n + 1  точек обязательно есть две, соединённые отрезком. Докажите, что всего проведено не менее 7n отрезков.


Решение

  Сначала докажем, что всего проведено не менее 6n отрезков.
  Рассмотрим граф, множество V вершин которого состоит из всех отмеченных точек, а множество E рёбер состоит из всех пар точек, соединённых отрезками. Тогда  |V| = 4n,  и для каждого  WV|W| ≥ n + 1,  найдутся  x, yW ,  образующие ребро  (x, y) ∈ E.
  Возьмём произвольное множество  Q1V, которое не содержит рёбер и имеет максимальную мощность среди всех подмножеств множества V, которые не содержат рёбер. Ясно, что  |Q1| ≤ n.  Кроме того, ввиду максимальности множества Q1 каждая вершина из  V \ Q1  имеет хотя бы одного соседа в Q1. Значит, в E по крайней мере 3n элементов.
  Удалим из V множество Q1. Останется граф G1 с множеством вершин V1 и множеством рёбер E1, причём  |V1| ≥ 3n,  и для каждого  WV1,
|W|n+ 1,  найдутся x, yW,  образующие ребро  (x, y) ∈ E1. Опять возьмём произвольное множество  Q2V1, которое не содержит рёбер и имеет максимальную мощность среди всех подмножеств множества V1, не содержащих рёбер. Аналогично докажем, что в E1 по крайней мере 2n элементов. Поскольку рёбра, найденные на первом шаге поиска, заведомо отличны от рёбер, найденных только что, то в E уже не менее 5n элементов.
  Делаем ещё один полностью аналогичный шаг и убеждаемся, что   |E| ≥ 6n.
  Для того чтобы доказать, что рёбер по крайней мере 7n, начнём сначала, немного усложнив процедуру: теперь мы учтём, что граф G – дистанционный граф на плоскости, то есть рёбрами соединены только пары вершин на расстоянии в 1 см друг от друга. Проведём почти ту же самую процедуру, что была описана выше; отличие будет только на первом шаге. Мы уже знаем, что каждая вершина из  V \ Q1  имеет хотя бы одного соседа в Q1. Давайте разобьём  V \ Q1  на две части W1 и W2. В W1 будут те вершины, у каждой из которых ровно один сосед в Q1, в W2 – те вершины, у каждой из которых не менее двух соседей. Если мы докажем, что  |W1| ≤ 2n,  то увидим, что на первом шаге вклад в |E| имеет величину не 3n, как это было раньше, а по крайней мере 4n.
  Предположим, что  |W1| > 2n.  Тогда в Q1 есть вершина q, смежная с тремя вершинами x1, x2, x3 из W1. Если между какими-то xi и xj нет ребра, то мы можем удалить q из Q1 и добавить к этому множеству обе вершины xi и xj. Получится множество, в котором нет рёбер и у которого мощность строго больше |Q1|. Значит, вершины x1, x2, x3 и q попарно соединены рёбрами. Но полный граф на четырёх вершинах нельзя реализовать отрезками длины 1 на плоскости. Противоречие.

Замечания

  Эта задача напрямую связана с самыми современными проблемами комбинаторной геометрии. Назовём граф  G = (V, Eграфом расстояний (или дистанционным графом) на плоскости, если  VR²,   а  E ⊂ {(x, y)| x, yV, |x – y| = a},  где  a > 0  – фиксированное число. Как правило, величина a роли не играет, поэтому для определённости рассматривают a = 1  и говорят о графах единичных расстояний.
  Наиболее известной задачей о дистанционных графах является задача о хроматическом числе плоскости. В то же время огромное количество серьёзных научных исследований посвящено проблемам отыскания ограничений на количества рёбер в графах расстояний. Так, например, очень важен следующий вопрос: каково максимальное количество en рёбер в дистанционном графе с n вершинами? Несмотря на усилия многих крупных специалистов в области комбинаторной геометрии, на этот вопрос по-прежнему нет окончательного ответа. Известны только нижние и верхние оценки величины en. Например, существует такая константа  c > 0,  что  en ≤ cn4/3.
  Ещё один глубокий вопрос состоит в том, насколько большими могут быть независимые множества вершин в графах расстояний. Под независимыми множествами понимаются такие наборы вершин графа, в которых никакие две вершины не соединены ребром. Известно, например, что в любом дистанционном графе на плоскости, имеющем n вершин, есть независимое множество размера не меньше [0,2293n].
  Наша задача в некотором смысле лежит на стыке двух упомянутых выше вопросов. Её можно сформулировать так: каково минимальное количество рёбер у дистанционного графа, который имеет n вершин и не содержит независимых множеств размера n/4 + 1?  Оказывается, что это количество никак не меньше 7n/4. Отметим, что при больших n такие графы действительно существуют.
  Аналогичными задачами занимаются не только в случае плоскости, но и в случае пространства Rn любой размерности.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 73
Год 2010
класс
Класс 10
задача
Номер 2010.10.6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .