设 $A=({a}_{ij})(i,j=1,2,…,n)$ 是以非负整数为元素的正方矩阵，又设对于任何一个 ${a}_{ij}=0$，其第 $i$ 行与第 $j$ 列诸元素的和不小于 $n$，求证：这正方矩阵的所有元素之和不小于 $\dfrac{{{n}^{2}}}{2}$．（瑞典）
【难度】
【出处】
1971年第13届IMO试题
【标注】
【答案】
略
【解析】
记 $\displaystyle R_i=\sum\limits_{j=1}^na_{ij},i=1,2,\cdots,n$
$\displaystyle C_j=\sum\limits_{i=1}^na_{ij},j=1,2,\cdots,n$
分别表示这正方矩阵的第 $i$ 行的行和与第 $j$ 列的列和．且设 $p=\min\{R_1,R_2,\cdots,R_n,C_1,C_2,\cdots,C_n\}$．
（1）若 $p\geqslant\dfrac{n}{2}$，则这正方矩阵的所有元素和 $S$ 至少为 $np$，故 $S\geqslant np\geqslant\dfrac{1}{2}n^2$．
（2）若 $p<\dfrac{n}{2}$，通过交换行和列，可以使得第一行的行和为 $p$，且第一行的前 $q$ 个元素不为零，第一行中的其他元素为 $0$．由于这 $q$ 个部为 $0$ 的数均为正整数，所以这 $q$ 个数的和 $\geqslant q$，即 $q\leqslant p\dfrac{n}{2}$．
考虑第 $q+1$ 列，它的第一个元素为 $0$，且此列和 $\geqslant n-p$，同理，第 $q+2$ 列，$\cdots$，第 $n$ 列的和均大于 $n-p$．
所以，这正方矩阵的所有元素之和
$\begin{aligned}
S&\geqslant pq+(n-p)(n-q)\\
&=\dfrac{n^2}{2}+\dfrac{1}{2}(n-2p)(n-2q)\\
&\geqslant \dfrac{n^2}{2}.
\end{aligned}$
$\displaystyle C_j=\sum\limits_{i=1}^na_{ij},j=1,2,\cdots,n$
分别表示这正方矩阵的第 $i$ 行的行和与第 $j$ 列的列和．且设 $p=\min\{R_1,R_2,\cdots,R_n,C_1,C_2,\cdots,C_n\}$．
（1）若 $p\geqslant\dfrac{n}{2}$，则这正方矩阵的所有元素和 $S$ 至少为 $np$，故 $S\geqslant np\geqslant\dfrac{1}{2}n^2$．
（2）若 $p<\dfrac{n}{2}$，通过交换行和列，可以使得第一行的行和为 $p$，且第一行的前 $q$ 个元素不为零，第一行中的其他元素为 $0$．由于这 $q$ 个部为 $0$ 的数均为正整数，所以这 $q$ 个数的和 $\geqslant q$，即 $q\leqslant p\dfrac{n}{2}$．
考虑第 $q+1$ 列，它的第一个元素为 $0$，且此列和 $\geqslant n-p$，同理，第 $q+2$ 列，$\cdots$，第 $n$ 列的和均大于 $n-p$．
所以，这正方矩阵的所有元素之和
$\begin{aligned}
S&\geqslant pq+(n-p)(n-q)\\
&=\dfrac{n^2}{2}+\dfrac{1}{2}(n-2p)(n-2q)\\
&\geqslant \dfrac{n^2}{2}.
\end{aligned}$
答案
解析
备注
