Разделить точки прямой

Jakov

взял отсюда: http://www.turgor.ru/12/turnir12.php
Задача 4.(5)
На плоскости расположено 20 точек, никакие три из которых не лежат на одной прямой, из них 10 синих и 10 красных.
Докажите, что можно провести прямую, по каждую сторону которой лежит 5 синих и 5 красных точек.
А. Кушниренко
ну там 20 на N замените
ну и делить достаточно так чтобы кол-во цветов с каждой стороны совпадало, ну тойсть там допустим на N-3,N-3 и 3,3
интересует общее решение

stm7543347

ну и делить достаточно так чтобы кол-во цветов с каждой стороны совпадало, ну тойсть там допустим на N-3,N-3 и 3,3
(N,N) и (0,0) сойдет?

Vadim46

ну идея наверно такая
возьмем направление, не параллельное ни одной из прямых, соединяющих наши точки.
можно выбрать прямую с этим направлением так, чтобы она удовлетворяла условию про синие точки.
допустим, что она не удовлетворяет условию про красные точки, т.е. с одной стороны от нее больше половины красных точек, а с другой - меньше.
будем непрерывно изменять это направление, соответствующая прямая тоже будет непрерывно крутиться (?). Будем также следить за той полуплоскостью, в которой изначально было больше красных точек.
когда прямая повернется на 180 градусов, стороны поменяются местами, т.е. в той полуплоскости, за которой мы следим, теперь будет меньше половины красных точек. Число точек менялось только в моменты, когда прямая проходила через красные точки; этих красных точек на этой прямой не может быть больше двух, откуда видно, что число красных точек в нашей полуплоскости меняется в такие моменты не больше чем на 1. Значит, в какой-то момент их было ровно половина.

stm7543347

Значит, в какой-то момент их было ровно половина.
И синих, главное, было тоже ровно половина, потому что они услужливо поворачивались вместе с прямой! :umn:

Vadim46

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

Jakov

ну мы же каждый раз выбирали прямую так как было написано в самом начале, только по другому направлению, так что да, ровно половина.
соответствующая прямая тоже будет непрерывно крутиться (?).
у меня в голове эти два тезиса не укладываются :(

Vadim46

потому и поставлен (?) :)
интуитивно кажется, что прямая действительно будет изменяться непрерывно, разве нет?
в смысле, она конечно не вокруг фиксированной точки будет вращаться, но тем не менее...

Jakov

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

Vadim46

нет, она будет задевать синие точки, но это будут "моменты разрыва", в них она будет проходить через две синие точки.
если нарисовать конкретный пример, например, когда синие точки расположены в вершинах квадрата, это видно наглядно.

Jakov

в них она будет проходить через две синие точки.
а если всего точек нечетное число?

Vadim46

ну в этом случае мы их не пополам делим, а на части a и b например.
в моменты разрыва прямая будет проходить через 2 точки, с одной стороны от нее будет a-1 точек, а с другой b-1.

Jakov

балин
спираль что ли будет?
вот так будем крутить крутить крутить
прямая когданить совпадет со своим когдалишним положением?
если да то ты нечетное кол-во точек парами пересчитал
тьфу
надоело пытаться вытянуть плавающее решение
решение должно быть четким, понятным
фраз типа "чутьчуть подвинем" там быть не должно

lenmas

типа "чутьчуть подвинем"
Не "подвинем", а "пошевелим". :)

Vadim46

прямая когданить совпадет со своим когдалишним положением?
ну да, совпадет через 180 градусов.
хотя нет, гоню, для разделения на неравные половины это не проходит.
если да то ты нечетное кол-во точек парами пересчитал
некоторые точки могут пересекаться несколько раз, что видно в случае треугольника например.
ну в общем я согласен, конечно, что это надо как-то обосновывать, но интуиция мне подсказывает, что задача решается так.

v1160908

