Пересечение отрезков и прямых

Оценка. Для начала докажем, что больше самопересечений быть не может. Назовём звенья одного направления горизонтальными, а звенья второго направления — вертикальными. Расположим плоскость так, чтобы горизонтальные звенья действительно стали горизонтальными. Заметим сразу две вещи:

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

Пронумеруем сверху вниз горизонтальные звенья от до . Посмотрим на звено с номером . Каждое пересекающее его вертикальное ребро должно иметь над ним конец, совпадающий с концов некоторого горизонтального ребра. Горизонтальных рёбер выше всего , поэтому на -м ребре не более точек самопересечений. Эта оценка хорошо работает для от до : на них суммарно не более

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

Для ребра с номером немного улучшим оценку: всего существует вертикальных рёбер, но два из них выходят из концов -го звена, поэтому не могут его пересекать. Итого, на звене не более точек самопересечений. Значит, суммарно их не больше

Пример. Пронумеруем и вертикальные звенья тоже. Пусть -е вертикальное ребро соединяет и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья; -е вертикальное ребро — и горизонтальные звенья.

Аналогичный пример для -звенной ломаной на картинке ниже:

(a) Возьмём одну из данных прямых и рассмотрим все точки пересечения данных прямых, не лежащие на выбранной прямой, и выберем среди них ближайшую. Среди кусков, на которые разрезана плоскость, есть треугольник, одна вершина которого — выбранная точка, а две другие лежат на выбранной прямой. Действительно, треугольник, образованный выбранной прямой и двумя прямыми, проходящими через выбранную точку, не могут пересекать другие прямые. Мы сопоставили каждой прямой треугольник, причём один и тот же треугольник не может соответствовать более чем трём разным прямым. Поэтому количество треугольников не меньше

(b) Докажем, что если проведено прямых, то число треугольников не меньше

Рассмотрим все точки пересечения данных прямых. Докажем, что эти точки могут лежать по одну сторону не более чем от двух данных прямых. Предположим, что все точки пересечения лежат по одну сторону от трёх данных прямых. Эти прямые образуют треугольник Четвёртая прямая не может пересекать только стороны этого треугольника, т.е. она пересекает хотя бы одно продолжение стороны. Пусть для определённости она пересекает продолжение стороны за точку в некоторой точке Тогда точки и лежат по разные стороны от прямой Получено противоречие. Поэтому имеются по крайней мере прямые, по обе стороны от которых лежат точки пересечения. Если мы выберем в полуплоскости, заданной прямой ближайшую к точку пересечения, то эта точка будет вершиной треугольника, прилегающего к прямой Таким образом, имеется не менее прямых, к которым прилегает по крайней мере по два треугольника, и две прямые, к каждой из которых прилегает хотя бы один треугольник. Так как каждый треугольник прилегает ровно к трём прямым, то треугольников не менее При получаем не менее треугольников. Значит, количество треугольников не меньше

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

Теперь берём пару отрезков. Пусть это отрезки с концами и считаем В каком случае они пересекается? В том, когда Учитывая, что могут быть любой парой, замечаем следующее: общее количество пересечений отрезков равно количеству случаев, когда в перестановке большее число стоит раньше меньшего (не обязательно по соседству). Как сказали бы старшие товарищи, число пересечений равно числу инверсий в перестановке. Так и будем говорить дальше.

