Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

  10
1 года 4 месяца назад #

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

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

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

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

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

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

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

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

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

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

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

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

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