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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Целые точки плоскости раскрашены в $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Максимум баллов за задание: 7

На окружности отметили $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Максимум баллов за задание: 7

При каких $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Максимум баллов за задание: 7

На плоскости расположены круг и правильный $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Максимум баллов за задание: 7

В трёхмерном координатном пространстве рассмотрим множество всех кубов с целочисленными координатами вершин. Докажите, что в этом множестве существует такое бесконечное подмножество $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Максимум баллов за задание: 7

Прямоугольный параллелепипед размером $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#127165Максимум баллов за задание: 7

Дано натуральное число $N.$ Куб со стороной $2N +1$ сложен из $(2N + 1)3$ единичных кубиков, каждый из которых — либо чёрный, либо белый. Оказалось, что среди любых 8 кубиков, имеющих общую вершину и образующих куб $2× 2× 2,$ не более 4 чёрных кубиков. Какое наибольшее количество чёрных кубиков могло быть использовано?

Источники: ВСОШ, ЗЭ, 2025, 11.4 (см. olympiads.mccme.ru)

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

Подсказка 1:

В подобных задачах всегда стоит поизучать примеры раскрасок, то есть не сразу делать оценку, а попробовать понять, как может выглядеть пример, заметить закономерности и так далее. Также частенько бывает очень полезно рассмотреть маленькие случаи, времени это много не займёт, а понимания может привнести достаточно. Итак, с чего начнём?

Подсказка 2:

Раз куб со стороной 2N + 1, то логичнее всего начать рассматривать случай куба 3×3×3. Исследуйте возможные примеры, удовлетворяющие условию.

Подсказка 3:

Уверены, пример на 18 вы построили, подумайте ещё и осознайте, что пример на 20 тоже строится несильно сложно. Теперь стоит подумать насчёт оценки...

Подсказка 4:

Она здесь тривиальная, рассмотрим два диагонально противоположных куба 3×3×3 и вот уже оценка на ≤ 20 готова (осознайте это). Итого, мы поняли, что для этого куба ответ 20. В такие моменты бывает очень полезно изучить число 20, а тем более то, как оно зависит от N (в нашем случае N = 1).

Подсказка 5:

20 = 2 * 2 * 5 = (N + 1)²(4N + 1) = 4N²(4N + 1) = 20N = 4N²(N+4) = ... (в случае N = 1). Также понятно, что ответ около трети от (2N+1)³. Очевидно, что в общем виде это многочлен с коэффициентом 4 при N³. Также естественное желание свести константы к минимуму (ну или оставить ± единички). На что это намекает?

Подсказка 6:

На то, что ответ, скорее всего, равен (N+1)²(4N + 1). Попробуем доказать эту гипотезу. С чего мы начнём?

Подсказка 7:

Разумеется, с примера, ведь подогнать пример под ответ проще, чем оценку (банально в силу наглядности). Итак, вперёд пробовать!

Подсказка 8:

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

Подсказка 9:

А от подобных мыслей недалеко до декартовой системы координат. Введём же её так, что все вершины единичных кубиков будут иметь целые координаты от 0 до 2N + 1. Рассмотрим произвольный куб 2×2×2. Хотим как-то в зависимости от координат вершин его кубиков определять его цвет.

Подсказка 10:

Но наборов координат всего 27, а кубиков 8, не хотелось бы рассматривать все эти наборы координат, в идеале для каждого кубика оставить свою координату, а ещё круче, если они будут выбраны "одинаково".

Подсказка 11:

Попробуем выбрать "наконечник" куба 2×2×2, то есть в каждом маленьком кубике рассмотрим вершину, которая ближе всего к началу координат. Этот наконечник образует куб из 8 вершин. Как координаты этих вершин записываются в общем виде?

Подсказка 12:

(a, b, c); (a + 1, b, c); (a, b + 1, c); (a, b, c + 1); (a + 1, b + 1, c); (a + 1, b, c + 1); (a, b + 1, c + 1); (a + 1, b + 1, c + 1). С какой точки зрения мы можем посмотреть на эти числа, учитывая, что a, b, c — произвольные?

