2019-01-20
В клетках таблицы $2000 \times 2000$ записаны числа 1 и -1. Известно, что сумма всех чисел в таблице неотрицательна. Докажите, что найдутся 1000 строк и 1000 столбцов таблицы таких, что сумма чисел, записанных в клетках, находящихся на их пересечении, не меньше 1000.
Решение:
Сумма всех чисел в таблице неотрицательна, поэтому найдется строка, содержащая не менее 1000 единиц. Переставим столбцы таблицы так, чтобы в первых 1000 клетках этой строки стояли 1. Обозначим через $А$ и $B$ прямоугольники $2000 \cdot 1000$, образованные соответственно первыми 1000 и последними 1000 столбцами таблицы.
Пусть $А_1 - 1000$ строк прямоугольника $А$ с наибольшими суммами записанных в них чисел, $А_2$ - остальные 1000 строк. Если сумма чисел в $А_1$ не меньше 1000, то утверждение задачи доказано.
Допустим, что сумма чисел в $А_1$ меньше 1000. Покажем, что тогда в каждой строке из $A_2$ сумма чисел отрицательна. Действительно, если хотя бы в одной из строк из $А_2$ сумма неотрицательна, то и во всех строках из $А_1$ она неотрицательна. Кроме того, одна из строк $А_1$ вся состоит из 1, следовательно, сумма всех чисел в $А_1$ не меньше 1000. Противоречие. Отсюда следует, что сумма чисел в каждой строке из $А_2$ не больше, чем -2, так как сумма чисел в любой строке четна. Значит, сумма чисел во всем прямоугольнике $А$ меньше, чем $1000 + (-2) \cdot 1000$, т. е. меньше - 1000. Но по условию сумма чисел в прямоугольнике $B$ больше 1000. Пусть $B_1$ - 1000 строк прямоугольника $B$ с наибольшими, а $B_2$ - 1000 строк прямоугольника $B$ с наименьшими суммами записанных в них чисел. Докажем, что сумма чисел в $B_1$ не меньше 1000. Это верно, если сумма чисел в каждой строке из $B_2$ неположительна. Если же хотя бы в одной строке из $В_2$ сумма чисел положительна, то она положительна и в каждой строке из $B_1$. Утверждение задачи доказано.