Пусть прямая задаётся уравнением y=kx+b, заменим такую прямую [k;b] точкой (k;b а точку (x;y) прямой [x;-y]. Тогда задача сведётся к тому, что есть 10 синих и 10 красных прямых, нужно найти точку, у которой сверху 5 красных и 5 синих прямых (с некоторыми ограничениями, естественно). Эта задача очевидно из соображений непрерывности решается.

blackout

С помощью этой идеи доказывается еще, что через внутреннюю точку выпуклого многоугольника можно провести прямую так, чтобы эта точка была серединой отрезка, образованного пересечением прямой и многоугольника.

iri3955

Для каждого напраления рассмотрим красную прямую, которая разделяет красные на 2 равные по кол-ву группы и лежит наиболее далеко от них (т.е. до групп расстояние от нее одинаково, в том числе может быть 0, если 2 точки лежат вдоль направления и должны принадлежать разным группам, назовем такой случай вырожденным). Так же построим синюю прямую. Каждая из прямых задается направлением (углом расстоянием (со знаком, так как у нас есть направление) от центра тяжести всех точек.
Причем функция расстояния от направления непрерывна (легко проверяется явно, отдельно рассматриватся вышеупомянутый вырожденный случай). Тогда у нас есть 2 непрерывных функции (красная и синяя которые при проходе от 0 до 180 меняют значение на противоположное, а значит в какой-то точке они совпадают. Так как никакие 3 не лежат на одной прямой, данная прямая либо не проходит ни через одну точку (тогда мы победили либо тока через 2 красные, либо только через 2 синие. Пусть красные. Возьмем серидину отрезка, соединяющего эти красные точки, тогда поворачиваем ее вокруг этой точки на половину минимального угла, образуемого одной из этих красных точек, выбранным центром, и любой из оставшихся точек, и получим искомую прямую

iri3955

С помощью этой идеи доказывается еще, что через внутреннюю точку выпуклого многоугольника можно провести прямую так, чтобы эта точка была серединой отрезка, образованного пересечением прямой и многоугольника.
Эта задача попроще. Сделаем центральную симметрию относительно точки, получим отреженный контур. Он пересекает исходный хотя бы в одной точке, посткольку они ограничивают фигуры равной площади, содержащие общую точку. Через эту точку пересечения и надо провести прямую

Vadim46

Эта задача очевидно из соображений непрерывности решается.
Вот это мне непонятно.

Suebaby

Вот это мне непонятно.
множество точек, лежащих между N синими и другими N синими прямыми — это область между 2 ломаными. при этом у этих двух ломаных есть в сумме 4 бесконечно длинных ребра (луча). Они (как максимум) лежат лишь на двух направлениях. Вообще глобально (сверху, когда все точки пересечения всех прямых в кучке) область может выглядеть как объединение двух плоских углов с противонаправленными сторонами или как две полуполосы с параллельными краями. Ну и в середине нечто, эти плоские углы (или полуполосы) соединяющее.
То же верно и про "красную" область. При этом обе не могут быть полосами, т.к. тогда у нас есть 4 параллельных прямых. Тогда очевидно, что "красная" и "синяя" области пересекаются.

Vadim46

ага, ясно. на бесконечности справа прямые упорядочиваются по коэффициенту k, а при равенстве — по свободному члену b. На бесконечности слева — в обратном порядке. Поэтому слева и справа получаются бесконечные области, зажатые между одной и той же парой прямых.
При этом обе не могут быть полосами, т.к. тогда у нас есть 4 параллельных прямых.
тогда у нас есть 2 пары параллельных прямых, что вроде бы ничему не противоречит

Suebaby

Поэтому слева и справа получаются бесконечные области, зажатые между одной и той же парой прямых.
не обязательно одной и той же
нарисуй, что будет если у нас две пары параллельных синих прямых (напр. 2 с k=1 и 2 с k=-1)
тогда у нас есть 2 пары параллельных прямых, что вроде бы ничему не противоречит
да, ты прав
я хотел сказать, что эти 2 полосы не должны быть параллельны, а тогда они пересекаются

Vadim46

не обязательно одной и той же
нарисуй, что будет если у нас две пары параллельных синих прямых (напр. 2 с k=1 и 2 с k=-1)
да, точняг
я хотел сказать, что эти 2 полосы не должны быть параллельны, а тогда они пересекаются
но нам-то нужно пересечение полуполос слева и справа, насколько я понял? а они не обязаны пересекаться, даже если не параллельны. и даже если есть красная полуполоса и синий угол, они могут не пересекаться.

Vadim46

а, от параллельных прямых вообще можно избавиться, если в изначальной задаче выбрать оси координат так, чтобы никакие две точки не лежали на прямой, параллельной осям.

Suebaby

но нам-то нужно пересечение полуполос слева и справа, насколько я понял? а они не обязаны пересекаться, даже если не параллельны. и даже если есть красная полуполоса и синий угол, они могут не пересекаться.
чаво? нам нужно пересечение двух фигур, каждая из которых есть
(а) либо два противонаправленных плоских угла, соединённых многоугольниками до связной фигуры
(б) либо две сонаправленных полуполосы, соединённых многоугольниками до связной фигуры
очевидно, что любые две фигуры типа (а) пересекаются
очевидно, что любые две фигуры разных типов пересекаются
очевидно, что любые две фигуры типа (б) пересекаются, если полуполосы фигур не сонаправленны

Vadim46

а если в этом примере
две пары параллельных синих прямых (напр. 2 с k=1 и 2 с k=-1)
мы хотим найти множество точек, лежащих ровно под одной прямой? получается несвязная фигура из двух непараллельных полос.
на бесконечности действительно понятно, что происходит, а внутри, по-моему, не очень.

Suebaby

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

Suebaby

можно так
если есть n непрерывных (линейных на самом деле) функций f1,f2,..fn, то их "моменты" (максимум всех, второе значение, ..., предпоследнее значение, минимум) — тоже непрерывные (кус-лин на деле)

Vadim46

нет, получается плоский угол, смотрящий вниз.
да нет же.
получается связная (через точку) фигура из двух непараллельных полос
вот так, да?
две такие фигуры могут не пересекаться.

v1160908

Вот это мне непонятно.
Ну, можно так. Выберем систему координат так, чтобы коэффиценты наклона всех получившихся прямых были различны. Тогда если при очень маленьком x (отрицательном с большим модулем) красная область (множество всех точек, у которых выше и ниже поровну красных прямых) будет выше синей, то при достаточно большом будет наоборот (легко проверяется). А поскольку, например, верхняя граница обеих областей - непрерывная функция от x, то они обязаны будут пересечься.

Vadim46

в случае, когда надо разделить на неравные части, это не проходит, насколько я понимаю.
а, ну да, для разделения на неравные части утверждение задачи неверно :o

v1160908

а, ну да, для разделения на неравные части утверждение задачи неверно
опередил :D
Оставить комментарий
Имя или ник:
Комментарий: