|
|
 |
Условие
На плоскости отметили 4n точек, после чего соединили отрезками все пары точек, расстояние между которыми равно 1 см. Оказалось, что среди любых n + 1 точек обязательно есть две, соединённые отрезком. Докажите, что всего проведено не менее 7n отрезков.
Решение
Сначала докажем, что всего проведено не менее 6n отрезков.
Рассмотрим граф, множество V вершин которого состоит из всех отмеченных точек, а множество E рёбер состоит из всех пар точек, соединённых отрезками. Тогда |V| = 4n, и для каждого W ⊂ V, |W| ≥ n + 1, найдутся x, y ∈ W , образующие ребро (x, y) ∈ E.
Возьмём произвольное множество Q1 ⊂ V, которое не содержит рёбер и имеет максимальную мощность среди всех подмножеств множества V, которые не содержат рёбер. Ясно, что |Q1| ≤ n. Кроме того, ввиду максимальности множества Q1 каждая вершина из V \ Q1 имеет хотя бы одного соседа в Q1. Значит, в E по крайней мере 3n элементов.
Удалим из V множество Q1. Останется граф G1 с множеством вершин V1 и множеством рёбер E1, причём |V1| ≥ 3n, и для каждого W ⊂ V1,
|W| ≥ n+ 1, найдутся x, y ∈ W, образующие ребро (x, y) ∈ E1. Опять возьмём произвольное множество Q2 ⊂ V1, которое не содержит рёбер и имеет максимальную мощность среди всех подмножеств множества 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) графом расстояний (или дистанционным графом) на плоскости, если
V ⊂ R², а E ⊂ {(x, y)| x, y ∈ V, |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 любой размерности.
