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

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

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

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

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

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

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

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

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

Задача 21#71905Максимум баллов за задание: 7

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

Источники: СпбОШ - 2018, задача 11.5(см. www.pdmi.ras.ru)

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

Подсказка 1

Предположим, что в графе нашёлся цикл, пусть также он проходит по горизонтальному отрезку. А что если взять и достроить ромб, примыкающей к a₀. Затем в новом ромбе отметим другую сторону, построим ещё один ромб, и так далее....

Подсказка 2

Попробуйте построением получить конструкцию, которую заведомо пересекает цикл.

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

Пусть в графе нашёлся цикл, и пусть он проходит по горизонтальному отрезку $a 0$ слева направо. Возьмём ромб, примыкающий к стороне $a0,$ и отметим в нём параллельную сторону $a1.$ Возьмём ромб, примыкающий к стороне $a1,$ и отметим в нём параллельную сторону $a2$ и т.д.

Такую же конструкцию провернём в другую сторону: возьмём ромб, примыкающий к отрезку $a0$ с другой стороны, и отметим в нём параллельную сторону $a−1,$ и т.д.

$PIC$

Мы получили “полосу ширины $a$ ”, которая рассекает наш шестиугольник. При этом цикл заведомо пересекает эту полосу, но всё время в направлении слева направо. Это невозможно.

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

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

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

Задача 22#95789Максимум баллов за задание: 7

У Артема есть неограниченный набор фигурок из $4$ кубиков, как на картинке. При каких $n$ он может выложить из них башню в виде параллелепипеда $3 ×3× n?$ Фигурки можно поворачивать.

$PIC$

Источники: Лига открытий - 2018

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

В каждой фигурке $4$ кубика. Каждый слой башни состоит из $9$ кубиков. Общее количество кубиков должно делиться на $4,$ значит, количество слоев должно делиться на $4.$

При $n,$ делящихся на $4,$ разобьем фигурку на кирпичики $3× 3×4$ и разобьем их так, как показано на картинке. Здесь каждой фигурке соответствует цифра и параллелепипед разбит на слои в $1$ клетку.

$PIC$

Ответ:

При всех $n,$ делящихся на $4$

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

Задача 23#102213Максимум баллов за задание: 7

В пространстве расположены $2016$ сфер, никакие две из них не совпадают. Некоторые из сфер — красного цвета, а остальные зеленого. Каждую точку касания красной и зеленой сферы покрасили в синий цвет. Найдите наибольшее возможное количество синих точек.

Источники: Всеросс., 2016, РЭ, 11.6(см. olympiads.mccme.ru)

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

Подсказка 1

Оценка в этой задаче делается совсем не сложным образом. Вам нужно лишь вспомнить, что две сферы могут касаться только в 1 точке. Что же делать с примером? Нужно как-то удачно расположить сферы между собой. Подумайте, как это можно сделать.

Подсказка 2

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

Подсказка 3

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

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

Пусть среди сфер есть $r$ красных и $2016− r$ зелёных. Так как у любых двух сфер максимум одна точка касания, количество синих точек не превосходит $2 2 2 r(2016− r) =1008 − (1008− r) ≤1008.$

Предъявим пример с таким количеством синих точек. Пусть $ℓ$ — некоторая прямая, $α$ — плоскость, перпендикулярная $ℓ$ и пересекающая её в точке $O,$ а $ω$ — окружность с центром $O$ и радиусом $1,$ лежащая в $α.$ Построим $1008$ красных сфер одинакового радиуса $r< 1$ с различными центрами $R1,R2,...,R1008,$ лежащими на $ω.$

$PIC$

Пусть $G1,G2,...,G1008$ — различные точки на $ℓ,$ удалённые от $O$ на расстояния $d1,d2,...,d1008.$ Тогда расстояние между $Gi$ и любой точкой $Rj$ равно $∘ ----- 1+ d2i.$ Значит, если мы построим зелёную сферу с центром $Gi$ и радиусом $∘ ----- 1+ d2i − r,$ она будет касаться всех красных сфер. При этом все точки касания будут попарно различными, поскольку они лежат на отрезках вида $RjGi,$ которые не имеют общих точек, кроме концов. Значит, в нашей конструкции действительно будут отмечены $10082$ синих точек.

Замечание. Все красные сферы в этом примере получаются друг из друга вращением вокруг прямой $ℓ.$ Поэтому, если зелёная сфера, центр которой лежит на $ℓ,$ касается одной красной сферы, то она касается и всех красных сфер.

Ответ:

$10082 =1016064$ точек

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

Задача 24#119330Максимум баллов за задание: 7

Квадрат разбит на $n2 ≥ 4$ прямоугольников $2(n− 1)$ прямыми, из которых $n− 1$ параллельны одной стороне квадрата, а остальные $n − 1$ — другой. Докажите, что можно выбрать $2n$ прямоугольников разбиения таким образом, что для каждых двух выбранных прямоугольников один из них можно поместить в другой (возможно, предварительно повернув).

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

Отсортируем строки и столбцы разбиения по убыванию их размеров: сверху вниз для строк и слева направо для столбцов. Каждый прямоугольник будем нумеровать парой $(i,j),$ где $i$ — номер строки, $j$ — номер столбца.

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

Рассмотрим ширины столбцов $xi$ и высоты строк $yi,$ которые образуют убывающие последовательности. Поскольку исходная фигура — квадрат, имеем:

x1 +x2+ ...+ xn = y1+y2+ ...+ yn

что эквивалентно:

(x1− y1)+ (x2− y2)+...+ (xn− yn)= 0

Из этого следует существование индекса $i,$ для которого выполняется $xi ≥ yi$ и $xi+1 ≤ yi+1$ (или наоборот). В этом случае прямоугольники $(i,i+1)$ и $(i+1,i)$ можно вложить друг в друга.

$PIC$

Рассмотрим путь, проходящий через прямоугольники $(i,i),$ $(i,i+ 1),$ $(i+ 1,i+ 1).$ Заменив в нём прямоугольник $(i,i+ 1)$ на $(i+1,i),$ получим новый путь. При этом прямоугольник $(i+1,i)$ либо вкладывается в соседние прямоугольники пути, либо они вкладываются в него. Таким образом, объединив исходный путь с добавленным прямоугольником, получаем искомые $2n$ прямоугольников.