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

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

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

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

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

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

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

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

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

Задача 1#118089

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

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

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

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

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

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

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

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

Задача 2#118092

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

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

Предположим, что треугольника, гомотетичного данному, удовлетворяющего условию задачи, нет. Рассмотрим кадрат $4× 4.$ Всего существует $16 3$ вариантов его раскраски. Тогда выберем произвольную прямую, параллельную оси $oX,$ и рассмотрим $16 3 + 1$ квадратов $4× 4,$ у которых одна из сторон на этой прямой. Очевидно, найдутся два квадрата, раскрашенных одинаково.

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

Теперь остается продублировать всю эту конструкцию еще раз. Для этого рассмотрим квадрат со стороной $(316+1)⋅4= t.$ Рассмотрим $3t+ 1$ таких квадратов. Два таких квадрата будут раскрашены одинаково. В первом квадрате на нижней стороне найдутся два квадрата $4× 4,$ раскрашенных одинаково, тогда и во втором большом квадрате найдутся два таких же квадрата. Таким образом, конструкция, описанная выше, может быть найдена в обоих квадратах, то есть мы нашли в каждом квадрате прямоугольные треугольники, гомотетичные данному, у которых на нижнем катете красные вершины, при этом на его сторонах параллельно оси $oX$ найдутся синие вершины, а последние вершины этих прямоугольных треугольников зеленые. При этом внутри больших квадратов все расстояния между описанными точками одинаковы. Рассмотрим найденные большие прямоугольные треугольники и продлим гипотенузу одного и катет второго до пересечения так, чтобы образовался новый прямоугольный треугольник, один из катетов которого содержит стороны двух рассматриваемых. Тогда одна из вершин этого треугольника не может быть раскрашена ни в один цвет. Противоречие.

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

Задача 3#118093

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

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

При $k= 1,$ очевидно: все точки одного цвета. Пусть $k≥ 2,$ будем доказывать от противного. Заметим, что среди любых $k +1$ точек найдутся две одноцветные (для определенности будем говорить, что они красного цвета). Рассмотрим две одноцветные точки, лежащие на одной горизонтальной прямой, и треугольник, образованный ими. Тогда третья вершина будет не красной, пусть синей. В любом квадрате размера $(k +1)× (k+ 1)$ найдётся равнобедренный треугольник, у которого вершины на горизонтальном катете одноцветны, а третья — другого цвета.

Теперь рассмотрим квадрат $(k+ 1)× (k+1).$ Точки внутри него индуцируют раскраску квадрата, и всего таких раскрасок $(k+1)2 k .$ Рассмотрим $(k+1)2 M2 = k + 1$ квадратов, лежащих на одной горизонтальной прямой (т.е. при горизонтальных сдвигах переходящих друг в друга). Найдутся два квадрата с одинаковой раскраской, тогда у них внутри найдутся два одинаковых треугольника. Посмотрим на узел в пересечении прямых гипотенузы первого и вертикального катета второго (см. рисунок).

$PIC$

Вершина, отмеченная серым цветом на рисунке, не может быть синего или красного цвета. При $k= 2,$ мы бы уже получили противоречие. Заметим, что построенная конструкция находится в квадрате $M2 ×M2,$ и в любом квадрате такого размера такая конструкция найдется. Повторим построение: рассмотрим $kM22 +1$ квадратов размера $M2.$ Снова найдутся два с одинаковой раскраской и одинаковыми конструкциями внутри. Посмотрим на аналогичную точку пересечения: у неё теперь три запрета на возможные цвета. Размер стороны квадрата, в котором это содержится, обозначим $M3 = (kM22 + 1)M2.$ В любом квадрате со стороной $M3$ найдется конструкция, у верхней вершины которой (серой на рисунках для случаев двух и трёх цветов) будет $3$ запрета на цвет.

$PIC$

