这和矩阵有关系么.

目测是一道组合数学的点阵，把它转化成一到算二次的题应该是可以的，分类，递推，导出矛盾即可。

先证明以下结论：设aij中的最大值a,则a=1时∑aij可以取到最小值.假设当a>1时取到最小值，这是因为对于aij>1，调整第i行和第j列中的0元素为1，同时减少aij直至aij减到1(若已无0元素则继续减少aij而不改变其他元素)，这过程中∑aij只减不增.所以结论成立.
于是我们只需证明，对于元素全为0和1的矩阵，有∑aij>n^2/2.用数学归纳法证明这一结论.n=1时显然成立.假设n=k-1时成立，对于n=k,选择一个aij=0,去掉矩阵的第i行和第j列，由归纳假设剩余元素的和>(k-1)^2/2.所以∑aij>(k-1)^2/2+k>k^2/2.

自己顶。。。楼上说化成0-1矩阵感觉挺对的。。然后就是要证明要保持性质，这个矩阵里的1要超过一半。。。看上去很显然。。。就是不知道怎么严格证- -||

自挽。

再挽。。。