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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• треугольников нет.
• треугольник один.
• пример на рисунке:
• подходит правильный пятиугольник.

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

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

Если же помечены не все строки и не все столбцы, то всего отмечено не более строк и не более столбцов:

Отсюда следует ответ

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

Пример:

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Понятно что каждого цвета должно быть хотя бы два дома, значит, ответ для не больше 43 . Если для ответ 43 , то каждого цвета ровно два дома. Занумеруем цвета в порядке их появления слева направо, и пусть дома -го цвета имеют номера и , причем . По определению . Докажем что . Предположим противное, т.е. для каких-то оказалось . Вспомнив что и видим, что , то есть любой отрезок, содержащий также содержит , то есть нет отрезка, на котором домов -го цвета больше всего — привели предположение к противоречию.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем еще два полезных неравенства: — иначе нет отрезка из 20 домов, в который попали оба из и — иначе каждый отрезок, содержащий , также содержит или или .

_________________________________________________________________________________________________________________________________________________________________________________

Среди первых 20 номеров ровно одна -шка, это : иначе, если там есть и , среди домов от 1 до 20 есть два дома второго цвета, тогда для первого цвета нет отрезка, в котором его больше чем любого другого (поскольку только отрезок содержит два дома первого цвета, но он содержит и два дома второго). Значит, среди первых 20 домов ровно 19 -шек. Значит, из соответствующих им -шек 18 лежат среди 19 номеров от 21 до 39 , то есть там максимум одна -шка, это может быть только . Мы доказали, что . Повторив то же самое рассуждение с другого конца, получим, что . Но это противоречит неравенству (частный случай доказанного выше для ).

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

1.

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

2.

Если одна из пар или цвета она образует искомый треугольник с точкой

3.

Если все точки цвета и одна из точек тоже цвета то треугольник или искомый. В противном случае треугольник искомый.

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

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

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

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

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

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

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

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

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

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

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

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

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

Из этого следует существование индекса для которого выполняется и (или наоборот). В этом случае прямоугольники и можно вложить друг в друга.

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