ГЛАВНАЯ » РЕШЕБНИК

2015-02-17   
Рассмотрим квадратную таблицу
$a_{11}a_{12} \cdots a_{1n} \\
a_{21}a_{22} \cdots a_{2n} \\
\cdots \\
a_{n1}a_{n2} \cdots a_{nn} $
состоящую из неотрицательных целых чисел и удовлетворяющую следующему условию: как только $a_{ij}=0$, так справедливо неравенство $a_{i1} + a_{i2} + \cdots + a_{in} +a_{1j}+a_{2j}+ \cdots + a_{nj} \geq n$. Докажите, что сумма всех элементов таблицы не меньше $\frac{1}{2} n^{2}$.


Решение:


Рассмотрим всевозможные суммы элементов по строкам, а также суммы по столбцам. Пусть $p$ — наименьшее значение из всех таких сумм. Если $p \geq n$, то утверждение задачи очевидно. Пусть теперь $p < n$. Поскольку перестановка строк и столбцов таблицы, очевидно, не меняет рассматриваемых здесь сумм, то мы можем считать, что сумма элементов первой строки равна $p$ и что в этой строке вначале следуют элементы, равные нулю, а затем ненулевые элементы. Так как $p < n$, то в первой строке стоит по крайней мере $n-p$ нулей. Тогда в силу неравенства из условия задачи сумма элементов в каждом из первых $n-p$ столбцов не меньше, чем $n-p$, а сумма всех элементов в этих столбцах не меньше, чем $(n-p)^{2}$. В последних $p$ столбцах общая сумма всех элементов не меньше $p^{2}$. Следовательно, общая сумма $S$ всех элементов таблицы удовлетворяет неравенству
$S_{n} \geq (n-p)^{2}+p^{2} = \frac{n^{2}}{2} + \frac{(n-2p)^{2}}{2} \geq \frac{n^{2}}{2}$
Что и требовалось доказать.