Высшая проба 2025, 10 класс, задача 3
( баллов) На плоскости отмечено точек, никакие три из которых не лежат на одной прямой. Между каждыми двумя проведён либо красный, либо синий отрезок. Красные отрезки не имеют общих точек, кроме, возможно, отмеченных точек. Обязательно ли найдётся треугольник с вершинами в отмеченных точках, все стороны которого синие?
Ответ
Ответ. Не обязательно.
Решение. Пример . Рассмотрим набор точек, изображенных на иллюстрации. Для простоты восприятия проведем только красные отрезки.
�Ɛ �Ɠ �ƕ �Ѷ �Ɣ �ѵ �Ƒ �ƒ Докажем, что синего треугольника не найдется. Для этого разделим точки на три уровня: точки , и будут принадлежать внешнему уровню, точки , и — среднему, а и — внутреннему.
Заметим, что на каждом уровне все точки соединены между собой красными отрезками, а значит, если синий треугольник существует, все его вершины находятся на разных уровнях.
Вершина соединена со всеми вершинами среднего уровня, а значит, не может быть вершиной синего треугольника. Аналогично, вершина соединена со всеми вершинами внешнего уровня, а значит, не может быть вершиной синего треугольника. Тогда вершина соединена со всеми вершинами среднего уровня, кроме , и не может быть вершиной синего треугольника. Значит, ни одна вершина внутреннего уровня не является вершиной треугольника с синими сторонами, а значит, такого треугольника не найдется.
Пример .
Пример .
Пример . Возьмем два графа K с красными ребрами. Тогда синие отрезки образуют граф K , в котором, как и любом другом полном двудольном графе, нет треугольников.
Замечание. Если точек или более, то синий треугольник обязательно найдется. Другими словами, граф, дополнительный к планарному на и более вершинах, всегда содержит граф-треугольник в качестве подграфа