Для каждого натурального $n\ge3$ укажите наименьшее $k$ такое, что любые $n$ точек плоскости, никакие три из которых не лежат на одной прямой, можно разделить $k$ прямыми. (Прямые разделяют данные точки, если для любых двух из этих точек найдётся прямая, от которой они лежат по разные стороны.)
Многие из приславших нам решение этой задачи вспомнили такой факт (его нетрудно доказать с помощью индукции): $k$ прямых разбивают плоскость не более чем на $\dfrac{k(k+1)}2+1$ частей (для $k$ прямых общего положения будет ровно $\dfrac{k(k+1)}2+1\Big)$.
Отсюда следует, что $k$ прямых не смогут разделить более чем $\dfrac{k(k+1)}2+1=n$ точек. Другими словами, даже при самом удачном расположении $n$ точек, нужно не менее $k=\dfrac{\sqrt{8n-7}-1}{2}\approx\sqrt{2n}$ прямых, чтобы их разделить.
Поэтому можно ожидать, что при любом расположении $n$ точек их можно разделить $c\sqrt{n}$ прямыми, где $c$ — некоторая постоянная. Но оказывается, это вовсе не так.
Докажем, что наименьшее значение $k$ равно $\left[\dfrac{n+1}2\right]$, т. е. $k=\dfrac n2$ при чётном $n$ и $k=\dfrac{n+1}{2}$ при нечётном $n$.
Сначала построим пример, показывающий, что меньшим числом прямых обойтись нельзя. Расположим $n$ точек на окружности (или на границе любой выпуклой фигуры). Если $k$ прямых разделяют эти $n$ точек, то они делят окружность по крайней мере на $n$ дуг, т. е. пересекают её не менее чем в $n$ точках. Но каждая прямая пересекает окружность не более чем в двух точках, поэтому $2k\ge n$, т. е. $k\ge\dfrac n2$.
Докажем теперь, что для любых $n$ точек можно построить систему не более чем из $\dfrac{n+1}2$ разделяющих их прямых. Ясно, что можно провести одну прямую $l_0$ так, чтобы количество точек по одну и другую сторону от неё было одинаковым (или отличалось на единицу). Покажем, как провести ещё не более $\dfrac{n-1}2$ прямых, чтобы разделить все точки.
Рис. 6
Возьмём наименьший выпуклый многоугольник, содержащий наши $n$ точек, и рассмотрим отрезок $A_1B_1$ его границы, пересекающий прямую $l_0$ (рис. 6). Проведём параллельно $[A_1B_1]$ прямую $l_1$, отделяющую точки $A_1$, $B_1$ от остальных $n-2$ точек (друг от друга точки $A_1$ и $B_1$ отделены прямой $l_0$).
Ту же процедуру применим к оставшимся $n-2$ точкам — возьмём наименьший выпуклый многоугольник, содержащий эти $n-2$ точки, и вновь рассмотрим отрезок $A_2B_2$ его границы, пересекающий $l_0$. Проведя прямую $l_2\parallel [A_2B_2]$, отделим точки $A_2$, $B_2$ от остальных точек. Затем отделим от остальных еще две точки $A_3$, $B_3$ прямой $l_3\parallel [A_3B_3]$ ($[A_3B_3]$ пересекает $l_0$) и т. д., до тех пор, пока не останутся две (в случае чётного $n$) или одна (в случае нечётного $n$) точки. Ясно, что вместе с прямой $l_0$ построенные прямые $l_1$, $l_2$, $l_3$, $\ldots$ уже разделяют все $n$ точек. Число прямых $l_i$, $i=1$, 2, 3, $\ldots$ равно $\dfrac{n-2}2$ если $n$ чётно, и $\dfrac{n-1}2$, если $n$ нечётно, т. е. это число не превосходит $\dfrac{n-1}2$, так что для разделения всех точек требуется не более чем $\dfrac{n+1}2$ прямых.
