How to find the minimum number of rooks present in the given situation on the chess board?

Question

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?

Answer 1

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.

Answer 2

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.