Отрезки на плоскости

[sbidujko]

На плоскости даны 35 точек, никакие три из которых не
лежат на одной прямой. Некоторые из них соединены
отрезками— их всего 100. Докажите, что какие-то два из этих
отрезков пересекаются. Что будет,если обобщить: при каких $m$ точек и $n$ отрезков всегда будут пересекающиеся?

[Sender]

Тут достаточно вспомнить теорему Фари и формулу Эйлера для планарного графа. Тогда при $n > 3m-6$ граф всегда будет непланарен.

[TOTAL]

sbidujko в сообщении #479369 писал(а):

Докажите, что какие-то два из этих
отрезков пересекаются.

Если отрезки не пересекаются, то их число не превосходит количества рёбер в триангуляции этого набора точек, т.е. не превосходит $102-N,$ где $N$ равно количеству вершин выпуклой облочки набора.

Зачем требуется нележание никаких 3 точек на одной прямой?

[Naf2000]

Мне кажется 100 это перебор, достаточно чтобы было более чем $2N-3$, при $N=35$ достаточно 68 отрезков

[TOTAL]

Naf2000 в сообщении #479480 писал(а):

Мне кажется 100 это перебор, достаточно чтобы было более чем $2N-3$, при $N=35$ достаточно 68 отрезков

В середину тр-ка поставьте точку и соедините её с вершинами. В любой из образовавшихся тр-ков поставьте точку и соедините с вершинами этого тр-ка. И так далее. Добавление одной точки позволяет нарисовать 3 никого не пересекающих ребра. Поэтому для 35 точек можно нарисовать 99 ребер, которые не пересекаются.