Обобщим рассуждения. Пусть $Mi$ — размер квадрата, в котором найдется индуктивно построенная конструкция, причём у верхней вершины будет $i$ запретов на цвет (так как есть $i$ пар точек, лежащих на одной горизонтальной прямой, причём одна из них лежит на гипотенузе, а другая — на вертикальном катете). Повторяя рассуждения для меньших случаев, в квадрате размера $Mi+1 =(kM2i + 1)Mi$ будет лежать конструкция с $i+ 1$ запретом на цвет верхней вершины. Тогда в квадрате со стороной $Mk$ все цвета будут запрещены, что приводит к противоречию.

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

Задача 4#119325

На окружности отметили $n$ точек. Оказалось, что среди треугольников с вершинами в этих точках ровно половина остроугольных. Найдите все значения $n,$ при которых это возможно.

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

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

Умножая количество четырёхугольников на $2,$ получаем нижнюю оценку общего числа тупоугольных треугольников:

2⋅C4n.

Каждый тупоугольный треугольник попадает ровно в $n − 3$ четырёхугольник. Следовательно, истинное количество тупоугольных треугольников хотя бы:

2⋅C4n n(n− 1)(n− 2) n−-3 =-----12-----

Сравнивая с общим числом треугольников $n(n−1)(n−2) C3n = ----6---,$ получаем, что доля тупоугольных не менее половины. Равенство возможно только, если в каждом четырёхугольнике ровно два тупоугольных треугольника, что достигается при $n =4, n = 5.$

Если четыре точки лежат на одной полуокружности, то любой треугольник из трёх таких точек будет содержаться в полуокружности, а значит, центр окружности не попадёт внутрь. Следовательно, все $4$ таких треугольника будут тупоугольными. Для $n> 5$ по принципу Дирихле обязательно найдётся четвёрка точек на одной полуокружности, что нарушит условие равенства половины.

$n =1,n= 2:$ треугольников нет.
$n =3 :$ треугольник один.
$n =4,$ пример на рисунке:

$PIC$
$n =5,$ подходит правильный пятиугольник.

Ответ:

$4,5$

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

Задача 5#121756

При каких $n≥ 2025$ существует такой набор из $n$ прямоугольников, что из них можно собрать прямоугольник (без пустот и наложений), а из любого меньшего их подмножества, состоящего из хотя бы двух прямоугольников, — нельзя?

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

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

Подсказка 1

Попробуйте определить некоторое разбиение (в дальнейшем будем называть его спиральным) клетчатого прямоугольника [(n+1)/2]×[(n+1)/2].

Подсказка 2

Нарисуем спираль, начиная двигаться из угла вдоль короткой стороны прямоугольника, если они не равны. Затем расположим в центре спирали квадратик 1×1, за ним — прямоугольник 1×2, а затем будем накрывать все непокрытые клетки частично покрытого отрезка спирали прямоугольником ширины 1 и соответствующей длины. Что еще нужно сделать в этом разбиении?

Подсказка 3

Нужно построить спиральное разбиение клетчатого прямоугольника со столбцами и строками неравной ширины.

Подсказка 4

Определим ширину столбца i как wᵢ = (n+1)ⁱ⁻¹, а ширину строки j как hⱼ = C ⋅ (n+1)ʲ⁻¹, где С = (n+1)ⁿ⁺³. Теперь разбейте неравномерный клетчатый прямоугольник на меньшие. Какие прямоугольники можно из них сложить?

Подсказка 5

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

Подсказка 6

Что, если в прямоугольнике, сложенном из малых прямоугольников, два прямоугольника ориентированы по-разному?

Подсказка 7

Можно получить противоречие с величиной его площади.

Подсказка 8

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

Подсказка 9

Оцените для любого i количества прямоугольников ширины не более wᵢ и высоты не более hᵢ.

Подсказка 10

Предположим, что мы сложили из подмножества малых прямоугольников некоторый прямоугольник. Заметим, что верхняя сторона этого прямоугольника состоит из сторон малых прямоугольников. Как тогда можно представить ее длину? А длину высоты?

Подсказка 11

Пусть некоторая горизонтальная прямая пересекает прямоугольник и не содержит сторон малых прямоугольников. Чему тогда равна суммарная ширина всех малых прямоугольников, которые пересекает эта прямая?

