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

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

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

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

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

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

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

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

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

Задача 1#82622

В таблице $n ×m$ отметили $k$ клеток. Для какого наименьшего $k$ гарантированно можно выбрать $3$ отмеченные клетки, центры которых образуют прямоугольный треугольник?

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

Сначала покажем, что можно отметить не более $m +n − 2$ клетки так, чтобы никакие $3$ клетки не образовывали треугольник. Выберем в таблице центры всех клеток нижней строки и правого столбца, за исключением правой нижней угловой клетки. Всего выбрано $m +n − 2$ точки, и каждая тройка отмеченных точек образует тупоугольный треугольник.

Докажем, что больше $m + n− 2$ центров клеток выбрать нельзя. Для каждого отмеченного центра либо в его строке, либо в его столбце других отмеченных центров нет. Пометим этот ряд. Если помечены все строки, то выбрано всего не больше $m ≤ m +n − 2$ центров. Аналогична ситуация, когда помечены все столбцы.

Если же помечены не все строки и не все столбцы, то всего отмечено не более $m − 1$ строк и не более $n− 1$ столбцов: $(m − 1)+ (n − 1)= m +n − 2.$

Отсюда следует ответ $m + n− 1.$

Ответ:

$m + n− 1$

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

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

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

Задача 2#98988

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

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

Подсказка 1

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

Подсказка 2

Нам хорошо подойдут углы. Внутренняя точка вносит вклад 360°, а вершина квадрата 90°. С другой стороны, это можно представить и как сумму углов в треугольниках.

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

Сумма углов треугольников с вершиной в некоторой вершине квадрата равна $90∘,$ каждая из отмеченных $100$ точек даёт вклад, равный $∘ 360 .$ Поскольку других вершин треугольников нет, то сумма углов всех треугольников разбиения равна $∘ ∘ ∘ 100⋅360 + 4⋅90 = 202⋅180 .$ Поскольку сумма углов треугольника равна $∘ 180 ,$ то количество треугольников равно $202.$

Ответ:

$202$ треугольников

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

Задача 3#71020

Существует ли многоугольник, не имеющий центра симметрии, который можно разрезать на два выпуклых многоугольника, каждый из которых имеет центр симметрии?

Источники: Изумруд-2023, 11.2 (см. izumrud.urfu.ru)

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

Подсказка 1

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

Подсказка 2

На прямоугольники! Составим фигуру из них)

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

Пример:

$PIC$

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

Ответ: да

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

Задача 4#81584

Можно ли отметить на плоскости $3100$ точек так, чтобы для каждой из них существовало не менее $200$ отмеченных точек, расстояние до которых от данной точки составляло бы ровно $1$ метр?

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

Будем строить конструкцию, постепенно увеличивая количество точек. Изначально нарисуем равносторонний треугольник со стороной $1.$ Пусть на очередном шаге на плоскости нарисована конструкция с $n 3$ точками так, что для каждой точки существует не менее $2n$ точек на расстоянии $1$ м от неё. Нарисуем от каждой точки конструкции по равностороннему треугольнику со стороной $1$ так, что соответствующие стороны этих треугольников параллельны друг другу. Нетрудно понять, что в получившейся конструкции будет $n+1 3$ точек и для каждой точки будет не менее $2n+ 2$ точек на расстоянии $1$ от неё. Увеличив исходную конструкцию $99$ раз, получим требуемое.

Ответ:

Можно

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

Задача 5#81902

Целые точки плоскости раскрашены в $2$ цвета. Докажите, что найдется клетчатый квадратик, вершины которого покрашены в один цвет.

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

Докажем, сначала, что для раскраски целочисленных точек в $k$ цветов любом квадрате достаточно большого размер, имеющего целые вершины и границы, параллельные линиям сетки, найдется одноцветный равнобедренный треугольник $ABC,$ у которого $AB$ и $BC$ являются катетами, а также вершина $B$ находится ниже вершины $A$ и правее вершины $C.$ Доказывать это утверждение будем индукцией по $k.$ База для $k= 1$ очевидна. Будем обозначать сторону квадрата из утверждения через $lk.$ Тогда берем $l1 = 2.$ Выберем произвольную горизонтальную прямую. Тогда по теореме ван дер Вардена для отрезка длины $W(k+ 1,2lk)$ найдется одноцветная арифметическая прогрессия длины $2lk$ . Обозначим координаты этих $2lk$ точек через $(x,0),(2x,0),...(2lkx,0)$ (не нарушая общности, можно считать координаты такими), и пусть они все покрашены в первый цвет. Рассмотрим решетку со стороной $x,$ содержащую точку $(0,0).$ Тогда заметим, что точки этой решетки, принадлежащие треугольнику с координатами $(2x,x),(2lkx,x),(2lkx,(2lk− 1)x),$ не могут быть покрашены в первый цвет (иначе требуемый прямоугольный треугольник уже был бы найден). С другой стороны внутрь выделенного треугольника помещается квадрат со стороной $lkx.$ Тогда требуемый прямоугольный треугольник найдется по предположению индукции в данном квадрате (с новой решеткой). В качестве $lk+1$ нам подойдет $W (k+1,2lk).$

