Тема КОМБИНАТОРИКА

Комбинаторная геометрия → .02 Пересечение отрезков и прямых

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

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

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

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

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

Разделы подтемы Комбинаторная геометрия

Расположение точек, отрезков и прямых

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

Общая точка, прямая, покрытие. Теорема Хелли

Разрезания и геометрические конструкции в текстовых

Конструктивы в комбигео

Принцип крайнего, индукция и другие методы в комбигео

Клетчатая решётка (координатная плоскость) и точки, отрезки, прямые на ней

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

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

Задача 1#119820

Пусть $n >3$ — натуральное число. Сколько существует способ выбрать два не пересекающихся прямоугольника внутри квадрата $n× n,$ идущих по линиям сетки? Прямоугольники пересекаются, если у них есть хотя бы одна общая внутренняя клетка или общая точка на границе.

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Для начала разберите случай, когда не пересекаются "горизонтальные" интервалы. А сколько тогда способов будет для "вертикальных" интервалов?

Подсказка 4

Если "горизонтальные" интервалы не пересекаются, то вертикальные можно выбрать абсолютно любыми! Аналогично и со случаем, когда не пересекаются "вертикальные" интервалы. Осталось лишь проверить, не посчиталось ли ничего лишнего ;)

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

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

Сначала посчитаем количество способов, при которых горизонтальные интервалы не пересекаются. Пусть эти интервалы — $[a,b]$ и $[c,d].$ Поскольку порядок прямоугольников не имеет значения, без потери общности можно предположить, что $a< c,$ то есть $a <b< c< d.$ Тогда количество способов выбрать $a,b,c,d$ равно $4 Cn+1.$ На вертикальные интервалы ограничений нет, поэтому количество способов выбрать их равно $2 2 (C n+1) .$ Таким образом, общее количество пар прямоугольников с непересекающимися горизонтальными интервалами равно $4 2 2 Cn+1⋅(C n+1) .$ По симметрии, количество пар прямоугольников с непересекающимися вертикальными интервалами такое же.

Осталось посчитать и вычесть количество способов, при которых и горизонтальные, и вертикальные интервалы не пересекаются. Пусть горизонтальные интервалы — $[a,b]$ и $[c,d],$ а вертикальные — $[e,f]$ и $[g,h].$ Без потери общности можно предположить $a< b< c< d,$ поэтому оличество способов выбрать горизонтальные интервалы равно $C4n+1.$ Однако случаи $e <f <g <h$ и $g <h < e<f$ теперь различны, поэтому количество способов выбрать вертикальные интервалы равно $2⋅C4n+1.$ Следовательно, количество пар прямоугольников, у которых и горизонтальные, и вертикальные интервалы не пересекаются, равно $2 ⋅(C4n+1)2.$

Ответ:

$2⋅C4 ⋅(C2 )2 − 2⋅(C4 )2 n+1 n+1 n+1$

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

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

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

Задача 2#126314

По кругу в некотором порядке выписаны все натуральные числа от 1 до 100 включительно. Пара не соседних чисел $a$ и $b$ называется хорошей, если все числа, выписанные по одну из сторон от хорды, соединяющей $a$ и $b,$ меньше $a$ и $b.$ Какое количество хороших пар чисел может содержаться среди выписанных, в зависимости от порядка записи? Найти все возможные значения.

Источники: Всесиб - 2025, 10.5 ( см. sesc.nsu.ru)

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

Подсказка 1

Попробуйте выписать числа от 1 до n по часовой стрелке. Какие пары будут хорошими?

Подсказка 2

Все пары, содержащие число n, кроме каких?

Подсказка 3

Кроме тех пар, в которых содержатся соседние с n числа. Получим целых n-3 хороших пар. :)

Подсказка 4

Давайте попробуем доказать, что их всегда будет n-3. Воспользуйтесь методом математической индукции.

Подсказка 5

Можно перебором доказать базу для n = 4.

Подсказка 6

Осталось доказать переход. Мы добавляем ещё одно число. Какое число не содержит ни одна хорошая пара?

Подсказка 7

Этим число будет единица. А что будет, если мы её выкинем?

Подсказка 8

Заметим, что есть хорошая пара соседних с 1 чисел, которая пропадает при вычёркивании единицы.

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

Первое решение

Если записать числа от 1 до $n$ по часовой стрелке, то хорошими будут все пары, содержащие число $n,$ кроме пар соседних с $n$ чисел $(n;1)$ и $(n;n − 1).$ Всего $n− 3$ пары.

Докажем индукцией по $n,$ что если по кругу выписаны все натуральные числа от 1 до $n,$ то количество хороших пар всегда равно $n − 3$ вне зависимости от порядка записи.

База индукции: $n = 4.$

Числа от 1 до 4 можно выписать по кругу четырьмя различными способами:

(1234);(1243);(1324);(1423)

Хорошими в них будут единственные пары:

(-2 4);( 2-3);( 3 4);( 4 3)

При этом $n− 3= 4− 3= 1.$ База индукции выполнена.

Шаг индукции.

Пусть утверждение индукции выполнено для всех количеств чисел от 4 до $n,$ докажем для $n+ 1.$ Рассмотрим все натуральные числа от 1 до $n+ 1,$ выписанные в произвольном порядке. Заметим, что ни одна хорошая пара чисел не содержит число 1, и пара чисел, записанных слева и справа от 1, образуют хорошую пару. Назовем такую пару маленькой.

Теперь вычеркнем единицу, получим $n$ выписанных чисел от 2 до $n +1.$ Пары, которые были хорошим для исходных $n+ 1$ чисел, кроме маленькой, останутся хорошими и для полученных $n$ чисел, верно и обратное.

