Олимпиадная задача по комбинаторной геометрии: минимум непараллельных прямых

  Случай  n = 2  тривиален, так что будем считать, что  n ≥ 3.

  Правильный n-угольник имеет ровно n осей симметрии. Поставим в соответствие каждой стороне и каждой диагонали её серединный перпендикуляр (это одна из осей симметрии). У параллельных сторон и диагоналей серединные перпендикуляры совпадают. Верно и обратное: для каждой оси симметрии найдётся перпендикулярная ей сторона или диагональ. Поэтому взяв n вершин правильного n-угольника, мы получим ровно n попарно непараллельных соединяющих их прямых.

  Теперь расмотрим произвольный удовлетворяющий условию набор точек. Выберем среди данных точек крайнюю. Для этого рассмотрим их выпуклую оболочку. Пусть O – вершина этого выпуклого многоугольника, A и B – соседние с ней вершины (см. рис.).

  Все лучи, соединяющиеOс остальными точками, проходят внутри углаAOB. Они задают  n– 1  попарно непараллельных прямых. ПрямаяABпересекает их все и, значит, её можно взять в качествеn-й прямой.

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