Question 13
(SWE 5) (IMO 6) Consider the $n\times n$ array of nonnegative integers
$$\begin{pmatrix}a_{11}&a_{12}&\ldots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&&\vdots\\a_{n1}&a_{n2}&\ldots&a_{nn}\end{pmatrix},$$
with the following property: If an element $a_{ij}$ is zero, then the sum of the elements of the $i$th row and the $j$th column is greater than or equal to $n$. Prove that the sum of all the elements is greater than or equal to $\frac12n^2$.
$$\begin{pmatrix}a_{11}&a_{12}&\ldots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&&\vdots\\a_{n1}&a_{n2}&\ldots&a_{nn}\end{pmatrix},$$
with the following property: If an element $a_{ij}$ is zero, then the sum of the elements of the $i$th row and the $j$th column is greater than or equal to $n$. Prove that the sum of all the elements is greater than or equal to $\frac12n^2$.