Подсказка 12

Вычислите, сколько четырёхугольников ширины wᵢ пересекает любая такая прямая.

Подсказка 13

Сколько тогда из них можно сложить прямоугольников, и какого они будут размера?

Подсказка 14

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

Подсказка 15

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

Подсказка 16

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

Подсказка 17

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

Подсказка 18

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

Подсказка 19

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

Подсказка 20

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

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

Для начала определим разбиение клетчатого прямоугольника

⌊n-+1⌋ ⌊n-+1⌋ 2 × 2 ,

которое в дальнейшем будем называть спиральным. Нарисуем спираль, начиная двигаться из угла вдоль короткой стороны прямоугольника, если они не равны. Затем расположим в центре спирали квадратик $1× 1,$ за ним — прямоугольник $1× 2,$ а затем будем накрывать все непокрытые клетки частично покрытого отрезка спирали прямоугольником ширины 1 и соответствующей длины.

Для того, чтобы получить искомое разбиение, построим спиральное разбиение клетчатого прямоугольника со столбцами и строками неравной ширины. Положим ширину столбца $i$ равной

wi =(n+ 1)i−1,

а ширину строки $j$ равной

hj = C ⋅(n +1)j−1,

где $C = (n +1)n+3.$

Далее разобьем неравномерный клетчатый прямоугольник на

⌊ n+ 1⌋ ⌊ n+ 1⌋ -2-- × -2--

прямоугольников (назовем их $малыми$ ) по линиям сетки. Выясним, какие прямоугольники можно сложить из подмножества множества малых прямоугольников.

Заметим, что суммарная площадь малых прямоугольников равна

( ⌈n+1⌉) ( ⌊n+1⌋) 1+ (n+ 1)+...+ (n+ 1) 2 C +C ⋅(n +1)+ ...+ C⋅(n+ 1) 2 <

( ⌈n+1⌉)( ⌊n+1⌋) < C ⋅n2⋅ 1+ (n+ 1)+ ...+(n+ 1)-2- 1 +(n+ 1)+...+(n+ 1)-2- =

( ⌈ ⌉ ) ( ⌊ ⌋ ) = C⋅ (n+ 1)n+21 +1− 1 (n+ 1) n+21+1 − 1 <

⌈n+1⌉+1 ⌊n+1⌋+1 ⌈n+1⌉+⌊n+1⌋+2 n+3 2 < C(n+ 1) 2 (n+ 1) 2 = C(n+1) 2 2 = C(n+ 1) = C

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение 1. Пусть даны некоторые целые неотрицательные числа, не превышающие $n$

′ ′ a1,...,a⌈n+21⌉ и a1,...,a⌈n+21⌉

Тогда если

a1w1+ ...+a⌈n+21⌉w⌈n+21 ⌉ =a′1w1+ ...+ a′⌈n+1⌉w⌈n+21⌉, 2

то $ai =a′i$ для всех $i.$

Предположим, что для некоторых различных наборов $ai$ и $a′i$ оказалось, что

a1w1+ ...+ an+1 w n+1 = a′1w1 +...+ a′n+1w n+1 ⌈2 ⌉ ⌈ 2 ⌉ ⌈ 2 ⌉ ⌈ 2 ⌉

Пусть $k$ — наибольшее число, при котором

′ ak ⁄=ak.

Не умаляя общности положим, что $ak >a′k.$ Тогда

( ) ( ) a1w1+ ...+a⌈n+1⌉w⌈n+1⌉ − a′w1 +...+a′⌈ ⌉w⌈n+1⌉ = -2- -2- 1 n+21 -2-

( ) = (a1− a′1)w1+ ...+ a⌈n+1⌉− a′⌈n+1⌉ w⌈n+1⌉ = (a1− a′1)w1+ ...+(ak− a′k)w⌈n+1⌉ > 2 2 2 2