Количество хороших пар для полученных $n +1$ чисел, по предположению индукции, равно $n +1− 3= n− 2.$ Все эти пары останутся хорошими, если вернуть назад вычеркнутую единицу, и ещё к ним добавится новая пара чисел — маленькая. Всего получаем $n − 2+ 1= n− 1= n+ 1− 3$ хороших пар, что доказывает шаг индукции.

В итоге ответ — 97 хороших пар чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение

Рассмотрим произвольную запись по кругу в некотором порядке всех натуральных чисел от 1 до 100. Будем считать их расположенными в вершинах правильного 100-угольника, обозначим его $C.$ Сначала докажем, что хорды, соответствующие двум разным хорошим парам чисел, не могут пересекаться по внутренним точкам.

Рассмотрим две хороших пары чисел $a< b,$ $c< d,$ в которых все 4 числа различны. Можно считать, что $a <c.$ Если хорды, соответствующие этим парам, пересекаются по внутренней точке, то числа $c$ и $d$ лежат по разные стороны от хорды $ab$ и оба больше $a,$ что противоречит «хорошести» пары $(a;b).$

Теперь предположим, что проведены хорды для всех хороших пар выписанных чисел. Как мы только что доказали, они не пересекаются по внутренним точкам, поэтому разбивают наш 100-угольник на несколько многоугольников с вершинами в вершинах 100-угольника. Если среди них есть многоугольник $M$ с более, чем тремя вершинами, рассмотрим самое маленькое из чисел в вершинах $M,$ обозначим его за $x,$ соседние с ним в $M$ числа обозначим за $y$ и $z.$ Рассмотрим возникающие при этом варианты расположения соответствующих им вершин в 100-угольнике $C.$

1) Все три числа $x,y,z$ записаны в трёх последовательных вершинах $C.$ Тогда $yz$ будет хорошей хордой $C,$ что противоречит предположению о том, что все хорошие хорды уже проведены.

2) Одна из пар $(x;y),$ $(x;z)$ является хорошей в $C,$ а вторая образует пару соседних вершин $C.$ Можно считать, что хорошей является пара $(x,y).$ Так как $x< z,$ все числа, лежащие в $C$ относительно $z$ с другой стороны от хорды $xy,$ меньше $x.$ Тогда хорда $yz$ снова будет не проведённой хорошей хордой $C.$

3) $(x;y)$ и $(x;z)$ являются хорошими в $C.$ В этом случае, так как $x< z,$ $y <z,$ маленькие числа для хорды $xy$ лежат в $C$ с другой относительно $z$ стороны, а маленькие числа для хорды $xz$ лежат в $C$ с другой относительно $y$ стороны. Следовательно, хорда $yz$ будет непроведенной хорошей хордой 100-угольника, у которой маленькие числа расположены в $C$ с той же стороны, что и $x.$ При том числа $y,x,z$ записаны в трёх последовательных вершинах многоугольника $M$ с более, чем тремя вершинами, поэтому $yz$ не может быть стороной $M,$ и тем более стороной $C.$

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

Сумма величин всех углов 100-угольника $C$ равна $98⋅180∘$ (сумма внутренних углов выпуклого $n$ -угольника равна $(n− 2)⋅180∘).$ В данной ситуации, когда все вершины треугольников лежат в вершинах $C,$ она равна сумме углов во всех треугольниках разбиения. Сумма углов в каждом треугольнике разбиения равна $180∘,$ поэтому общее число треугольников разбиения равно 98. В общем числе $3⋅98$ сторон всех треугольников разбиения каждая хорда учитывается дважды, а каждая сторона — один раз. Следовательно, количество проведённых хороших хорд равно $(3⋅98− 100):2= 97$ для любого порядка записи чисел от 1 до 100 в его вершинах.

Ответ:

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

Задача 3#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

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

Задача 4#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.$

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

Задача 5#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

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

Задача 6#71014

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

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

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

C26 ⋅C28 = 420.

Ответ: 420

Курсы

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

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

Задача 7#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

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

Задача 8#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

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

Задача 9#33925

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

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

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

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

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

Ответ: 65

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

Задача 10#35622

На плоскости нарисованы $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$ .

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

$PIC$

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

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

Задача 11#35623

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

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

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

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

$PIC$

Ответ: 105

Интенсивы

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

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

Задача 12#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

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

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

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

Задача 13#77011

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

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

Подсказка 1

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

Подсказка 2

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

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

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

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

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

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

Задача 14#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

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

Задача 15#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′$ образуют конфигурацию с треугольником меньшей площади. Противоречие.

$PIC$

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

Задача 16#119315

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

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

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

Самый левый из всех правых концов проекций: $L = min b i$
Самый правый из всех левых концов проекций: $R = maxai$

Заметим, что точка $L$ принадлежит как минимум $n +1$ отрезку. Аналогично, точка $R$ принадлежит как минимум $n+ 1$ отрезку. Тогда общее количество отрезков, содержащих хотя бы одну из этих точек, не менее $2(n+ 1).$

Поскольку всего отрезков $[43n],$ то количество отрезков, содержащих обе точки $L$ и $R,$ будет:

[ ] 2(n+ 1)− 4n > 0 3

Заметим, что такие отрезки пересекают все остальные, так как в них полностью лежит отрезок $[L;R],$ а его все пересекают по выбору $L,R.$ Аналогичные рассуждения проводим для проекций на ось $OY.$

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

( [4 ]) 2 2(n+ 1)− 3n

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

( [ ]) [ ] [ ] 2 2(n+ 1)− 4n > 4n ⇔ 4(n +1)> 3 4n 3 3 3

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

[ ] 3 4n ≤ 3⋅ 4n =4n <4(n+ 1) 3 3

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

Предыдущая подтема

Следующая подтема