第6题

设

A=(a_{ij})

（

i,j=1,2,\ldots,n

）是元素为非负整数的方阵。假设只要

a_{ij}=0

，第

i

行与第

j

列元素之和就至少为

n

。证明矩阵所有元素之和至少为

n^2/2

。

第 3/7 步：将矩阵分成三个分块

X=\sum_{i,j\le k}a_{ij},\quad Y=\sum_{i\le k<j}a_{ij}+\sum_{j\le k<i}a_{ij},\quad Z=\sum_{i,j>k}a_{ij}

详细分析

假设 $k<n$ 。令 $X$ 为左上 $k\times k$ 分块之和， $Y$ 为两个非对角矩形分块之和， $Z$ 为右下 $(n-k)\times(n-k)$ 分块之和。于是 $S=X+Y+Z$ 。