MathLabs

第6题

设 A=(aij)A=(a_{ij})（i,j=1,2,…,ni,j=1,2,\ldots,n）是元素为非负整数的方阵。假设只要 aij=0a_{ij}=0，第 ii 行与第 jj 列元素之和就至少为 nn。证明矩阵所有元素之和至少为 n2/2n^2/2。
第 7/7 步：合并各分块界
上一步下一步
2S=2X+2Y+2Z≥(2X+Y)+Y+Z≥kn+k(n−k)+(n−k)2=n22S=2X+2Y+2Z\ge(2X+Y)+Y+Z\ge kn+k(n-k)+(n-k)^2=n^2
详细分析

最后，2S=2X+2Y+2Z=(2X+Y)+Y+Z2S=2X+2Y+2Z=(2X+Y)+Y+Z。应用三个界得 2S≥kn+k(n−k)+(n−k)2=n22S\ge kn+k(n-k)+(n-k)^2=n^2，所以 S≥n2/2S\ge n^2/2。