( k−2) k−1 > (− n)⋅(w1+ ...+ wk−1)+wk = (−n)⋅ 1+ (n+ 1)+ ...+ (n +1) +(n+ 1) =

( k−1 ) k−1 = − (n+ 1) − 1 +(n+ 1) =1 >0

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение 2. Пусть даны некоторые целые неотрицательные числа, не превышающие $n$

′ ′ b1,...,b⌊n+21⌋ и b1,...,b⌊n+21⌋

Тогда если

b1h1+ ...+ b⌊n+21⌋h⌊n+21 ⌋ =b′1h1+ ...+b′⌊n+21⌋h⌊n+21⌋,

то $bi = b′i$ для всех $i.$

Доказывается аналогично утверждению 1.

_________________________________________________________________________________________________________________________________________________________________________________

По построению для любого $i$ малых прямоугольников ширины $wi$ не больше

⌈ ⌉ n+-1 ≤ n, 2

а малых прямоугольников высоты $hi$ не более

⌊n+-1⌋ 2 ≤ n

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

a1w1+ ...+ a⌈n+21⌉w⌈n+21⌉,

где $ai$ — целые неотрицательные числа, не превышающие $n.$ Аналогично, высота прямоугольника представима в виде

b1h1+ ...+ b⌊n+21⌋h⌊n+21⌋,

где $bi$ — целые неотрицательные числа, не превышающие $n.$

Пусть некоторая горизонтальная прямая пересекает прямоугольник и не содержит сторон малых прямоугольников. Тогда суммарная ширина всех малых прямоугольников, которые пересекает эта прямая, равна

a1w1+ ...+ a⌈n+1⌉w⌈n+1⌉ 2 2

Из утверждения 1 следует, что любая такая прямая пересекает ровно $ai$ прямоугольников ширины $wi.$ Значит, из всех прямоугольников ширины $wi$ можно сложить $ai$ прямоугольников размера

wi× (b1h1+ ...+ bn+1 h n+1-) ⌊ 2 ⌋ ⌊2 ⌋

Из утверждения 2 следует, что для каждого такого прямоугольника нам нужно использовать $bi$ малых прямоугольников высоты $hi.$ Получается, для построения нашего прямоугольника нам понадобится не менее $ai⋅bj$ малых прямоугольников размера $wi× hj.$ С другой стороны, все малые прямоугольники различны, а значит, все $ai$ и $bi$ равны либо 0, либо 1.

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

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

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

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

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

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

Получается, $A$ состоит из всех прямоугольников разбиения, что и требовалось.

Ответ:

При всех $n ≥ 2025$

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

Задача 6#121758

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

Источники: Турнир городов - 2025, устный тур, 11.1(см. turgor.ru)

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

Подсказка 1

Давайте попробуем грубо оценить количество точек. Каким свойством для 100-угольника должны обладать его две вершины, чтобы они не могли быть одновременно внутри круга?

Подсказка 2

А что если две точки 100-угольника диаметрально противоположны?

Подсказка 3

Итак, две диаметрально противоположные точки одновременно внутрь круга попасть не могут. Значит, можно сделать оценку на количество вершин! Осталось построить пример.

Подсказка 4

Можно сначала поместить внутрь круга две вершины, а затем на них построить описанную окружность нашего многоугольника!

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

Заметим, что $51$ вершина не помещается, так как тогда среди них нашлись бы две диаметрально противоположные точки, их можно было бы поместить на диаметр круга, и весь $100-угольник$ поместился бы в данном круге вместе со своим описанным кругом, площадь которого больше.

Докажем, что $50$ вершин поместить можно. Заметим, что диагональ, соединяющая $1- ю$ и $50- ю$ вершины — это диаметр вписанного круга $100- угольника,$ площадь этого круга меньше площади $100- угольника.$ Поэтому внутрь диаметра исходного круга $1-я$ и $50-я$ вершины поместятся. Рассмотрим тогда описанную окружность $ω$ нашего $100-угольника.$ Она не может лежать целиком в исходном круге, а значит, пересекается с окружностью исходного круга в двух точках. Тогда одна из дуг окружности $ω$ (на самом деле меньшая) поместится внутри исходного круга, то есть заведомо поместятся $50$ вершин $100- угольника.$

