|
|
 |
Условие
В клетках таблицы 2000×2000 записаны числа 1 и –1. Известно, что сумма всех чисел в таблице неотрицательна. Докажите, что найдутся 1000 строк и 1000 столбцов таблицы, для которых сумма чисел, записанных в клетках, находящихся на их пересечении, не меньше 1000.
Решение
Сумма всех чисел в таблице неотрицательна, поэтому найдётся строка, содержащая не менее 1000 единиц. Переставим столбцы таблицы так, чтобы в первых 1000 клетках этой строки стояли единицы. Обозначим через A и B прямоугольники 2000·1000, образованные соответственно первыми 1000 и последними 1000 столбцами таблицы.
Пусть A1 – 1000 строк прямоугольника A с наибольшими суммами записанных в них чисел, A2 – остальные 1000 строк. Если сумма чисел в A1 не меньше 1000, то утверждение задачи доказано.
Допустим, что сумма чисел в A1 меньше 1000. Покажем, что тогда в каждой строке из A2 сумма чисел отрицательна. Действительно, если хотя бы в одной из строк из A2 сумма неотрицательна, то и во всех строках из A1 она неотрицательна. Кроме того, одна из строк A1 вся состоит из единиц, следовательно, сумма всех чисел в A1 не меньше 1000. Противоречие.
Отсюда следует, что сумма чисел в каждой строке из A2 не больше чем –2, так как сумма чисел в каждой строке чётна. Значит, сумма чисел во всем прямоугольнике A меньше чем 1000 + (–2)·1000 < –1000. Но тогда сумма чисел в прямоугольнике B больше 1000.
Пусть B1 – 1000 строк прямоугольника B с наибольшими суммами записанных в них чисел, а B2 – 1000 его остальных строк. Докажем, что сумма чисел в B1 не меньше 1000. Это верно, если сумма чисел в каждой строке из B2 неположительна. Если же хотя бы в одной строке из B2 сумма чисел положительна, то она положительна и в каждой строке из B1.
