Олимпиадная задача по комбинаторной геометрии: сумма расстояний между синими и красными точками (Мусин О.)

Докажем утверждение задачи в более общем предположении, когда рассматриваемые точки могут и совпадать. Доказательство будем вести индукцией по числу 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-

Рассмотрим произвольный отрезочек между двумя соседними отмеченными точками. Докажем, что количество отрезков с одноцветными концами, покрывающих его, не превосходит количества отрезков с разноцветными концами, покрывающих его (из этого, очевидно, будет следовать требуемое).

Пусть слева от нашего отрезочка лежит k синих и l красных точек (одна из них– левый конец отрезочка). Тогда количество требуемых одноцветных отрезков равно k(n-k)+l(n-l), а разноцветных– k(n-l)+l(n-k), и требуемое неравенство переписывается в виде n(k+l)-(k²+l²) n(k+l)-2kl , что очевидно.

Ответ задачи отсутствует