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