Подсказка 13:

С точки зрения чётности! И нам нужно покрасить ровно 4 кубика в чёрный цвет. Как же это сделать?

Подсказка 14:

Давайте сделаем так, чтобы кубики, у которых в выбранном наборе координат хотя бы 2 чётные, будут чёрными, а остальные — белыми. Осознайте, что это искомый пример. Путём несложных вычислений докажите, что всего чёрных кубиков при такой раскраске ровно (N+1)²(4N+1). Осталось подогнать оценку под пример, однако наш пример уже достаточно сложный и идейный, может попробовать как-то использовать его в оценке?

Подсказка 15:

Давайте вместо отдельной оценки попробуем доказать оптимальность нашего примера (осознайте, что эти идеи разные). Пусть в общем виде кубик тёмный, если в нашем примере он чёрный, и светлый — если в примере он белый (то есть кубик вполне может быть тёмным и светлым одновременно). Раз пример аналитический, то оценка, скорее всего, такая же. В примере мы используем идеи чётности и расстояний, и они отлично работают, может стоит вновь прибегнуть к ним? Давайте для каждой целочисленной точки в нашей ДСК (a, b, c) введём определение t-ранга. t-ранг — минимальное расстояние до грани куба, перпендикулярной соответствующей оси (разумеется, t ∈ {x, y, z}). Значения рангов — r_x, r_y, r_z. А просто рангом точки (a, b, c) — r будем называть min(r_x, r_y, r_z). Вспомним про наши идеи, что можно сделать дальше?

Подсказка 16:

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

Подсказка 17:

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

Подсказка 18:

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

Подсказка 19:

Разумеется, ∑ = сумма всех кратностей чёрных кубиков — сумма кратностей белых кубиков. Итого, опираясь на некоторую "интуицию", мы ввели много обозначений и что-то поняли про ∑. Кажется, пришло время вновь немного поисследовать, посмотреть случаи. Рассмотрим произвольный кубик 2×2×2, пусть ранги его центра — r_x, r_y, r_z. Для однозначности будем считать, что r_x ≤ r_y ≤ r_z. Разберём несколько случаев.

Подсказка 20:

1) r_x < ry;
2) r_x = r_y = 1/2 + d, где d — чётно;
3) r_x = r_y = 1/2 + d, где d — нечётно.
Аккуратно разберите каждый случай и осознайте, что кратности всех тёмных кубиков не больше 4, а всех светлых — не меньше 4 (именно тёмных и светлых, а не чёрных и белых). Отличное продвижение. Давайте теперь для удобства введём обозначения кратностей: s₁ ≤ s₂ ≤ ... ≤ s_{(2N+1)³} С учётом продвижения и построенного примера, что можно сказать про эти кратности?

Подсказка 21:

Что s₁ + ... + s_{(N+1)²(4N+1)} = s_{(N+1)²(4N+1)+1} + ... + s_{(2N+1)³}, так как в примере ∑ = 0. Фух, осталось совсем немного. Осталось красиво завершить оценку противоречием. Пусть в раскраске чёрных кубиков > (N+1)²(4N+1). Что тогда?

Подсказка 22:

0 ≥ ∑ > s₁ + ... + s_{(N+1)²(4N+1)} − s_{(N+1)²(4N+1)+1} − ... − s_{(2N+1)³} = 0. В этой цепочке неравенств есть одно упущение (осознайте какое и допишите его, не забудьте обосновать). В итоге мы получили, что 0 > 0, если кубиков > (N+1)²(4N+1). Кажется, это победа)

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

Положим $k= (N + 1)2(4N + 1).$ Введём систему координат так, что все вершины единичных кубиков будут иметь целые координаты от 0 до $2N + 1.$