Перейдем к решению задачи. Разобьем все целые точки на квадраты со стороной $l2.$ Будем каждый квадрат считать точкой. Цвет квадрата определим как набор цветов его целочисленный точек (то есть всего цветов не больше $2 2(l2+1)$ ). Тогда по ранее доказанному найдется равнобедренный прямоугольный треугольник с вершинами — квадратами. Но в каждом таком квадрате есть равнобедренный прямоугольный треугольник. Тогда имеем конструкцию как на рисунке. Будем считать, что наши цвета это белый и черный, и три найденный треугольника покрашены в белый цвет. Заметим. что вершины, дополняющие каждый треугольник до квадрата должны быть окрашены в черный (иначе мы бы уже нашли квадрат). Но тогда посмотрим на обведенную точку. Легко видеть, что независимо от ее цвета мы найдем требуемый квадрат.

$PIC$

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

Задача 6#92420

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

a) $n= 84$ ?

б) $n= 86?$

Источники: Высшая проба - 2021, 11.3 (см. olymp.hse.ru)

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

а) Цветов не может быть больше 42, иначе есть цвет, в который покрашен только один дом, тогда домов этого цвета ни в каком отрезке не может быть строго больше, чем любого другого.

_________________________________________________________________________________________________________________________________________________________________________________

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

Назовем 38-блоком следующую конструкцию: подряд стоят 38 домов, пары домов на расстоянии 19 (т.е. такие, между которыми ровно 18 других домов)покрашены в один цвет, и больше этого цвета домов нет (не только в блоке но вообще из участвующих домов); 2-блоком назовем стоящие подряд два дома, покрашенные в уникальный цвет. 84 дома надо раскрасить так: 2-блок, 38-блок, два 2-блока, 38-блок, 2-блок.

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

_________________________________________________________________________________________________________________________________________________________________________________

б) Этот же пример позволяет реализовать 42 цвета на 86 домах — в конец добавим еще два дома, цвет которых совпадает с последним 2-блоком. Теперь постараемся доказать оценку в условиях данного пункта.

_________________________________________________________________________________________________________________________________________________________________________________

Понятно что каждого цвета должно быть хотя бы два дома, значит, ответ для $n= 86$ не больше 43 . Если для $n= 86$ ответ 43 , то каждого цвета ровно два дома. Занумеруем цвета в порядке их появления слева направо, и пусть дома $i$ -го цвета имеют номера $ai$ и $bi$ , причем $ai < bi$ . По определению $1= a1 < a2 <a3⋅⋅⋅<a43$ . Докажем что $b1 < b2 < b3⋅⋅⋅<b43 = 86$ . Предположим противное, т.е. для каких-то $i< j$ оказалось $bj < bi$ . Вспомнив что $aj < bj$ и $ai < aj$ видим, что $ai < aj < bj < bi$ , то есть любой отрезок, содержащий $ai,bi$ также содержит $aj,bj$ , то есть нет отрезка, на котором домов $i$ -го цвета больше всего — привели предположение к противоречию.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем еще два полезных неравенства: $bi− ai ≤ 19$ — иначе нет отрезка из 20 домов, в который попали оба из $ai,bi;$ и $bi+1 − ai−1 ≥ 21$ — иначе каждый отрезок, содержащий $ai,bi$ , также содержит или $ai− 1,bi−1$ или $ai+1,bi+1$ .

_________________________________________________________________________________________________________________________________________________________________________________

Среди первых 20 номеров ровно одна $b$ -шка, это $b1$ : иначе, если там есть и $b2$ , среди домов от 1 до 20 есть два дома второго цвета, тогда для первого цвета нет отрезка, в котором его больше чем любого другого (поскольку только отрезок $[1,20]$ содержит два дома первого цвета, но он содержит и два дома второго). Значит, среди первых 20 домов ровно 19 -шек. Значит, из соответствующих им $b$ -шек 18 лежат среди 19 номеров от 21 до 39 , то есть там максимум одна $a$ -шка, это может быть только $a20$ . Мы доказали, что $a21 ≥ 40$ . Повторив то же самое рассуждение с другого конца, получим, что $b23 ≤ 46$ . Но это противоречит неравенству $b23− a21 ≥ 21$ (частный случай доказанного выше для $i= 22$ ).

Ответ:

