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

[Dave]

А вот эта чуть посложнее будет.

Задача.
Докажите, что любые $2nm$ точек плоскости, никакие три из которых не лежат на одной прямой, можно разделить $n$ прямыми, не проходящими ни через одну из этих точек, на области, в каждой из которых расположено не более $m$ точек ($n$ и $m$ - любые натуральные).

[TOTAL]

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

Задача.
Докажите, что любые $2nm$ точек плоскости, никакие три из которых не лежат на одной прямой, можно разделить $n$ прямыми, не проходящими ни через одну из этих точек, на области, в каждой из которых расположено не более $m$ точек ($n$ и $m$ - любые натуральные).

Как и в предыдущей задаче, прямой линией $L$ разделим точки на равные части синего и красного цвета. Очень косо спроецируем все точки на $L$, так что проекции красных и синих не чередуются. Затем плавно изменяем угол проекции (проекции красных и синих плавно ползут друг к другу, постепенно перемешиваются, меняются местами) и дожидаемся момента, когда на $L$ можно с одного края отделить по $m$ красных и синих проекций.

Т.е. $m$-я по счету справа синяя проекция и $m$-я по счету справа красная проекция непрерывно зависят (их положение на прямой $L$ зависит) от угла (параллельного) проецирования и изменяются в противоположных направлениях, поэтому при каком-то угле они совпадут.

[Dave]

Да, всё правильно. Это был двухмерный дискретный случай. Оказывается, народ уже додумался и до трёхмерного непрерывного. Там даже три тела одновременно можно разделить плоскостью.

[Aritaborian]

Всё-таки это другая задача. И очень старая, кстати. Dave, неужели вы о ней никогда не слышали?

[Dave]

Нет, не слышал. И мне кажется, там какого-то условия в формулировке недостаёт для строгости. Выпуклости тел, наверное.

[Aritaborian]

С чего бы там требовать выпуклость?

[TOTAL]

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

Да, всё правильно. Это был двухмерный дискретный случай. Оказывается, народ уже додумался и до трёхмерного непрерывного. Там даже три тела одновременно можно разделить плоскостью.

Каждое тело всего на две равные части. Вот здесь задача из этой оперы задача про голодного студента