Условие
На прямой отмечены n различных синих точек и n различных красных точек.
Докажите, что сумма попарных расстояний между точками одного цвета не превосходит суммы попарных
расстояний между точками разного цвета.
Решение
Докажем утверждение задачи в более общем предположении, когда рассматриваемые точки могут и
совпадать. Доказательство будем вести индукцией по числу N различных точек среди 2n отмеченных.
В случае N=1 доказываемое неравенство, очевидно, выполнено. Для N различных точек обозначим
через S1N сумму попарных расстояний между точками одного цвета, а через S2N – сумму
попарных расстояний между точками разных цветов.
Предположим, что S1N-1
S2N-1 , и докажем, что S1N S2N .
Занумеруем различные точки, двигаясь по прямой слева направо:
A1 , A2 , AN . Пусть с точкой A1 совпадает k красных и s синих точек.
Переместим все точки, совпадающие с A1 , в точку A2 . При этом разность
S1N-S2N не уменьшается. Действительно, так как S1N-S1N-1=(k(n-k)+s(n-s))· A1A2 ,
а S2N-S2N-1=(k(n-s)+s(n-k))· A1A2 , то
(S1N-S2N)-(S1N-1-S2N-1)=
(S1N-S1N-1)-(S2N-S2N-1)=
=
(2ks-k2-s2)· A1A2=-(k-s)2· A1A20,
т.е.
S1N-S2N S1N-1
-S2N-1
0
, откуда и следует доказываемое неравенство.
Рассмотрим произвольный отрезочек между двумя соседними отмеченными
точками. Докажем, что количество отрезков с одноцветными концами,
покрывающих его, не превосходит количества отрезков с разноцветными
концами, покрывающих его (из этого, очевидно, будет следовать требуемое).
Пусть слева от нашего отрезочка лежит
k синих и
l красных точек
(одна из них– левый конец отрезочка). Тогда количество
требуемых одноцветных отрезков равно
k(
n-k)
+l(
n-l)
, а
разноцветных–
k(
n-l)
+l(
n-k)
, и требуемое неравенство
переписывается в виде
n(
k+l)
-(
k2+l2)
n(
k+l)
-2
kl , что
очевидно.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Всероссийская олимпиада по математике |
|
год |
|
Год |
1994 |
|
Этап |
|
Вариант |
5 |
|
класс |
|
Класс |
9 |
|
задача |
|
Номер |
94.5.9.4 |
