Республиканская олимпиада по математике, 2023 год, 11 класс

Дан граф $G$, вершинами которого являются 2000 точек на плоскости, никакие три из которых не лежат на одной прямой. 1000 из этих точек покрашено в черный цвет, а остальные 1000 в красный. Оказалось, что существуют 100 красных точек, которые образуют такой выпуклый 100-угольник, что все остальные 1900 точек лежат внутри этого 100-угольника. Докажите, что можно провести несколько отрезков с одноцветными концами так, чтобы любой отрезок, соединяющие красные точки не пересекался с любым отрезком, соединяющим черные точки, и при этом из любой вершины $G$ можно было добраться до любой вершины того же цвета (ребра графа — это проведенные отрезки). ( Зауытхан А. )

Комментарий/решение

Назовем треугольник 2ч, если в нем две вершины черного цвета (соединенные реором и

одна красного. Аналогично 2K, если две вершины красного цвета (соединенные ребром) и одна черного

Опрелелим операцию нал треугольником 29 или 2К слетуюшим образом

• БОО рассмотрим треугольник 2K.

• Если внутри этого треугольника нету черных точек, то соединим все красные точки внутри тре

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

• Если есть хотя бы олна черная точка внутои 2К, то возьмем любую из них и соелиним ее с черной

вершиной 2К. Заметьте. что эта черная точка соединена с предыдущей черной вершиной треугольника ?К (пля связности черных точек). Потом разобъем треутольник на тои части как показано на рисунке выше. Таким образом, 2К разбивается на два 2Ч и одну 2К и дальше делаем Ф на каждые получив-

поскольку любой треугольник 2 или 2к содержит только конечное количество точек внутри, опе

рания в какой-то момент закончится.

Возьмем изначальный граф и соединим ребром все соседние вершины выпуклой оболочки. оерем люоую черную точку внутри выпуклого Оо-угольника и разооьем граф на 100 треугольников вида 2К, и исполним ( для каждого из них. Из построения можно понять, что новые найденные точки внутри треугольников имеют реоро хотя оы с одной предыдущей вершино того же цвета. Из этого

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

все конны этих двух отрезков одного цвета