Тема Комбинаторная геометрия

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторная геометрия

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#90452

На плоскости нарисована замкнутая 222-звенная ломаная. Известно, что два соседних звена ломаной перпендикулярны друг другу, а также никакие два звена ломаной не лежат на одной прямой. Какое наибольшее количество точек самопересечений может иметь такая ломаная?

Источники: Турнир Ломоносова - 2024, 11.5 (см. turlom.olimpiada.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Да, верно! Каждая точка самопересечения — это пересечение вертикального и горизонтального отрезка, а каждого типа по 111 штук. Пронумеруем горизонтальные отрезки и посмотрим на произвольный (пусть k-ый) из них. Попробуйте оценить, сколько точек самопересечения с горизонтальными отрезками выше k-ого образуют вертикальные отрезки, пересекающий данный.

Подсказка 3

Точно! Не более 2(k-1) точек самопересечения. Отлично! Теперь мы можем оценить общее кол-во точек самопересечения. Однако наша оценка работает хорошо только для первой половины отрезков. Попробуйте для второй половину оценить аналогично, только снизу.

Подсказка 4

Так, попробуем ещё докрутить оценку для центрального (то есть 56-ого) горизонтального отрезка. У нас из всех 111 вертикальных отрезка 2 выходят из нашего. Тогда как мы можем оценить кол-во точек пересечения для 56-ого горизонтального отрезка?

Подсказка 5

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

Показать ответ и решение

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

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

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

0+ 2+4 +...+ 2⋅54= 2970

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

Для ребра с номером $56$ немного улучшим оценку: всего существует $111$ вертикальных рёбер, но два из них выходят из концов $56$ -го звена, поэтому не могут его пересекать. Итого, на $56$ звене не более $109$ точек самопересечений. Значит, суммарно их не больше $2⋅2970+109= 6049.$

Пример. Пронумеруем и вертикальные звенья тоже. Пусть $⋅1$ -е вертикальное ребро соединяет $55$ и $56$ горизонтальные звенья; $⋅2$ -е вертикальное ребро — $54$ и $57$ горизонтальные звенья; $⋅3$ -е вертикальное ребро — $53$ и $58$ горизонтальные звенья; $...$ $⋅55$ -е вертикальное ребро — $1$ и $110$ горизонтальные звенья; $⋅56$ -е вертикальное ребро — $1$ и $111$ горизонтальные звенья; $⋅57$ -е вертикальное ребро — $2$ и $111$ горизонтальные звенья; $⋅58$ -е вертикальное ребро — $3$ и $110$ горизонтальные звенья; $⋅59$ -е вертикальное ребро — $4$ и $109$ горизонтальные звенья; $...$ $⋅111$ -е вертикальное ребро — $56$ и $57$ горизонтальные звенья.

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

$PIC$

Ответ: 6049

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#92971

На плоскости проведено $300$ прямых, причем никакие две из них не параллельны и никакие три не пересекаются в одной точке. Докажите, что среди областей, образованных ими, есть не менее (a) $100$ (b) $200$ треугольников.

Подсказки к задаче

Подсказка 1 пункт а

Прямых 300, от нас хотят 100 треугольников, поэтому разумно каждой прямой сопоставить 1 какой-то треугольник.

Подсказка 2 пункт а

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

Подсказка 1 пункт б

Решение пункта а можно немного изменить. Если брать треугольники с двух сторон, то их будет 200. Такое решение не работает, потому что все точки могут лежать по одну сторону. Как можно решить эту проблему?

Подсказка 2 пункт б

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

Показать доказательство

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

(b) Докажем, что если проведено $n≥ 3$ прямых, то число треугольников не меньше $2n−2 -3-.$

Рассмотрим все точки пересечения данных прямых. Докажем, что эти точки могут лежать по одну сторону не более чем от двух данных прямых. Предположим, что все точки пересечения лежат по одну сторону от трёх данных прямых. Эти прямые образуют треугольник $ABC.$ Четвёртая прямая не может пересекать только стороны этого треугольника, т.е. она пересекает хотя бы одно продолжение стороны. Пусть для определённости она пересекает продолжение стороны $AB$ за точку $B$ в некоторой точке $M.$ Тогда точки $A$ и $M$ лежат по разные стороны от прямой $BC.$ Получено противоречие. Поэтому имеются по крайней мере $n− 2$ прямые, по обе стороны от которых лежат точки пересечения. Если мы выберем в полуплоскости, заданной прямой $ℓ,$ ближайшую к $ℓ$ точку пересечения, то эта точка будет вершиной треугольника, прилегающего к прямой $ℓ.$ Таким образом, имеется не менее $n − 2$ $2$ прямых, к которым прилегает по крайней мере по два треугольника, и две прямые, к каждой из которых прилегает хотя бы один треугольник. Так как каждый треугольник прилегает ровно к трём прямым, то треугольников не менее $(2(n − 2)+ 2)∕3.$ При $n= 100$ получаем не менее $19913$ треугольников. Значит, количество треугольников не меньше $200.$

Ошибка.
Попробуйте повторить позже

Задача 3#67944

∙ ∙ ∙ ∙ ∙ ∙

∙ ∙ ∙ ∙ ∙ ∙

Есть два ряда — верхний и нижний, каждый из 6 точек (см. рисунок). Проводят отрезки с концами в противоположных рядах так, чтобы из каждой точки выходил ровно один отрезок. Сколько существует способов провести отрезки, чтобы среди всех пар отрезков было ровно 7 пар пересекающихся отрезков?

Источники: Ломоносов-2023, 10.8 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

В таких задачах полезно посмотреть на случаи поменьше, с меньшим количеством отрезков и необходимых пересечений

Подсказка 2

Когда два отрезка пересекаются? Когда начало первого левее, чем начало второго, а конец первого правее, чем конец второго

Подсказка 3

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

Подсказка 4

Мы можем поставить второй конец в самую правую точку. Тогда у нас останется k пересечений.

Подсказка 5

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

Подсказка 6

Общая формула будет иметь вид

Показать ответ и решение

Пусть в каждом ряду по $n$ точек. Способ соединить точки можно задать перестановкой $n$ чисел, ${i ,i ,...,i }: 1 2 n$ первая точка верхнего ряда соединяется с точкой под номером $i1,$ вторая — с $i2,$ и так далее. Значит, всего возможных рисунков будет $n!.$

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

Например, $12345$ — нет инверсий и нет пересечений, $21345$ — одна инверсия ( $2$ и $1),$ $43152$ — $6$ инверсий ( $4$ и $3,$ $4$ и $1,$ $4$ и $2,$ $3$ и $1,$ $3$ и $2,$ $5$ и $2).$ Наибольшее количество инверсий будет, если написать числа задом наперёд: $54321,$ какие два числа не выбери — большее будет стоять раньше. То есть инверсий в последнем примере $10,$ а в общем случае — $C2n.$

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

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

{1}; [1]

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

{◟1◝2◜}◞ , {◟2◝1}◜◞ ; [1,1] 0 инверсий1инверсия

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

{◟12◝◜3}◞,{◟2 ◝13◜} ◞,{◟13 ◝2◜} ◞,{2◟3 ◝1◜} ◞,{◟31◝◜2}◞,{◟3 ◝21◜} ◞, [1,2,2,1] 0+0 1+0 0+1 1+1 0+2 1+2

Так же будет происходить добавление нового числа $n$ в общем случае: число $n$ можно поставить на любое место, и в зависимости от места к инверсиям добавится $+ 0,+1,+2,...,+(n − 1)$ штук. То есть на новом шаге перестановка с $l$ инверсиями превращается в $n$ перестановок с $l+0,l+1,l+2,...,l+(n− 1)$ инверсиями соответственно.

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

$pict$

Здесь в $n- й$ строке (нумерация начинается с $1$ ) приводятся числа $Pkn$ для $k =0,1,...,Ckn,$ равные количеству перестановок из $n$ чисел с $k$ инверсиями.

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

Pnk= Pkn−1 + Pkn−−11 + Pkn−−21+ ⋅⋅⋅+ Pkn−−n1+1 ◟+ ◝0◜и ◞нв. +◟1 ◝◜ин ◞в. +◟2 ◝◜ин◞в. +◟(n−◝1◜)и◞нв.

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

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

Продолжаем так вплоть до $P k− n+1, n−1$ потому что добавить больше $(n− 1)$ инверсии нельзя. Всего получается $n$ слагаемых. Из других перестановок предыдущей строки мы ничего нового получить не сможем.

Заметим, что $P−k =0, n$ так как не бывает перестановок с отрицательным числом инверсий, как и не может быть перестановок со слишком большим (больше чем $C2 n$ ) количеством инверсий.

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

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

...0 0◟◝◜0◞0 0 0 1 0 0 0 0 0 0... −→

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

...0(◟0◝ 0◜)◞1 0 0 0 ... ...0 0(0◟◝◜1)◞0 0 0 ... ...0 0 0(◟1◝ 0◜)◞0 0 ... ...0 0 0 1(◟0◝ 0◜)◞0 ... =0 =1 =1 =0

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

...0 0 0 0 0 0 1 1 0 0 0 0 0 0 ... ◟◝−→◜◞

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

...0 0 0 0 0 1 2 2 1 0 0 0 0 0 ... ◟-◝−→◜-◞

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

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

$pict$

Получаем ответ $101.$

Ответ: 101

Ошибка.
Попробуйте повторить позже

Задача 4#71014

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

Источники: Надежда энергетики-2023, 11.1 (см. www.energy-hope.ru)

Подсказки к задаче

Подсказка 1

Нас просят найти количество попарных пересечений! Для начала давайте разберемся, а когда образуется одно попарное пересечение?

Подсказка 2

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

Подсказка 3

Первые два дома нужно выбрать из 6, а вторые два из 8. То есть, это просто число сочетаний из 6 по 2 и число сочетаний из 8 по 2!

Показать ответ и решение

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

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

C26 ⋅C28 = 420

Ответ: 420

Ошибка.
Попробуйте повторить позже

Задача 5#33923

На плоскости отметили $4$ точки. Через любые две провели прямую. Сколько различных прямых при этом могло получиться? Найдите все ответы.

Показать ответ и решение

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

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

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

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

Ответ: 1, 4, 6

Ошибка.
Попробуйте повторить позже

Задача 6#33924

На плоскости проведены несколько прямых. Известно, что прямые $a$ и $b$ параллельны. Прямую $a$ пересекают $10$ прямых. Сколько прямых пересекают прямую $b$ ?

Показать ответ и решение

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

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

Ответ: 10

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#33925

В каком числе точек пересекаются $12$ прямых, если никакие три не пересекаются в одной точке, и среди прямых есть ровно $2$ параллельные?

Показать ответ и решение

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

Посчитаем сначала количество упорядоченных пар прямых. Первую прямую можно выбрать $12$ способами, вторую — $11$ способами. Эти количества надо перемножить, так как выбор последовательный и независимый. Получается $12⋅11 =132$ упорядоченные пары прямых. При этом неупорядоченных пар ровно вдвое меньше, так как каждую неупорядоченную пару можно упорядочить ровно двумя способами. Значит, неупорядоченных пар $132 :2=66$ .

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

Ответ: 65

Ошибка.
Попробуйте повторить позже

Задача 8#33928

На плоскости проведены $10$ прямых, среди которых нет параллельных, но есть ровно три прямые $a$ , $b$ и $c$ , проходящие через одну точку. Сколько точек пересечения этих прямых получилось?

Показать ответ и решение

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

Посчитаем сначала количество упорядоченных пар. Их $10⋅9= 90$ , так как первую прямую можно выбрать $10$ способами, вторую — $9$ способами, и выбор последовательный и независимый. Неупорядоченных пар вдвое меньше, так как каждой неупорядоченной паре соответствуют две упорядоченные. Получается $90:2= 45$ неупорядоченных пар.

Теперь вернемся к нашей задаче. У нас три прямые пересекаются в одной точке. Это значит, что для трех пар прямых, а именно пар $a$ , $b$ ; $a$ , $c$ и $b$ , $c$ , точки пересечения совпадают. Поэтому вместо трех точек пересечения мы получаем одну точку пересечения. Значит, общее количество точек пересечения уменьшается на $3− 1= 2$ . Итого не $45$ , а $45− 2 =43$ точки пересечения.

Ответ: 43

Ошибка.
Попробуйте повторить позже

Задача 9#33932

На плоскости нарисованы $5$ прямых. Может ли оказаться, что эти прямые имеют ровно $2$ точки пересечения?

Показать ответ и решение

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

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

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

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

Ответ: Нет, не может

Ошибка.
Попробуйте повторить позже

Задача 10#33935

Можно ли провести $7$ прямых так, чтобы они пересекались ровно в $9$ точках?

Показать ответ и решение

Один из возможных примеров приведен на рисунке. На нем $4$ прямые параллельны, а еще три попарно пересекаются на этих параллельных прямых.

Ответ: Да, можно

Ошибка.
Попробуйте повторить позже

Задача 11#33937

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

Показать ответ и решение

Заметим, что любые две прямые пересекаются не больше чем в одной точке. Значит, точек пересечения не больше, чем неупорядоченных пар прямых. Упорядоченных пар $15⋅14= 210$ , так как первая прямая выбирается $15$ способами, вторая — $14$ способами, и выбор последовательный и независимый. Неупорядоченных пар половина, так как каждой неупорядоченной паре соответствую две упорядоченные. Таким образом, неупорядоченных пар $210:2= 105$ , и точек пересечения не больше $105$ .

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

Ответ: 105

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#35496

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

Показать ответ и решение

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

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 13#35622

На плоскости нарисованы $5$ прямых. Может ли оказаться, что эти прямые имеют ровно $2$ точки пересечения?

Показать ответ и решение

$PIC$

Ответ: Нет, не может

Ошибка.
Попробуйте повторить позже

Задача 14#35623

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

Показать ответ и решение

$PIC$

Ответ: 105

Ошибка.
Попробуйте повторить позже

Задача 15#35625

Отметьте на плоскости $9$ точек так, чтобы можно было начертить $10$ различных прямых, на каждой из которых лежит по $3$ отмеченные точки.

Показать ответ и решение

Пример приведен на рисунке ниже.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 16#74585

Дан правильный $n$ -угольник $(n= 4k+ 2),$ в котором проведены все диагонали. Докажите, что они образуют не больше

n(n-− 1)(n-− 2)(n-− 3) n (n ) n (n ) ( n ) 24 − 4 ⋅ 2 − 1 + 1− 2 ⋅ 2 − 1 ⋅ 2 − 3

точек пересечения (не считая вершин).

Источники: ИТМО-2022, 11.7 (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

Нам дали уж слишком какое-то магическое число, но каждое его слагаемое похоже на какой-то комбинаторный подсчёт. Может быть, у нас получится объяснить, как получить каждое из этих слагаемых?

Подсказка 2

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

Подсказка 3

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

Подсказка 4

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

Подсказка 5

2-ое слагаемое: верно, это центр нашего многоугольника. Остаётся только посчитать, сколько раз мы посчитали её и вычесть так, чтобы по итогу в нашем подсчёте точка осталась учтена.

Подсказка 6

3-е слагаемое: оно явно содержит похожие диагонали на те, которые мы выбирали, когда рассуждали про центр, потому что в нём тоже фигурирует n/2. Может быть стоит опять порассуждать про такие диагонали?

Подсказка 7

3-е слагаемое: первый множитель в слагаемом это n/2, давайте тогда зафиксируем какую-то диагональ, проходящую через центр многоугольника. Попробуйте понять, что означают остальные множители, последовательно распутывая, за что отвечает каждый из множителей.

Подсказка 8

3-е слагаемое: верно, слева и справа от диагонали осталось по n/2-1 точке. А значит, вторым действием мы скорее всего выбрали с одной из сторон одну из точек. Почему тогда последний множитель не такой же, а имеет на 2 точки меньше? Понятно, что, выкинув 2 точки с другой стороны, мы запретили какие-то 2 диагонали, остаётся понять - какие?

Подсказка 9

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

Подсказка 10

3-е слагаемое: да, можно, если отразить симметрично вторую диагональ относительно "центральной".

Подсказка 11

3-е слагаемое: а вы заметили, что на самом деле это слагаемое содержит в себе удвоенное количество ситуаций, про которые мы рассуждали? Ведь, когда мы брали диагональ-1 с концами по разные стороны от "центральной" диагонали и отражали её, то получалась диагональ-2, которая тоже может быть посчитана нашими рассуждениями, а так как симметричная для 2-ой диагонали - 1-ая, то мы посчитали всё дважды. А сколько раз мы посчитали такие ситуации в 1-ом слагаемом?

Подсказка 12

Верно, по 3 раза, потому что там мы выбираем неупорядоченную пару диагоналей, а в наших рассуждениях мы получали неупорядоченные тройки диагоналей (если учесть, что мы посчитали их дважды), а значит 1 наша тройка содержит по 3 пары. Но вычесть всё равно придётся удвоенное количество, поэтому мы победили!!!

Показать доказательство

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

n(n− 1)(n− 2)(n− 3) --------24--------

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

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

n (n ) 2-⋅-2 −-1 2

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

n ( n ) 2 ⋅-2 −-1-− 1 2

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

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

n (n ) ( n ) 2 ⋅ 2 − 1 ⋅ 2 − 3 --------2--------

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

n (n ) ( n ) 2 ⋅ 2 − 1 ⋅ 2 − 3

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

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

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#77011

На прямой дано $2n− 1$ черных и $2n− 1$ белых отрезков. Каждый пересекает хотя бы $n$ отрезков другого цвета. Докажите, что найдется отрезок одного из двух цветов, пересекающий все отрезки другого цвета.

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Проверьте для каждого из этих белых отрезков, пересекают ли они хотя бы n чëрных отрезков, или нет.

Показать доказательство

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

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

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

Ошибка.
Попробуйте повторить позже

Задача 18#38872

Определите, в каком количестве точек пересекаются $10$ прямых, если среди них есть только две параллельные и ровно три из этих прямых пересекаются в одной точке.

Источники: Школьный этап - 2018, Москва, 9.5

Подсказки к задаче

Подсказка 1

С чего бы начать решение этой задачи? Не чертить же все 10 прямых и искать вручную точки пересечения, да и еще со странными условиями : 2 прямые параллельны, 3 пересекаются в одной точке...

Подсказка 2

Может быть стоит рассмотреть все возможные точки пересечения пар прямых? Сколько их?

Подсказка 3

Посчитать точки пересечения пар прямых совсем не трудно : их кол-во = кол-ву способов выбрать пару из 10 прямых (любимые С'шки), потому что две прямые единственным образом задают точку пересечения.

Подсказка 4

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

Подсказка 5

3 прямых пересекаются в одной точке - значит, что одну точку пересечения мы посчитали аж целых 3 раза, тогда нам нужно оставить одну = вычесть 2.

Показать ответ и решение

Раз только две прямые параллельны, то у нас есть $9$ различных направлений прямых. Заметим, что любые две прямые разных направлений пересекаются в некоторой точке. Тогда всего их будет $9 ⋅8∕2$ — число способов выбрать две прямые разных направлений и плюс ещё $8$ , которые даёт вторая параллельная прямая. Всего $44$ пересечения. Так как есть три прямые, которые пересекаются в одной точке, то одно из пересечений мы посчитали $3$ раза, а значит, настоящее количество точек пересечения равно $44− 2= 42$ .

Ответ: 42

Ошибка.
Попробуйте повторить позже

Задача 19#92974

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

Источники: Всеросс., 2002, ЗЭ, 10.8(см. math.ru)

Подсказки к задаче

Подсказка 1

Задачи по комбинаторной геометрии часта решаются рассмотрением чего-нибудь крайнего. Найдите в задаче что-нибудь такое.

Подсказка 2

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

Подсказка 3

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

Показать доказательство

Предположим противное. Заметим, что через каждую точку пересечения двух прямых проходит красная прямая. Рассмотрим синюю прямую $ℓ;$ пусть $A,B$ — две наиболее удалённые друг от друга точки пересечения $ℓ$ с красными прямыми, $m$ и $n$ — красные прямые, проходящие через $A$ и $B,C$ — точка пересечения $m$ и $n.$ Тогда через $C$ проходит синяя прямая $p,$ которая пересекает $ℓ$ в какой-то точке $D$ отрезка $AB,$ иначе $A$ и $B$ — не наиболее удалённые (cм. рис.).

$PIC$

Рассмотрим все четвёрки прямых $l′,m′,n′,p′,$ расположенных как $l,m,n,p(l′,p′$ — одного цвета; $m′,n′$ — другого; $m′,n′,p′$ пересекаются в одной точке; точка пересечения $p′$ и $l′$ лежит между точками пересечения $l′$ с $m′$ и $n′),$ и рассмотрим среди них такую, в которой прямые $l′,m ′,n′$ образуют треугольник наименьшей площади (cм. рис.). Тогда через точку $D ′$ проходит прямая $q′,$ одноцветная с $m ′.$ Она пересекает либо отрезок $B ′C′,$ либо $A′C′$ (пусть, для определенности, $B′C ′),$ Тогда прямые $n′,l′,p′,q′$ образуют конфигурацию с треугольником меньшей площади. Противоречие.