Задача 2. Красные и синие

Почему нельзя красить как попало

Красных чисел десять, а синих только девять, так что «на глаз» красные в выигрыше. Посмотрим на набор из девятнадцати чисел $-1$ и одного числа $19$ — их сумма $19-19=0$. Если покрасить $19$ в красный, то красные — это $19$ и девять чисел $-1$:

а синие — девять чисел $-1$, их сумма $-9$. Синие проиграли: $-9<10$.

Значит, всё решает выбор, какие числа красить. Естественная мысль: синим отдать самые большие числа, а красным — самые маленькие. Лучше выбрать нельзя: если какое-то не синее число больше какого-то синего, то, поменяв их ролями, мы увеличим сумму синих (или уменьшим сумму красных). Осталось доказать, что такая раскраска срабатывает для любых двадцати чисел с суммой $0$.

Раскладываем числа по порядку

Выпишем числа по возрастанию:

Если среди чисел есть равные, их можно ставить в любом порядке. Покрасим в красный десять наименьших $a_1,\ldots,a_{10}$, число $a_{11}$ оставим без цвета, а в синий покрасим девять наибольших $a_{12},\ldots,a_{20}$. Обозначим суммы:

Сравнивать $\text{С}$ и $\text{К}$ напрямую неудобно: про сами числа мы ничего не знаем. Зато знаем, что сумма всех чисел равна $0$, — поэтому удобно сравнить каждую сумму с нулём. План такой: доказать, что $\text{С}\ge 0$ и $\text{К}\le 0$. Тогда $\text{С}\ge 0\ge \text{К}$, и задача решена.

Сумма синих не отрицательна

Предположим противное: $\text{С}<0$. Если бы все синие числа были неотрицательными, их сумма тоже была бы неотрицательной. Значит, среди синих есть отрицательное число. Самое маленькое синее число $a_{12}$ не больше его, поэтому $a_{12}<0$.

Но все остальные числа $a_1,\ldots,a_{11}$ стоят в ряду левее, то есть не больше $a_{12}$, — значит, они тоже отрицательны, и их сумма отрицательна. Тогда сумма всех двадцати чисел

— это сумма двух отрицательных чисел, она отрицательна. А по условию она равна $0$. Противоречие, поэтому $\text{С}\ge 0$.

По-другому: девять самых больших чисел «в среднем» не меньше среднего всех чисел, а среднее всех равно $0$.

Сумма красных не положительна

Рассуждаем точно так же, только с другого конца ряда. Предположим, что $\text{К}>0$. Тогда среди красных есть положительное число, и самое большое красное $a_{10}$ не меньше его, то есть $a_{10}>0$.

Все остальные числа $a_{11},\ldots,a_{20}$ стоят правее, они не меньше $a_{10}$ и потому положительны. Тогда сумма всех чисел

положительна как сумма двух положительных — снова противоречие с тем, что она равна $0$. Значит, $\text{К}\le 0$.

Собираем вместе

Из шагов 3 и 4 получаем

то есть сумма девяти синих чисел не меньше суммы десяти красных. Нужная раскраска: десять наименьших чисел — красные, девять наибольших — синие, одно число посередине остаётся без цвета.

Почему в условии сказано «не меньше», а не «больше»: если все двадцать чисел — нули, то при любой раскраске обе суммы равны $0$. Так что строгого неравенства гарантировать нельзя, а нестрогое мы доказали для любого набора.