Олимпиадная задача Карпова: сумма на пересечении строк и столбцов в таблице 2000×2000

  Сумма всех чисел в таблице неотрицательна, поэтому найдётся строка, содержащая не менее 1000 единиц. Переставим столбцы таблицы так, чтобы в первых 1000 клетках этой строки стояли единицы. Обозначим через A и B прямоугольники 2000·1000, образованные соответственно первыми 1000 и последними 1000 столбцами таблицы.

  Пусть A₁ – 1000 строк прямоугольника A с наибольшими суммами записанных в них чисел, A₂ – остальные 1000 строк. Если сумма чисел в A₁ не меньше 1000, то утверждение задачи доказано.

  Допустим, что сумма чисел в A₁ меньше 1000. Покажем, что тогда в каждой строке из A₂ сумма чисел отрицательна. Действительно, если хотя бы в одной из строк из A₂ сумма неотрицательна, то и во всех строках из A₁ она неотрицательна. Кроме того, одна из строк A₁ вся состоит из единиц, следовательно, сумма всех чисел в A₁ не меньше 1000. Противоречие.

  Отсюда следует, что сумма чисел в каждой строке из A₂ не больше чем –2, так как сумма чисел в каждой строке чётна. Значит, сумма чисел во всем прямоугольнике A меньше чем  1000 + (–2)·1000 < –1000.  Но тогда сумма чисел в прямоугольнике B больше 1000.

  Пусть B₁ – 1000 строк прямоугольника B с наибольшими суммами записанных в них чисел, а B₂ – 1000 его остальных строк. Докажем, что сумма чисел в B₁ не меньше 1000. Это верно, если сумма чисел в каждой строке из B₂ неположительна. Если же хотя бы в одной строке из B₂ сумма чисел положительна, то она положительна и в каждой строке из B₁.

Ответ задачи отсутствует