Ответ:

$50$

Курсы

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

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

Задача 7#121765

В трёхмерном координатном пространстве рассмотрим множество всех кубов с целочисленными координатами вершин. Докажите, что в этом множестве существует такое бесконечное подмножество $K,$ что любые два разных куба из $K$ не имеют параллельных рёбер.

Источники: Турнир городов - 2025, устный тур, 11.4(см. turgor.ru)

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

Подсказка 1

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

Подсказка 2

Мы знаем, что существует бесконечно много кубов с непараллельными ребрами. Чтобы их получить, можно просто много раз повернуть какой-нибудь куб. Но что делать с тем, что координаты должны быть целыми?

Подсказка 3

Одна из важных идей — это гомотетия. Если все вершины куба имеют рациональные координаты, то мы можем подобрать коэффициент гомотетии так, чтобы они стали целыми. Но можем ли мы поворачивать куб так, чтобы координаты вершин всех повёрнутых кубов были рациональными? Можем! Осталось только строго расписать задачу: подобрать общий вид направляющих векторов и доказать, что они перпендикулярны.

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

Решение 1. Рассмотрим куб с тремя направляющими векторами рёбер вида $(a,b,c), (b,c,a), (c,a,b),$ где

a= −n, b= n+ 1, c= n(a+1)

Числа $a,b,c$ подобраны так, что

1 1 1 ab+bc+ ca =0 (эквивалентно a + b + c =0),

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

Замечание. Геометрически эту конструкцию можно описать так: векторы рёберстандартного единичного куба $(1,0,0), (0,1,0), (0,0,1)$ поворачивают на подходящий угол вокруг диагонали $(1,1,1)$ (так, чтобы координаты новых векторов оказались рациональными), а затем применяют гомотетию с подходящим коэффициентом, превращающую рациональные координаты в целые.

_________________________________________________________________________________________________________________________________________________________________________________

Решение 2. Рассмотрим куб с тремя направляющими векторами рёбер вида

2 2 2 (2, 2n, n), (2n, n − 2, −2n), (−n , 2n, −2)

Длина каждого ребра равна тогда $n2+2.$ Нетрудно проверить, что векторы попарно перпендикулярны через равенство скалярного произведения нулю. Выбирая $n= 1,2,3,...,$ снова получаем бесконечный набор кубов без параллельных рёбер (никакие два соответствующих вектора не пропорциональны).

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

Задача 8#125076

Прямоугольный параллелепипед размером $6× 7×11,$ разбитый на единичные кубики, проткнули иглой по его диагонали. Сколько единичных кубиков проткнула игла?

