Разделы 
Дополнительно
Задача по математике - 1796
2019-01-20 
На прямой отмечены $n$ различных синих точек и $n$ различных красных точек. Докажите, что сумма попарных расстояний между точками одного цвета не превосходит суммы попарных расстояний между точками разного цвета.
Решение:
Первое решение. Докажем утверждение задачи в более общем предположении, когда рассматриваемые точки могут и совпадать. Доказательство будем вести индукцией по числу $N$ различных точек среди $2n$ отмеченных.
В случае $N = 1$ доказываемое неравенство, очевидно, выполнено. Для $N$ различных точек обозначим через $S_1^N$ сумму попарных расстояний между точками одного цвета, а через $S_2^N$ - сумму попарных расстояний между точками разных цветов.
Предположим, что $S_1^{N-1}$, и докажем, что $S_1^N \leq S_2^N$.
Занумеруем различные точки, двигаясь по прямой слева направо: $А_1, А_2,\cdots, A_N$. Пусть с точкой $А_1$ совпадает $k$ красных и $s$ синих точек. Переместим все точки, совпадающие с $А_1$, в точку $А_2$. При этом разность $S_1^N - S_1^{N-1}$ не уменьшается. Действительно, так как $S_1^N - S_2^{N-1} = (k(n - k) + s(n - s)) \cdot A_1A_2$, а $S_2^N - S_2^{N-1} = (k(n - s) + s(n - к)) \cdot A_1A_2$, то $(S_1^N - S_2^{N}) - (S_1^{N-1} - S_2^{N-1}) - S_2^{N-1} = (2ks - k^2 - s^2) \cdot A_1A_2 = -(k - s)^2 \cdot A_1A_2 \leq 0$, т. е. $S_1^N - S_2^N \leq S_1^{N-1} - S_2^{N-1} \leq 0$, откуда и следует доказываемое неравенство.
Второе решение. Рассмотрим произвольный отрезочек между двумя соседними отмеченными точками. Докажем, что количество отрезков с одноцветными концами, покрывающих его, не превосходит количества отрезков с разноцветными концами, покрывающих его (из этого, очевидно, будет следовать требуемое).
Пусть слева от нашего отрезочка лежит $k$ синих и $l$ красных точек (одна из них - левый конец отрезочка). Тогда количество требуемых одноцветных отрезков равно $k(n - k) + l(n - l)$, а разноцветных - $k(n - l) + l(n - k)$, и требуемое неравенство переписывается в виде $n(k +l) - (k^2 + l^2) \geq n(k + l) - 2kl$, что очевидно.
На прямой отмечены $n$ различных синих точек и $n$ различных красных точек. Докажите, что сумма попарных расстояний между точками одного цвета не превосходит суммы попарных расстояний между точками разного цвета.
Решение:
Первое решение. Докажем утверждение задачи в более общем предположении, когда рассматриваемые точки могут и совпадать. Доказательство будем вести индукцией по числу $N$ различных точек среди $2n$ отмеченных.
В случае $N = 1$ доказываемое неравенство, очевидно, выполнено. Для $N$ различных точек обозначим через $S_1^N$ сумму попарных расстояний между точками одного цвета, а через $S_2^N$ - сумму попарных расстояний между точками разных цветов.
Предположим, что $S_1^{N-1}$, и докажем, что $S_1^N \leq S_2^N$.
Занумеруем различные точки, двигаясь по прямой слева направо: $А_1, А_2,\cdots, A_N$. Пусть с точкой $А_1$ совпадает $k$ красных и $s$ синих точек. Переместим все точки, совпадающие с $А_1$, в точку $А_2$. При этом разность $S_1^N - S_1^{N-1}$ не уменьшается. Действительно, так как $S_1^N - S_2^{N-1} = (k(n - k) + s(n - s)) \cdot A_1A_2$, а $S_2^N - S_2^{N-1} = (k(n - s) + s(n - к)) \cdot A_1A_2$, то $(S_1^N - S_2^{N}) - (S_1^{N-1} - S_2^{N-1}) - S_2^{N-1} = (2ks - k^2 - s^2) \cdot A_1A_2 = -(k - s)^2 \cdot A_1A_2 \leq 0$, т. е. $S_1^N - S_2^N \leq S_1^{N-1} - S_2^{N-1} \leq 0$, откуда и следует доказываемое неравенство.
Второе решение. Рассмотрим произвольный отрезочек между двумя соседними отмеченными точками. Докажем, что количество отрезков с одноцветными концами, покрывающих его, не превосходит количества отрезков с разноцветными концами, покрывающих его (из этого, очевидно, будет следовать требуемое).
Пусть слева от нашего отрезочка лежит $k$ синих и $l$ красных точек (одна из них - левый конец отрезочка). Тогда количество требуемых одноцветных отрезков равно $k(n - k) + l(n - l)$, а разноцветных - $k(n - l) + l(n - k)$, и требуемое неравенство переписывается в виде $n(k +l) - (k^2 + l^2) \geq n(k + l) - 2kl$, что очевидно.
