СПбГУ 2024, отборочный этап, 10–11 классы, задача 7
( баллов) В пространстве отмечены точек. Некоторые пары отмеченных точек соединены отрезками. Если какие-то два отрезка пересекаются, то у них есть общий конец. Известно, что как ни покрась точки в красный и синий цвета, количество отрезков с разноцветными концами будет не более . Докажите, что отрезков проведено не более .
Ответ
Решение. Возьмем раскраску с максимальным количеством отрезков с разноцветными концами. Рассмотрим какую-либо одну точку, пусть она будет красной, и все точки, соединенные с ней отрезком. Пусть красных точек среди них , а синих — . Это означает, что выбранная красная точка инцидентна одноцветным и разноцветным отрезкам. Теперь поменяем цвет выбранной точки на синий. Количество разноцветных отрезков, инцидентных выбранной точке, уменьшилось на и увеличилось на ; количество разноцветных отрезков всего — не увеличилось, так как было максимальным. Следовательно, . То есть количество одноцветных отрезков, чьим концом была выбранная точка, не больше, чем количество разноцветных отрезков с концом в выбранной точке. Поскольку точка выбиралась произвольно, то такое соотношение одноцветных и разноцветных отрезков верно для любой другой из ста точек. По условию, разноцветных отрезков не более , значит, одноцветных тоже не более . Поэтому и суммарно отрезков будет не более .