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

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

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела комбинаторная геометрия
Решаем задачу:

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

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

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!