第6题

设

A=(a_{ij})

（

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

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

a_{ij}=0

，第

i

行与第

j

列元素之和就至少为

n

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

n^2/2

。

第 2/7 步：处理全零对角线

k=n\implies 2S=\sum_{i=1}^n(r_i+c_i)\ge n^2\implies S\ge n^2/2

详细分析

令 $S=\sum_{i,j}a_{ij}$ ，记 $r_i,c_i$ 为行和、列和。若 $k=n$ ，对每个对角零应用条件得 $r_i+c_i\ge n$ 。求和得 $2S=\sum_i(r_i+c_i)\ge n^2$ ，故 $S\ge n^2/2$ 。