Problem 6

Let

A=(a_{ij})

(

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

) be a square matrix whose elements are nonnegative integers. Suppose that whenever

a_{ij}=0

, the sum of the elements in the

i

th row and the

j

th column is at least

n

. Prove that the sum of all elements of the matrix is at least

n^2/2

Step 7 of 7: Combine the block bounds

2S=2X+2Y+2Z\ge(2X+Y)+Y+Z\ge kn+k(n-k)+(n-k)^2=n^2

Detailed analysis

Finally, $2S=2X+2Y+2Z=(2X+Y)+Y+Z$ . Applying the three bounds gives $2S\ge kn+k(n-k)+(n-k)^2=n^2$ , so $S\ge n^2/2$ .