|
|
 |
Условие
В каждой клетке квадратной таблицы m×m клеток стоит либо натуральное число, либо нуль. При этом, если на пересечении строки и столбца стоит нуль, то сумма чисел в "кресте", состоящем из этой строки и этого столбца, не меньше m. Докажите, что сумма всех чисел в таблице не меньше чем ½ m².
Решение
Рассмотрим все ряды (строки и столбцы) и выберем ряд с наименьшей суммой чисел s. Если s ≥ m/2, то требуемое неравенство очевидно.
Пусть s < m/2 и в выбранной строке k нулей и m – k ненулевых чисел. Тогда k > m/2. В каждом из k столбцов, соответствующих нулям исходной строки, сумма чисел не меньше m – s, а в каждом из остальных столбцов сумма чисел не меньше s. Таким образом, сумма всех чисел в таблице не меньше
k(m – s) + s(m – k) = ½ m² + 2(k – m/2)(m/2 – s) > ½ m².