Источники: Звезда - 2025, 11.4 ( см. zv.susu.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

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

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

Параллелепипед разрезан на единичные кубики плоскостями трёх семейств, в каждое из которых входят все плоскости, параллельные какой-то грани. Количество этих плоскостей — 5, 6 и 10 соответственно. Заметим, что игла не прокалывает две плоскости из разных семейств в одной точке, пусть в $M.$ Действительно, в таком случае проекция иглы на грань $α$ третьего семейства была бы её диагональю, на которой есть целочисленная точка $P$ — проекция точки $M$ на $α.$ Но очевидно, что если целочисленная точка лежит на диагонали целочисленного прямоугольника внутри его, то стороны прямоугольника не взаимно просты. Итак, игла прокалывает 5, 6 и 11 плоскостей в разных точках, поэтому на игле

5+ 6+ 10 =21

следов её пересечения с гранями кубиков, поэтому количество прокалываемых кубиков равно

21+ 1= 22

Ответ:

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

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

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

Задача 10#98988

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

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

Подсказка 1

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

Подсказка 2

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

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

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

Ответ:

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

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

Задача 11#71020

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

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

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

Подсказка 1

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

Подсказка 2

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

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

Пример:

$PIC$

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

Ответ: да

Интенсивы

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

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

Задача 12#119332

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

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

Разобьем многоугольник на горизонтальные полоски $1× n. n$ В каждой полоске будем двигаться слева направо, в таком же порядке соединяя встретившиеся нам точки. Пусть в некоторой полоске было отмечено $x$ точек. Тогда по горизонтали мы суммарно сместились не более чем на $1,$ а по вертикали — не более чем на $x−-1 n .$ Тогда всего в каждой полоске сумма длин звеньев не превосходит $x 1+ n.$ То есть суммарная длина звеньев в полосках не превосходит $n+ 1⋅n2 = 2n. n$ Теперь осталось лишь соединить ломаные из полосок в одну замкнутую ломаную. Для этого будем идти сверху вниз, переходя в соседнюю полоску. На спуск и переход в сеседнюю полоску мы в люом случае затрачиваем не более $2.$ В конце нам надо будет вернуться в самю верхнюю полоску. Для этого достаточно спуститься на нижнюю границу, пройти вдоль нее (если есть необходимость), затем подняться на верхнюю границу, возможно, пройти вдоль нее, и наконец, замкнуть ломаную. На это мы затратим не более $4.$ Итого, суммарная длина получившейся ломаной не превосходит

2n+ 2+n + n2= 4n+ 2< 10n n

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

Задача 13#81584

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

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

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

Ответ:

Можно

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

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

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

Задача 15#92420

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

a) $n= 84$ ?

б) $n= 86?$

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

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

Подсказка 1

Будем разбираться с пунктами по очереди. Давайте в первом попробуем начать с оценки на количество: наверняка, цветов не может быть n, почему? А (n-1) может получиться? Нам помешает тот цвет, в который будет покрашен только один.

Подсказка 2

Получается, больше n/2 цветов мы использовать не можем, для первого пункта осталось создать пример. Этот же пример с небольшой доработкой подойдет и для второго пункта.

Подсказка 3

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

Подсказка 4

Для полной оценки нужно использовать факты ниже. Наибольший номер дома конкретного цвета i меньше номера дома цвета (i+1) для любого i от 1 до 43. Также разность между наибольшим и наименьшим значением номеров у фиксированного i не более 19, а разность между наибольшим номером цвета (i + 1) и наименьшим номером цвета (i - 1) не менее 21. С этими рассуждениями оценка является полной и верной, ура!

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

а) Цветов не может быть больше 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

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

Задача 16#124037

Существует ли тетраэдр, в сечениях которого двумя разными плоскостями получаются квадраты $100×100$ и $1× 1?$

Источники: ММО - 2020, первый день, 11.5 (см. mmo.mccme.ru)

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

Подсказка 1

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

Подсказка 2

Подумайте о диагоналях параллелипипеда. Сколько у тетраэдра будет квадратных сечений, параллельных парам его скрещивающихся рёбер?

Подсказка 3

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

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

Первое решение. Покажем, что если у тетраэдра два скрещивающихся ребра перпендикулярны и имеют длины $a$ и $b,$ то существует сечение тетраэдра, которое является квадратом со стороной $ab∕(a+ b).$

$PIC$

Разделим четыре остальных ребра тетраэдра в отношении $k:(1− k),$ считая от концов ребра длины $b$ (см. рис.). Соединив точки деления, получим сечение, которое является параллелограммом со сторонами длины $ka$ и $(1− k)b$ в силу подобия треугольников. На самом деле, это сечение является прямоугольником, поскольку стороны параллелограмма параллельны перпендикулярным рёбрам тетраэдра по обратной теореме Фалеса и, следовательно, тоже перпендикулярны. Осталось подобрать $k$ таким образом, чтобы стороны прямоугольника были равны, т. е. $ka= (1− k)b,$ откуда $k = b∕(a+b).$ При этом сторона получившегося квадрата будет равна $ka= ab∕(a+ b).$

$PIC$

