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

Жазықтықта ешқандай үшеуі бір түзудің бойында жатпайтын 2000 нүктеден тұратын $G$ графы берілген. Олардың 1000-ы қара, ал қалған 1000-ы қызыл түске боялған. 100 қызыл нүкте дөңес 100-бұрыштың төбелері болатындай, ал қалған 1900 нүкте осы 100-бұрыштың ішінде жататындай 100 қызыл нүкте табылатыны белгілі. Қызыл нүктелерді қосатын кез келген кесінді қара нүктелерді қосатын ешбір кесіндімен қиылыспайтындай ұштары бір түсті бірнеше кесінділерді жүргізуге болатынын, және $G$-ның әрбір төбесінен сол түске боялған кез келген төбеге жете алатындай, бірнеше кесінді жүргізе алатынымызды дәлелдеңіз (графтың қабырғалары — бұл жүргізілген кесінділер). ( Зауытхан А. )

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

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

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

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

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

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

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

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

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

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

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

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

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

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