Олимпиадная задача Райгородского: минимум отрезков между 4n точками на плоскости

  Сначала докажем, что всего проведено не менее 6n отрезков.

  Рассмотрим граф, множество V вершин которого состоит из всех отмеченных точек, а множество E рёбер состоит из всех пар точек, соединённых отрезками. Тогда  |V| = 4n,  и для каждого  W ⊂ V,  |W| ≥ n + 1,  найдутся  x, y ∈ W ,  образующие ребро  (x, y) ∈ E.

  Возьмём произвольное множество  Q₁ ⊂ V, которое не содержит рёбер и имеет максимальную мощность среди всех подмножеств множества V, которые не содержат рёбер. Ясно, что  |Q₁| ≤ n.  Кроме того, ввиду максимальности множества Q₁ каждая вершина из  V \ Q₁  имеет хотя бы одного соседа в Q₁. Значит, в E по крайней мере 3n элементов.

  Удалим из V множество Q₁. Останется граф G₁ с множеством вершин V₁ и множеством рёбер E₁, причём  |V₁| ≥ 3n,  и для каждого  W ⊂ V₁,

|W| ≥ n+ 1,  найдутся x, y ∈ W,  образующие ребро  (x, y) ∈ E₁. Опять возьмём произвольное множество  Q₂ ⊂ V₁, которое не содержит рёбер и имеет максимальную мощность среди всех подмножеств множества V₁, не содержащих рёбер. Аналогично докажем, что в E₁ по крайней мере 2n элементов. Поскольку рёбра, найденные на первом шаге поиска, заведомо отличны от рёбер, найденных только что, то в E уже не менее 5n элементов.

  Делаем ещё один полностью аналогичный шаг и убеждаемся, что   |E| ≥ 6n.

  Для того чтобы доказать, что рёбер по крайней мере 7n, начнём сначала, немного усложнив процедуру: теперь мы учтём, что граф G – дистанционный граф на плоскости, то есть рёбрами соединены только пары вершин на расстоянии в 1 см друг от друга. Проведём почти ту же самую процедуру, что была описана выше; отличие будет только на первом шаге. Мы уже знаем, что каждая вершина из  V \ Q₁  имеет хотя бы одного соседа в Q₁. Давайте разобьём  V \ Q₁  на две части W₁ и W₂. В W₁ будут те вершины, у каждой из которых ровно один сосед в Q₁, в W₂ – те вершины, у каждой из которых не менее двух соседей. Если мы докажем, что  |W₁| ≤ 2n,  то увидим, что на первом шаге вклад в |E| имеет величину не 3n, как это было раньше, а по крайней мере 4n.

  Предположим, что  |W₁| > 2n.  Тогда в Q₁ есть вершина q, смежная с тремя вершинами x₁, x₂, x₃ из W₁. Если между какими-то x_i и x_j нет ребра, то мы можем удалить q из Q₁ и добавить к этому множеству обе вершины x_i и x_j. Получится множество, в котором нет рёбер и у которого мощность строго больше |Q₁|. Значит, вершины x₁, x₂, x₃ и q попарно соединены рёбрами. Но полный граф на четырёх вершинах нельзя реализовать отрезками длины 1 на плоскости. Противоречие.

Ответ задачи отсутствует