|
|
 |
Условие
Даны n точек на плоскости, никакие три из которых не лежат на одной прямой. Через каждую пару точек проведена прямая. Какое минимальное число попарно непараллельных прямых может быть среди них?
Решение
Случай n = 2 тривиален, так что будем считать, что n ≥ 3.
Правильный n-угольник имеет ровно n осей симметрии. Поставим в соответствие каждой стороне и каждой диагонали её серединный перпендикуляр (это одна из осей симметрии). У параллельных сторон и диагоналей серединные перпендикуляры совпадают. Верно и обратное: для каждой оси симметрии найдётся перпендикулярная ей сторона или диагональ. Поэтому взяв n вершин правильного n-угольника, мы получим ровно n попарно непараллельных соединяющих их прямых.
Теперь расмотрим произвольный удовлетворяющий условию набор точек. Выберем среди данных точек крайнюю. Для этого рассмотрим их выпуклую оболочку. Пусть O – вершина этого выпуклого многоугольника, A и B – соседние с ней вершины (см. рис.).
Все лучи, соединяющие O с остальными точками, проходят внутри угла AOB. Они задают n – 1 попарно непараллельных прямых. Прямая AB пересекает их все и, значит, её можно взять в качестве n-й прямой.
Замечания
Условие общего положения точек нельзя заменить на более слабое: "не все точки лежат на одной прямой". Например, для вершин правильного 2k-угольника и его центра найдутся лишь 2k попарно непараллельных прямых.
