Комбинаторная геометрия
Немного теории
Олимпиадные задачи этого раздела относятся к разнообразным оценкам, связанным с размещениями, покрытиями, упаковками и замощениями, различными комбинациями фигур. Здесь используются самые общие свойства, связанные с расположением фигур на плоскости и в пространстве. Отметим лишь следующие:
Теорема Жордана: любая несамопересекающаяся замкнутая ломаная делит плоскость на две области – внутреннюю и внешнюю, причём любой путь из точки внутренней области в точку внешней пересекает эту ломаную, а две точки каждой области можно соединить путём, не пересекающим ломаной.
Выпуклое множество – это множество, которое вместе с каждыми двумя точками содержит и весь отрезок, соединяющий эти точки.
Выпуклая оболочка фигуры – это наименьшее выпуклое множество, содержащее эту фигуру; выпуклая оболочка конечного множества – многоугольник (в пространстве – многогранник) с вершинами в некоторых из данных точек.
Вместе с данной фигурой бывает полезно рассмотреть её r-окрестность: множество точек, наименьшее расстояние от которых до точек фигуры меньше чем r.
Две фигуры (в частности, точки) находятся на расстоянии не меньшем 2r, если и только если их r-окрестности не пересекаются.
Если объединение нескольких фигур содержит данную фигуру F, то говорят, что эти фигуры образуют покрытие фигуры F. При этом покрывающие фигуры могут пересекаться.
Упаковка – это размещение внутри данной фигуры нескольких фигур, не имеющих общих точек, кроме, быть может, граничных.
В некоторых задачах фигура разрезается на меньшие части (например, на две одинаковые), или наоборот, из нескольких данных фигур составляется одна большая. Это – задачи на разрезание или замощение. Замощение является одновременно покрытием и упаковкой.
Задачи с решениями
1. Можно ли покрыть равносторонний треугольник двумя равносторонними треугольниками меньшего размера?
Каждый из меньших треугольников может покрыть только одну вершину большего, но вершин три, а треугольников только два.
Ответ: нельзя.
2. Из пяти данных окружностей любые четыре проходят через одну точку. Докажите, что найдётся точка, через которую проходят все пять окружностей.
Пусть
1-я, 2-я, 4-я и 5-я окружности проходят через точку А;
1-я, 3-я, 4-я и 5-я – через точку В;
2-я, 3-я, 4-я и 5-я – через точку С.
Мы видим, что все три точки А, В и С не могут быть различными, так как они лежат на 4-й и 5-й окружностях, а две окружности имеют не больше двух точек пересечения. Значит, согласно принципу Дирихле, какие-то две из точек А, В и С совпадают.
Пусть, например, совпадают точки А и В. Тогда все окружности проходят через точку А. Доказательство завершено.
3. На какое наименьшее число неперекрывающихся тетраэдров можно разбить куб?
Легко видеть, что куб можно разбить на 5 тетраэдров. На рисунке это тетраэдры АА'В'D', АВ'ВС, АСDD', В'С'D'С и АСD'В'.
Докажем теперь, что на меньшее число тетраэдров разбить куб нельзя. Пусть куб с ребром а разбит на несколько тетраэдров. Имеются, по крайней мере, два из них, основания которых лежат на грани АВСD куба. Точно так же имеются по крайней мере 2 тетраэдра с основаниями на грани А'В'С'D'.
Эти тетраэдры заведомо отличны от первых двух, так как у тетраэдра не может быть двух параллельных граней. Итак, у нас уже есть 4 тетраэдра. Их общий объем не больше чем 2а3/3, то есть меньше объёма куба. Таким образом, на 4 тетраэдра куб разбить нельзя.
Ответ: 5.
4. На окружности отмечено n точек. Сколько существует незамкнутых несамопересекающихся (n–1)-звенных ломаных с вершинами в этих точках?
Первую точку можно выбрать n способами. Каждую из следующих n–2 точек можно выбрать двумя способами, так как она должна быть соседней с одной из ранее выбранных точек (иначе получится самопересекающаяся ломаная). Поскольку начало и конец при таком подсчёте не различаются, результат нужно разделить на 2. Следовательно, всего имеется
n·2n–2/2 = n·2n–3
ломаных.
Ответ: n·2n–3.
5. а) Выбраны шесть цветов, и требуется раскрасить шесть граней куба в разные цвета. Сколькими различными способами можно это сделать? (Различными считаются те раскраски, которые нельзя совместить одну с другой при помощи вращений куба вокруг его центра.)
б) Сколькими различными способами можно раскрасить грани додекаэдра в двенадцать цветов?
a) Куб можно повернуть так, чтобы грань, окрашенная первым цветом, заняла заданное положение. Для окраски противоположной ей грани есть пять различных вариантов; разные раскраски противоположной грани дают различные раскраски куба.
Среди оставшихся четырёх граней можно выбрать грань, окрашенную данным цветом, и перевести её в данное положение (не меняя при этом положение первых двух граней). Разные раскраски трёх оставшихся граней дают различные раскраски куба. Одну из этих граней можно окрасить тремя способами, одну из оставшихся – двумя. Всего получаем
5 · 3 · 2 = 30
различных раскрасок.
Ответ: 30 способами.
б) Количество всех возможных раскрасок додекаэдра равно 12! = 1 · 2 · ... · 12. Чтобы найти число различных раскрасок, нужно поделить 12! на число самосовмещений додекаэдра. Любую из 12 граней можно перевести в любую другую. Кроме того, есть пять поворотов (включая тождественный), сохраняющих данную грань. Всего получается 60 самосовмещений. Поэтому количество различных раскрасок додекаэдра равно
12! / 60 = 7983360.
Ответ: 7983360 способами.
6. В плоскости дано конечное множество многоугольников, каждые два из которых имеют общую точку. Докажите, что некоторая прямая пересекает все эти многоугольники.
Спроектируем все многоугольники на некоторую прямую. Проекция каждого многоугольника является отрезком, причём по условию любые два отрезка имеют общую точку. Отсюда следует, что все отрезки имеют общую точку (чтобы убедиться в этом, достаточно рассмотреть данную прямую как числовую ось и взять наименьший из правых концов этих отрезков). Прямая, перпендикулярная к данной и проходящая через отмеченную точку, пересекает все многоугольники.
7. Каждая точка плоскости окрашена в красный или голубой цвет. Докажите, что найдется прямоугольник, все вершины которого окрашены в один и тот же цвет.
Согласно принципу Дирихле, из семи точек не меньше четырёх должны иметь одинаковый цвет. Выберем из семи точек на прямой p четыре точки Р1, Р2, Р3, Р4, окрашенные в один цвет, скажем, в красный. Рассмотрим ещё две прямые q и r, параллельные прямой р, и две четверки точек на них (Q1, Q2, Q3, Q4) и (R1, R2, R3, R4), полученные ортогональным проектированием выбранной четвёрки на эти прямые. Рассмотрим прямоугольники с вершинами в этих точках и в точках Р1, Р2, Р3, Р4. Теперь, если две из точек, например, Qi и Qj – красные, то все точки прямоугольника РiQiQjРj также красные. Аналогично и для двух красных точек из R1, R2, R3, R4.
Если ни один из этих случаев не имеет места, то некоторые три (или более) точек на прямой q и три (или более) точек на прямой r должны быть голубыми. Но эти тройки голубых точек расположены так, что среди них обязательно найдутся по паре точек, лежащих одна под другой и, таким образом, образующие голубой прямоугольник, откуда и следует утверждение задачи.
Замечание: отметим, что этот результат справедлив для любой области на плоскости, заключённой внутри сколь угодно малой окружности.
8. Через фиксированную точку пространства проводим плоскости так, чтобы разделить пространство на возможно большее число частей. Одна плоскость разделит пространство на две части, две пересекающиеся плоскости – на четыре части, три пересекающиеся в некоторой точке плоскости и не имеющие другой общей точки делят пространство на восемь частей.
а) Какое максимальное число частей можно получить при четырех плоскостях?
б) Какое – при n плоскостях?
Вместо всего пространства будем делить шар, через центр которого проводим плоскости. На поверхности шара (на ограничивающей его сфере) возникнут взаимно пересекающиеся большие окружности. Примем одну из них за экватор и все эти окружности спроектируем из центра шара на плоскость, касательную к шару в полюсе. Проекциями наших окружностей (за исключением одной, являющейся экватором и вовсе ни во что не проектирующейся) будут прямые. Следовательно, нужно вычислить максимальное число областей плоскости, разделенной n–1 прямыми. Методом индукции можно получить (смотрите задачу 9 в разделе «Метод математической индукции»), что оно равно
1 + 1 + 2 + 3 + . . . + (n–1) = 1 + n(n–1)/2.
Так как на сфере имеется вдвое больше областей, чем на её плоской проекции (помним об экваторе, который присутствует на сфере и отсутствует на плоскости проекции), то искомое число будет вдвое больше вычисленного нами выше, следовательно, оно равно 2 + n(n–1).
В частности, при n = 4 искомым числом является 14.
Ответ: а) 14; б) 2+n(n–1).
9. Имеется несколько квадратов, сумма площадей которых равна 4. Докажите, что такими квадратами всегда можно покрыть квадрат площади 1.
Если покрывать квадрат набором квадратов, сторона каждого из которых уменьшена до ближайшего меньшего числа вида 1/2k, k = 1, 2, ... , то эти квадраты можно разместить без наложений (смотрите рисунок).
Поскольку площадь каждого квадрата уменьшилась менее чем в 4 раза, то сумма их площадей больше 1, так что они заведомо покроют весь квадрат.
10. Необходимо разделить треугольник на 19 треугольников так, чтобы в каждой вершине полученной фигуры (а также в вершинах большого треугольника) сходилось одинаковое число сторон. Число 19 нельзя заменить большим числом, но можно заменить меньшими числами. Какими же?
Чтобы разделить треугольник на некоторое число треугольников так, чтобы в каждой вершине образованной фигуры сходилось одинаковое число сторон, воспользуемся правильными многогранниками, грани которых являются треугольниками. Это могут быть следующие многогранники: правильные тетраэдр, октаэдр и икосаэдр, и только они.
Если внутри тетраэдра мы выберем точку, лежащую близко от центра одной из граней, и из этой точки спроектируем рёбра тетраэдра на плоскость, то получим первую фигуру, изображенную на следующем рисунке.
Она состоит из трех треугольников, соответствующих граням тетраэдра; четвертая грань при проектировании перешла в большой треугольник ABC. В каждой вершине фигуры сходятся три стороны, так как в каждой вершине тетраэдра сходятся три ребра.
Подобным же образом, при помощи центральной проекции, получим из правильного октаэдра вторую фигуру на рисунке, состоящую из семи треугольников, в каждой вершине которой сходится четыре стороны, а из правильного икосаэдра – третью фигуру, состоящую из 19 треугольников, в каждой вершине которой сходится пять сторон.
Не существует фигуры, отвечающей условиям задачи и отличающейся от изображенных трёх, так как ей соответствовал бы правильный многогранник, отличающийся от трёх упомянутых выше, а такого не существует.
Итак, возможное число треугольников, меньшее 19 – это 4 и 7.
Задачи без решений
1. На столе лежат 15 журналов, полностью покрывая его. Докажите, что можно убрать 7 журналов так, чтобы оставшиеся покрывали не менее 8/15 площади стола.
2. В пространстве заданы четыре точки, не лежащие в одной плоскости. Сколько имеется различных параллелепипедов, для которых эти точки служат вершинами?
3. В выпуклом n-угольнике (n > 3) проведены все диагонали, причём никакие три из них не пересекаются в одной точке. Найдите число точек пересечения диагоналей.
4. Докажите, что нельзя покрыть всю плоскость сетью треугольников так, чтобы в каждой вершине сходилось пять треугольников.
5. На плоскости проведено n прямых (n > 2), делящих плоскость на несколько областей. Некоторые из этих областей окрашены, причем никакие две окрашенные области не могут соприкасаться по границе. Докажите, что число окрашенных областей не превосходит n(n+1)/3.
Создано на конструкторе сайтов Okis при поддержке Flexsmm - накрутка телеграм