а) 42

б) 42

Курсы

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

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

Задача 7#91949

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

Источники: ММО - 2019, 10.4(см. mmo.mccme.ru)

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

Подсказка 1

Предположим, что искомого треугольника не существует. Ясно, что если зафиксировать любую прямую, то на ней найдется две точки A и B одного цвета (назовем его цветом 1). Где может располагаться третья точка, которая образовывала бы с найденным точками треугольник единичной площади?

Подсказка 2

Пусть расстояние между точками A и B равно d. Тогда искомая точка может располагаться на любой из прямых, расположенных от данной на расстоянии 2/d, (назовем их l₁ и l₂). По предположению, точек цвета 1 на данных прямых нет. А могут ли на прямой AB находится точки цветов, отличных от 1, если на каждой из прямых l₁ и l₂ присутствует 2 и 3 цвет?

Подсказка 3

Несложно показать, что это не могут (разберите случай, когда любые две точки на прямых l₁ и l₂, расстояние между которыми равно d/2, имеют разный цвет и противный ему). Какое естественное свойство при этом накладывается на одну из прямых AB, l₁ и l₂?

Подсказка 4

По крайней мере на одной из этих прямых все точки имеют один и тот же цвет. Что можно сказать о цветах остальных точек плоскости?

Подсказка 5

Они покрашены в цвет, отличный от данной прямой. Как теперь можно завершить решение?

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

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

Пусть на некоторой прямой $l$ есть две точки $A,B$ одного цвета (обозначим этот цвет $1),$ расстояние между которыми равно $d.$ Пусть $l1,l2$ — две прямые, параллельные $l$ и удаленные от нее на расстоянии $2∕d.$ Если на какой-нибудь из этих прямых есть точка цвета $1,$ то она образует с точками $A,B$ треугольник площади $1,$ все вершины которого имеют одинаковый цвет. Если на каждой из прямых $l1,l2$ присутствуют два цвета и на одной из них найдутся две точки одного цвета на расстоянии $d∕2,$ то они вместе с точкой такого же цвета на другой прямой образуют треугольник площади $1,$ все вершины которого имеют одинаковый цвет. Если же на каждой из прямых $l1,l2$ присутствуют два цвета и любые две точки на расстоянии $d∕2$ разных цветов, то любые две точки на расстоянии $d$ будут одного цвета, а значит, на прямой $AB$ все точки имеют цвет $1.$

Пусть теперь все точки некоторой прямой $a$ покрашены в цвет $1.$ Тогда остальные точки плоскости покрашены в два оставшихся цвета. Возьмем прямую, не параллельную $a,$ и две точки $C,D$ на ней одного цвета (обозначим этот цвет $2).$ Если на какой-нибудь из двух прямых, параллельных $CD$ и удаленных от нее на расстояние $2∕CD,$ найдется точка цвета $2,$ то $C,D$ и эта точка образует треугольник площади $1,$ все вершины которого имеют одинаковый цвет. Если же таких точек нет, то найдется треугольник площади $1$ с вершинами цвета $3.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Пусть не все точки плоскости раскрашены в один цвет. Тогда на некоторой прямой присутствуют точки разных цветов: точки $A$ и $B$ цвета $1$ и точка $X$ цвета $2.$ Пусть $A1B1B2A2$ — прямоугольник, в котором $A,B$ середины сторон $A1A2,B1B2$ соответственно, длины этих сторон равны $4∕AB,C1,C2$ — середины $A1B1$ п $A2B2$ соответственно, $D$ — точка, симметричная $C1$ относительно $B1.$

Если среди точек $A1,B1,C1,A2,B2,C2$ есть точка цвета $1,$ она образует искомый треугольник с точками $A,B.$ Если среди точек $A1,B1,C1,A2,B2,C2$ нет точек цвета $1,$ то возможны следующие случаи.

1.: Точки $A1$ и $B1$ (рассуждение для точек $A2$ и $B2$ аналогичны) разного цвета. Тогда цвет $C1$ совпадает с цветом одной из них, например, $A1.$ Если какая-то из точек $A2,C2$ того же цвета, эти три точки образуют искомый треугольник. В противном случае искомым будет треугольник $A2C2B1.$
2.: Если одна из пар $A1,B1$ или $A2,B2$ цвета $2,$ она образует искомый треугольник с точкой $X.$
3.: Если все точки $A1,B1,A2,B2$ цвета $3$ и одна из точек $C1,D$ тоже цвета $3,$ то треугольник $B1C1B2$ или $B1DB2$ искомый. В противном случае треугольник $C1DX$ искомый.

Ответ:

да

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

Задача 8#71905

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

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

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

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

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

$PIC$

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

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

Задача 9#95789

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

$PIC$

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

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

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

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