Начнём с примера, показывающего, что количество чёрных кубиков действительно может быть равно $k.$ У каждого кубика рассмотрим его вершину, ближайшую к началу координат (её координаты принимают значения от 0 до $2N$ ). Пусть кубик чёрный, если хотя бы две координаты этой вершины чётны, и белый иначе. Ясно, что тогда в любом кубе $2 ×2× 2$ будет ровно 4 чёрных и 4 белых кубика. При этом количество чёрных кубиков, у которых все три соответствующих координаты чётны, равно $3 (N + 1),$ а количество кубиков, у которых чётны ровно две координаты, равно $2 3(N + 1)N,$ поэтому общее количество чёрных кубиков будет равно $k.$

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

Для каждой точки с координатами $(a,b,c)$ в большом кубе назовём её $x,$ $y$ - и $z$ -рангом соответственно числа

rx = min(a,2N + 1− a)

ry = min(b,2N + 1− b)

rz = min(c,2N + 1− c)

Назовём рангом этой точки число $r =min(r,r,r ). x y z$ Иначе говоря, $x,$ $y$ - или $z$ -ранг точки — это расстояние от неё до ближайшей грани большого куба, перпендикулярной соответствующей оси, а её ранг — это просто расстояние от неё до ближайшей грани большого куба.

Отметим все вершины единичных кубиков с нечётными рангами. Для каждой отмеченной вершины рассмотрим разность количеств чёрных и белых кубиков, сходящихся в этой вершине; поскольку все эти вершины являются центрами кубов $2× 2× 2,$ эта разность неположительна. Значит, и сумма $∑$ всех таких разностей неположительна.

Скажем, что кратность единичного кубика — это количество его отмеченных вершин (столько раз этот кубик учтён в $∑$ ). Тогда $∑$ равна разности суммы всех кратностей чёрных кубиков и суммы кратностей всех белых кубиков. Поэтому нам достаточно доказать, что если такая разность неположительна, то количество чёрных кубиков $ℓ$ не превосходит $k.$

Пусть $rx,$ $ry$ и $rz$ — это $x$ -, $y$ - и $z$ -ранги центра некоторого кубика; пусть для определённости $rx ≤ ry ≤ rz.$ Тогда нетрудно видеть, что

если $rx < ry,$ то кратность этого кубика равна 4;
если
$rx =ry = 1 +d, 2$
где $d$ чётно, то кратность кубика меньше 4, и он тёмный;
если
$rx =ry = 1 +d, 2$
где $d$ нечётно, то кратность кубика больше 4, и он светлый.

Итак, кратности всех тёмных кубиков не больше 4, а всех светлых — не меньше 4.

Пусть теперь

s1 ≤s2 ≤ ⋅⋅⋅≤ s(2N+1)3

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

s1 +s2+ ⋅⋅⋅+ sk − sk+1− ⋅⋅⋅− s(2N+1)3 = 0,

поскольку в приведённом выше примере значение $∑$ было равно 0.

Если теперь в рассматриваемой раскраске $ℓ>k$ чёрных кубиков, то

∑ 0 ≥ ≥ s1+s2+ ⋅⋅⋅+ sℓ − sℓ+1 − sℓ+2− ⋅⋅⋅− s(2N+1)3 >

> s1+ s2+ ⋅⋅⋅+sk− sk+1− ⋅⋅⋅− s(2N+1)3 = 0,

поскольку $sk+1 ≥4.$ Это противоречие показывает, что $ℓ≤ k,$ что и требовалось доказать.

Ответ:

$(N +1)2(4N +1)$

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

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

В пространстве дано $2025$ точек общего положения и $2025$ отрезков, изначально образующие замкнутую ломаную. За один ход можно взять пару отрезков $AB$ и $CD$ заменить на пару отрезков $AC$ и $BD.$ Может ли через $2025$ ходов система отрезков представлять собой $675$ треугольников?

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

Подсказка 1.

Получше изучите операцию из условия, испытав её в различных конфигурациях.

Подсказка 2.

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

Подсказка 3.

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

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

Пусть нам дана ломаная $A A 1 2$ … $A A . 2025 1$ Первые $2025− 674 =1351$ ход будем по очереди менять пару отрезков $(A A ,A A ) 1 2 3 4$ на $(A1A3,A2A4)$ и обратно. Тогда получим ломаную $A1A3A2A4$ … $A2025A1.$

