Точки и прямые

[Dave]

(Оффтоп)

Навеяна под впечатлением от 2 задачи IMO 2013. Интересно, сложнее она или проще?

На плоскости расположено $n$ точек, никакие три из которых не лежат на одной прямой. Каким минимальным количеством прямых, не проходящих ни через одну из этих точек, наверняка можно разделить плоскость на области, в каждой из которых находится не более одной из заданных точек?

[Aritaborian]

Я, возможно, туплю, но разве не $n-1$?

[statistonline]

Aritaborian в сообщении #754218 писал(а):

Я, возможно, туплю, но разве не $n-1$?

Именно.

[Dave]

Aritaborian в сообщении #754218 писал(а):

Я, возможно, туплю, но разве не $n-1$?

Вообще говоря, нет.

[Aritaborian]

Возьмём $n$ точек с координатами $(i,\frac1i)$, $i=1,...,n$. Разве их можно отделить друг от друга менее чем $n-1$ прямыми?

[Dave]

А почему же нельзя?

[Aritaborian]

Но как?

[Dave]

Это уже будет подсказкой.

[BatMan]

зведочкой

[Terraniux]

Предположение - $\left[\frac{n+1}{2}\right]$.

[TOTAL]

Aritaborian в сообщении #754243 писал(а):

Но как?

Прямой делим все точки на две равные (почти) части синего и красного цвета. Затем прямой линией от кучи красных и кучи синих отрезаем по одной точке. Затем еще по одной, затем еще и т.д.

[Aritaborian]

Кажется, понял ;-)

[griboedovaa]

извините,но я не понял,а что нельзя взять выпуклую оболочку ,а потом отрезать по две точки этой оболочки?

[Dave]

TOTAL в сообщении #754477 писал(а):

Затем прямой линией от кучи красных и кучи синих отрезаем по одной точке.

Нужно ещё строго обосновать, почему это всегда возможно.

[TOTAL]

Dave в сообщении #754522 писал(а):

TOTAL в сообщении #754477 писал(а):

Затем прямой линией от кучи красных и кучи синих отрезаем по одной точке.

Нужно ещё строго обосновать, почему это всегда возможно.

А вот тут пригодится вышеупомянутая выпуклая оболочка, два ребра которой разноцветны, любое из них и отрезаем.