Всесиб 2024, 9 класс, задача 2
( баллов) Девять точек соединены отрезками, как показано на рисунке. Каждая точка окрашивается в один из двух цветов. Какое максимальное количество отрезков с концами разного цвета может получиться?
Ответ. .
Решение. Если убрать средние отрезки сторон большого треугольника, получатся три
маленьких треугольника. По принципу Дирихле, при любой окраске трёх вершин
треугольника в два цвета найдутся две одноцветных вершины, поэтому среди его сторон не
больше двух с концами разного цвета. Всего в трёх треугольниках будет не больше шести
таких сторон, а во всей фигуре не больше отрезков с концами разного цвета.
Замечание. Утверждение второго предложения может быть доказано прямым перебором.
Пример окраски вершин, когда получается отрезков с концами разного цвета: во
внутреннем шестиугольнике красим вершины в два цвета по очереди через одну, остальные
три вершины произвольно. Тогда разноцветными будут все стороны шестиугольника и ещё
по одному отрезку в каждом маленьком треугольнике.
Доказано, что число отрезков с концами разного цвета не превосходит
Отсутствие явного доказательства того, что в каждом маленьком треугольнике будет не больше двух сторон с концами разного цвета
Пример окраски точек с отрезками