Докажем индукцией по $k,$ что если у нас есть ломаная $B1B2$ … $B3kB1,$ то за $k− 1$ ход мы сможем нашими операциями создать $k$ треугольников. База индукции очевидна. Произведём индуктивный переход. Пусть утверждение доказано для $k − 1,$ докажем для $k.$ Пусть есть ломаная $B1B2$ … $B3kB1,$ тогда поменяем пару отрезков $(B3k−3B3k−2,B3kB1)$ на $(B3k−3B1,B3k−2B3k).$ Образуются треугольник $B3k−2B3k−1B3k$ и ломаная $B1B2$ … $B3k− 3B1,$ которая по предположению индукции за $k − 2$ хода разбивается на треугольники. Переход доказан, а значит, и нашу ломаную из $2025$ отрезков мы сможем разбить на треугольники за $674$ хода.

Ответ:

может

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

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

В таблице $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$

Интенсивы

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

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

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

Ответ:

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

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

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

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

Источники: Курчатов - 2024, 10.5 (см. olimpiadakurchatov.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Обозначим координаты центра тяжести (x₀, y₀). Тогда нам почти всегда подойдет прямая y₀x = x₀y, кроме одного случая. Подумайте, какого.

Подсказка 4

Да, для случая (x₀, y₀) = (0, 0) нужна другая прямая, например, y = 0. Подумайте, какие ходы необходимо делать, чтобы все камни в итоге легли на нашу прямую.

Подсказка 5

Попробуйте поочередно попарно двигать камни 1 и n, 2 и n, 3 и n, ..., n-1 и n. Если мы положили первые n-1 камешков на нашу прямую (а мы можем так сделать, потому что у нее бесконечное количество точек с целыми координатами), то почему n-й камешек окажется на прямой? Вспомните про центр тяжести.

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

Пусть начальные координаты камешков это

(x1,y1),(x2,y2),...,(xn,yn)

и пусть координаты их центра масс

( x1+x2+-...+-xn-y1+-y2+-...+-yn) (x0,y0) = n , n

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

Действительно, если $(x0,y0)⁄= (0,0),$ то годится прямая

y0x = x0y

На ней лежат узлы вида $(mnx0,mny0),$ где $m ∈ℤ.$ Если же $(x0,y0)= (0,0),$ то подойдет прямая

y = 0

Сделаем ход с $1$ -м и $n$ -м камешками так, чтобы $1$ -й камешек попал в некоторый незанятый узел прямой $ℓ.$ Отметим, что такой ход можно сделать: если $1$ -й камешек попал в узел $A,$ то $n$ -й камешек попадет в узел $A ′,$ симметричный $A$ относительно середины отрезка между положениями $1$ -го и $n$ -го камней до хода; так как возможностей выбора узла $A$ бесконечно много, то для какого-то из них соответствующий узел $′ A$ будет незанятым. Сделаем аналогичные ходы со $2$ -м и $n$ -м камешками, с $3$ -м и $n$ -м камешками, и так далее, с $(n− 1)$ -м и $n$ -м камешками.

Теперь все камни, кроме возможно $n$ -го, лежат на прямой $ℓ.$ Но заметим, что в процессе выполнения ходов центр масс камней $(x0,y0)$ остается неизменным, и он лежит на прямой $ℓ$ (согласно нашему выбору $ℓ).$ Но отсюда следует, что и оставшийся $n$ -й камень также лежит на $ℓ.$

Ответ: Да, всегда

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

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

Пример:

$PIC$

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

Ответ: да

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

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

Внутри квадрата со стороной $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

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

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

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

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

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

Ответ:

Можно

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

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

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

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

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

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

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

В ряд стоят $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

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

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

Существует ли тетраэдр, в сечениях которого двумя разными плоскостями получаются квадраты $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,$ что и требовалось.

Ответ:

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

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

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

Каждая точка плоскости раскрашена в один из трех цветов. Обязательно ли найдется треугольник площади $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$ искомый.

Ответ:

да