Задача 109568

Темы:    [ Системы точек ] [ Индукция в геометрии ] [ Полуинварианты ]

Сложность: 5+ Классы: 9,10,11

Условие

Автор: Мусин О.

На прямой отмечены n различных синих точек и n различных красных точек. Докажите, что сумма попарных расстояний между точками одного цвета не превосходит суммы попарных расстояний между точками разного цвета.

Решение

Докажем утверждение задачи в более общем предположении, когда рассматриваемые точки могут и совпадать. Доказательство будем вести индукцией по числу N различных точек среди 2n отмеченных. В случае N=1 доказываемое неравенство, очевидно, выполнено. Для N различных точек обозначим через S₁^N сумму попарных расстояний между точками одного цвета, а через S₂^N – сумму попарных расстояний между точками разных цветов. Предположим, что S₁^N-1 S₂^N-1 , и докажем, что S₁^N S₂^N . Занумеруем различные точки, двигаясь по прямой слева направо: A₁ , A₂ , A_N . Пусть с точкой A₁ совпадает k красных и s синих точек. Переместим все точки, совпадающие с A₁ , в точку A₂ . При этом разность S₁^N-S₂^N не уменьшается. Действительно, так как S₁^N-S₁^N-1=(k(n-k)+s(n-s))· A₁A₂ , а S₂^N-S₂^N-1=(k(n-s)+s(n-k))· A₁A₂ , то

(S₁^N-S₂^N)-(S₁^N-1-S₂^N-1)= (S₁^N-S₁^N-1)-(S₂^N-S₂^N-1)= = (2ks-k²-s²)· A₁A₂=-(k-s)²· A₁A₂0,
т.е. S₁^N-S₂^N S₁^N-1-S₂^N-10 , откуда и следует доказываемое неравенство. Рассмотрим произвольный отрезочек между двумя соседними отмеченными точками. Докажем, что количество отрезков с одноцветными концами, покрывающих его, не превосходит количества отрезков с разноцветными концами, покрывающих его (из этого, очевидно, будет следовать требуемое). Пусть слева от нашего отрезочка лежит k синих и l красных точек (одна из них– левый конец отрезочка). Тогда количество требуемых одноцветных отрезков равно k(n-k)+l(n-l) , а разноцветных– k(n-l)+l(n-k) , и требуемое неравенство переписывается в виде n(k+l)-(k²+l²) n(k+l)-2kl , что очевидно.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1994
Этап
Вариант	5
класс
Класс	9
задача
Номер	94.5.9.4