Например, — нет инверсий и нет пересечений, — одна инверсия ( и — инверсий ( и и и и и и Наибольшее количество инверсий будет, если написать числа задом наперёд: какие два числа не выбери — большее будет стоять раньше. То есть инверсий в последнем примере а в общем случае —

Как посчитать число перестановок с заданным количеством инверсий? Подойдём к задаче индуктивно. В фигурных скобках будем указывать различные перестановки, а в квадратных перечислим количества перестановок, имеющих соответственно инверсий.

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

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

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

Так же будет происходить добавление нового числа в общем случае: число можно поставить на любое место, и в зависимости от места к инверсиям добавится штук. То есть на новом шаге перестановка с инверсиями превращается в перестановок с инверсиями соответственно.

Посмотрим, какие числа получались в квадратных скобках. Напишем эти последовательности одну под другой:

Здесь в строке (нумерация начинается с ) приводятся числа для равные количеству перестановок из чисел с инверсиями.

Вспоминая, как происходит добавление нового получим

Действительно, — количество перестановок из (n-1) чисел, в которых уже есть инверсий. В них мы вынуждены поставить новое на последнее место ( инверсий). Раз мы ставим на единственно возможное место, количество перестановок не изменится.

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

Продолжаем так вплоть до потому что добавить больше инверсии нельзя. Всего получается слагаемых. Из других перестановок предыдущей строки мы ничего нового получить не сможем.

Заметим, что так как не бывает перестановок с отрицательным числом инверсий, как и не может быть перестановок со слишком большим (больше чем ) количеством инверсий.

Итак, имеем следующий способ построения коллекции

Первая строчка:

По строчке ползёт «окно» шириной Попавшие в «окно» числа складываются и выписываются в следующую (2-ю) строку:

Вторая строка:

По ней будет ползти окно шириной Сложение попавших в окно чисел даст третью строку:

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

Выпишем (без нулей) первые строк нашей коллекции и выберем в ней нужное нам

Получаем ответ

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

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

Предположим, что все отмеченные точки лежат на одной прямой. В этом случае, очевидно, получается всего одна прямая.

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

Пусть никакие три точки не лежат на одной прямой. Тогда прямые через любые две точки различны, и нам достаточно лишь посчитать количество неупорядоченных пар из двух точек. Сначала посчитаем количество упорядоченных пар. Первую точку можно выбрать способами, вторую — способами, и эти количества способов надо перемножить, так как выбор точек последовательный и независимый. Итого получается упорядоченных пар. Неупорядоченных же вдвое меньше, так как каждой неупорядоченной паре соответствуют две упорядоченные. Значит, неупорядоченных пар точек , и прямых тоже .

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

Докажем, что каждая прямая, которая пересекает , также пересекает и прямую . Пусть есть прямая , которая пересекает , но не пересекает . Тогда прямые и параллельны. Но по условию и тоже параллельны. Поэтому и прямые и параллельны. Это противоречит тому, что они пересекаются, значит, все-таки верно, что любая прямая, пересекающая , также пересекает и .

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

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

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

Итак, если бы все прямые пересекались, но никакие три не пересекались бы в одной точке, точек пересечения было бы . Но по условию среди прямых есть две параллельные. Это значит, что пропадает одна точка пересечения. Поэтому на самом деле точек пересечения на одну меньше, то есть .

Предположим, что указанная в условии конструкция существует. Назовем точки пересечения и . Разберем два случая.

Случай 1. Среди нарисованных прямых есть прямая, проходящая через и . Назовем ее . Так как и  — точки пересечения хотя бы двух прямых, то через каждую из точек проходит еще хотя бы одна прямая, отличная от . Назовем эти прямые и соответственно. Прямые и не могут пересекаться в точках и , так как проходят каждая ровно через одну из этих точек. Значит, они параллельны. Рассмотрим четвертую прямую, отличную от , и . Если эта прямая проходит через какую-то из точек и , пусть , то она точно пересекает прямую в точке, отличной от , и мы получаем третью точку пересечения. Если эта прямая не проходит через точки и , то она не параллельна хотя одной из прямых и , значит, она пересекает одну из прямых и в точке, отличной от и , и вновь получилась лишняя точка пересечения.

Случай 2. Среди нарисованных прямых нет прямой, проходящей через и . Пусть через точку проходят две прямые и . Через точку должна проходить еще одна прямая, назовем ее . Тогда пересекает одну из прямых и (так как она не может быть одновременно параллельна двум пересекающимся прямым). Мы получили еще одну точку пересечения, отличную от и .

Итак, мы рассмотрели все случаи, и во всех случаях пришли к противоречию. Значит, описанной в условии конструкции не существует.

Заметим, что любые две прямые пересекаются не больше чем в одной точке. Значит, точек пересечения не больше, чем неупорядоченных пар прямых. Упорядоченных пар , так как первая прямая выбирается способами, вторая — способами, и выбор последовательный и независимый. Неупорядоченных пар половина, так как каждой неупорядоченной паре соответствую две упорядоченные. Таким образом, неупорядоченных пар , и точек пересечения не больше .

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

Если бы все точки пересечения диагоналей были различны, для их подсчёта достаточно было бы посчитать общее количество способов выбрать 4 вершины -угольника. Действительно, каждая пара пересекающихся диагоналей даёт нам 4 вершины; с другой стороны, для каждых 4 вершин отрезок, соединяющий первую и третью по часовой стрелке, и отрезок, соединяющий вторую и четвёртую, будут пересекающимися диагоналями (сторонами они не могут быть, так как стороны ни с чем не пересекаются). Количество таких способов составляет

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

Во-первых, поскольку количество вершин чётно, "длинных"диагоналей (соединяющий противоположные вершины многоугольника) пересекаются в центре многоугольника. Эта точка посчитана

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

Во-вторых, для каждой "длинной"диагонали можно взять две симметричные относительно неё диагонали, не проходящие через центр многоугольника. "Длинную"диагональ можно выбрать способами. Для удобства представим себе, что выбранная диагональ расположена вертикально. По каждую сторону от этой диагонали остаётся вершина. Мы выбираем вершину слева от “длинной” диагонали, после чего для выбора вершины справа у нас остаётся варианта: мы не можем выбрать вершину, симметричную относительно "длинной"диагонали (иначе диагональ будет симметрична сама себе) и вершину, симметричную относительно центра, иначе будет "длинной а эти точки пересечения мы уже учли.

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

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

точек меньше.

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

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

Предположим противное. Выберем для каждого чёрного отрезка белый, не пересекающийся с ним. Такой белый отрезок лежит либо левее соответствующего чёрного, либо правее. Следовательно, есть хотя бы чёрных отрезков, для каждого из которых его белый отрезок лежит по одну и ту же сторону от него (пусть, для определённости, левее). Для каждого из этих чёрных отрезков его левый конец лежит правее правого конца соответствующего ему белого отрезка.

Тогда, если мы выберем из правых концов белых отрезков самый левый, то он будет левее хотя бы левых концов чёрных отрезков, то есть этот белый отрезок не будет пересекаться ни с одним из этих отрезков. Противоречие.

Раз только две прямые параллельны, то у нас есть различных направлений прямых. Заметим, что любые две прямые разных направлений пересекаются в некоторой точке. Тогда всего их будет — число способов выбрать две прямые разных направлений и плюс ещё , которые даёт вторая параллельная прямая. Всего пересечения. Так как есть три прямые, которые пересекаются в одной точке, то одно из пересечений мы посчитали раза, а значит, настоящее количество точек пересечения равно .

Предположим противное. Заметим, что через каждую точку пересечения двух прямых проходит красная прямая. Рассмотрим синюю прямую пусть — две наиболее удалённые друг от друга точки пересечения с красными прямыми, и — красные прямые, проходящие через и — точка пересечения и Тогда через проходит синяя прямая которая пересекает в какой-то точке отрезка иначе и — не наиболее удалённые (cм. рис.).

Рассмотрим все четвёрки прямых расположенных как — одного цвета; — другого; пересекаются в одной точке; точка пересечения и лежит между точками пересечения с и и рассмотрим среди них такую, в которой прямые образуют треугольник наименьшей площади (cм. рис.). Тогда через точку проходит прямая одноцветная с Она пересекает либо отрезок либо (пусть, для определенности, Тогда прямые образуют конфигурацию с треугольником меньшей площади. Противоречие.

Спроецируем все прямоугольники на оси координат. Рассмотрим сначала проекции на ось для каждого прямоугольника получим отрезок Выберем:

• Самый левый из всех правых концов проекций:
• Самый правый из всех левых концов проекций:

Заметим, что точка принадлежит как минимум отрезку. Аналогично, точка принадлежит как минимум отрезку. Тогда общее количество отрезков, содержащих хотя бы одну из этих точек, не менее

Поскольку всего отрезков то количество отрезков, содержащих обе точки и будет:

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

Суммарное количество “хороших” проекций на обеих осях:

Покажем, что это число превышает общее количество прямоугольников:

Это неравенство выполняется, так как для целой части справедливо:

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