题目
设有一个方阵:每一行中最大的两个数之和都等于\(r\);每一列中最大的两个数之和都等于\(c\)。
证明:\(r=c\)。
分析
用反证法。若结论不成立,不妨设\(r\gt c\)(另一种情况由行列对称同理)。
在每一行中,把最大数圈出,把次大数打方框。于是每一行都有一对"圈+框",其和为\(r\)。
先看所有被圈出的数。若某个被圈数\(\lt r/2\),则同一行里"圈+框"之和就会\(\le r\),矛盾;所以每个被圈数都\(\ge r/2\)。
又因为我们假设每一列里最大的两个数之和是\(c\lt r\),所以同一列不可能出现两个被圈数(否则这两个被圈数都\(\ge r/2\),其和\(\ge r\gt c\))。因此,被圈数分别落在不同列。
示意图:下图展示关键变量的位置(粗体=圈出,\(\boxed{\phantom{0}}\)=方框):
\[ \begin{pmatrix} \cdots & \mathbf{y} & \boxed{z} & \cdots \\ \cdots & \boxed{x} & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots \end{pmatrix} \quad\leftarrow \begin{matrix} \text{第 }j\text{ 列} \\ \text{(}x\text{ 所在列)} \end{matrix}\]
先取所有方框数中的最大者\(x\),设它位于第\(j\)列。再看同一列中的圈出数,记为\(y\)(由前面结论,每列恰有一个圈出数)。最后看\(y\)所在行中的方框数,记为\(z\)。
由\(y\)所在行的定义有\(y+z=r\)。在第\(j\)列里,\(y\)与\(x\)同列,所以该列最大的两个数之和至少是\(y+x\)。按题设该和等于\(c\),故\(y+x\le c\)。
又由于\(x\)是所有方框数中的最大者,故\(x\ge z\)。于是\(y+x\ge y+z=r\)。
合并得\(r\le y+x\le c\),这与\(r\gt c\)矛盾。
故假设不成立,只能有\(r=c\)。