How to find the minimum number of rooks present in the given situation on the chess board? I have the following question with me:

"Rooks are placed on the $n * n$ chess board satisfying the following condition:
If the square $(i,j)$ is free then there are at least n rooks on the $i^{th}$ row and $j^{th}$ column together. "
Show that there are at least $n^2/2$ rooks present on the board

I consider the row/column which has the minimum number of rooks, say $k$. If $k\geq n/2$ it is easy to show that
But I am unable to prove the statement for $k < n/2$. Can somebody please explan how to proceed?
 A: Let $c_j$ be the number of rooks placed on $j$-th column and $r_i$ be the number of rooks placed on $i$-th row. The condition can be phrased as
$$
(i,j) \text{ is free} \Rightarrow r_i + c_j \geq n.
$$ Now, let $F $ be the family of free pairs $(i,j)$. Then, we have
$$
\sum_{i=1}^n r_i = \sum_{j=1}^n c_j =n^2 -|F|,
$$ and
$$
n|F| \le \sum_{(i,j)\in F} (r_i + c_j).\tag{*}
$$On the other hand, the RHS of $(*)$ can be computed as
$$
\sum_{(i,j)\in F} (r_i + c_j) = \sum_{i=1}^n r_i(n-r_i) +  \sum_{j=1}^n c_j(n-c_j) = 2n(n^2-|F|) -\sum_{i=1}^n r_i^2-\sum_{j=1}^n c_j^2.
$$ since for each $i$-th row, the number of $j$ for which $(i,j)$ is free is $n-r_i$ and for each $j$-th column, it is $n-c_j$. By Cauchy-Schwarz, we have
$$
\sum_{i=1}^n r_i^2\ge \frac{(\sum_{i=1}^nr_i)^2}{n} = \frac{(n^2-|F|)^2}{n}
$$ and similarly for $\sum_{j=1}^n c_j^2$. Therefore, we get the bound
$$
n|F| \leq 2n(n^2-|F|)-2\frac{(n^2-|F|)^2}{n}.
$$ Multiply $n$ on both sides and we have
$$
2|F|^2 \le n^2 |F|.
$$ This proves $|F|\le \frac{n^2}{2}$ as desired.
A: Let $c_i$ be the number of free cells in $i$-th column and
let $r_j$  be the number of free cells in $i$-th row.
We make a graph between free cells so that two are connected if both are in the same line (row or column). So we see that each cell has a degree at most $n-2$. Let $f$ be a number of all cells. Then by handshake lemma we have $$2\varepsilon \leq f\cdot (n-2)$$
where $\varepsilon$ is total number of edges.
Notice that $$ f = \sum  _{j= 1}^n r_j = \sum _{i= 1}^n c_i$$
Let us count $\varepsilon $ on each row and column. Since we have $r_j$ free cells in $j-$ th row, we have ${r_j\choose 2}$ edges in $j$-th row. The same story goes for columns. So $$ \varepsilon = \sum _{j= 1}^n {r_j\choose 2}+\sum _{i= 1}^n{c_i\choose 2}$$ 
By Cauchy inequality we have: $$\sum _{j= 1}^n {r_j\choose 2} \geq {{1\over n}f^2-f\over 2}$$
and $$\sum _{i= 1}^n {c_i\choose 2} \geq {{1\over n}f^2-f\over 2}$$
So $$(n-2)\cdot f\geq 4{{1\over n}f^2-f\over 2} \implies f\leq {n^2\over 2}$$
and we are done.