Рассмотрим три взаимно перпендикулярные прямые, пересекающиеся в точке $O.$ Отложим на этих прямых от точки $O$ отрезки $OA = 1,$ $OB = 1,$ $OC = x,$ где $x$ — некоторый параметр (см. рис.). В тетраэдре $OABC$ есть три пары скрещивающихся перпендикулярных рёбер: ребро $OC$ перпендикулярно плоскости $OAB,$ следовательно, перпендикулярно ребру $AB,$ лежащему в этой плоскости; аналогично ребра $OA$ и $OB$ перпендикулярны ребрам $BC$ и $AC$ соответственно. Покажем, что можно подобрать параметр $x >0$ так, что сторона одного из построенных квадратных сечений будет в $100$ раз больше стороны другого. Рассмотрим пару перпендикулярных скрещивающихся ребер $CO$ и $AB$ длин $x$ и $√2.$ По доказанному утверждению длина стороны соответствующего квадратного сечения равна

√- c(x)= -x-2√-- 1 x+ 2

Теперь возьмём пару перпендикулярных скрещивающихся рёбер $OA$ и $CB$ длины $1$ и $√ -2--- x + 1.$ Сторона соответствующего квадратного сечения будет равна

√x2-+-1 c2(x)= ---√-2--- 1+ x + 1

Рассмотрим функцию $f(x)= c2(x). c1(x)$ Она непрерывна при $x> 0$ и $f(1)= 1.$ Далее, $c2(x)> 1, 2$ поэтому

√- f(x)> x+√-2-> 1- (при x→ 0), 2x 2 2x

т.е. $f(1∕200)> 100.$ По теореме о промежуточном значении непрерывной функции на отрезке $[1∕200;1]$ существует такое $x∗,$ что $f(x∗)=100.$ Для найденного $x∗$ возьмём получившийся тетраэдр $OABC.$ Искомый тетраэдр подобен $OABC$ с коэффициентом подобия $1∕c(x∗). 1$

______________________________________________________________________________________________________________________________________________________

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

$PIC$

Рассмотрим параллелепипед $ABCDA1B1C1D1,$ боковые грани которого являются квадратами с диагоналями, равными $200,$ а верхняя и нижняя грани — ромбы. Рассмотрим тетраэдр $A1BDC1$ (см. рис.). Поскольку диагонали граней параллелепипеда $ABCDA1B1C1D1$ перпендикулярны, а диагонали его противоположных граней попарно параллельны, пары скрещивающихся рёбер тетраэдра перпендикулярны. Согласно первому решению у такого тетраэдра есть три квадратных сечения, параллельных парам его скрещивающихся рёбер. Сторона квадратного сечения тетраэдра, параллельного рёбрам $A1B$ и $C1D,$ будет равна $100.$

Покажем, что можно выбрать ромб в верхнем и нижнем основаниях параллелепипеда таким образом, что квадратное сечение тетраэдра, параллельное рёбрам $A1C1$ и $BD,$ будет иметь сторону длины $1.$ Спроектируем параллелепипед на верхнюю грань, при этом рёбра тетраэдра $A1BDC1$ спроектируются на стороны ромба $A1B1C1D1,$ а квадрат сечения тетраэдра, параллельного прямым $BD$ и $A1C1,$ спроектируется в равный ему квадрат, вершины которого будут лежать на сторонах ромба $A1B1C1D1.$ Сторона вписанного в ромб квадрата не превосходит меньшей диагонали ромба, поэтому, устремляя длину меньшей диагонали ромба к $0,$ получим квадрат со стороной, сколь угодно близкой к нулю. В то же время, если в качестве ромба взять квадрат, то сторона вписанного квадрата будет равна $100.$ В силу непрерывности изменения длины стороны вписанного квадрата найдётся такой ромб, что сторона вписанного в него квадрата равна $1,$ что и требовалось.

Ответ:

Да, существует

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

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

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

Задача 17#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$ искомый.

Ответ:

да

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

Задача 18#71905

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

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

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

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

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

$PIC$

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

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

Задача 19#95789

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

$PIC$

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

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

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

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

$PIC$

Ответ:

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

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

Задача 20#102213

В пространстве расположены $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$ точек