There are some checkers in $n\cdot n$ size chess board.Known that for all numbers $1\le i,j\le n$ if checkwork in the intersection of $i$ th row and $j$ th column is empty,so the number of checkers that are in this row and column is at least $n$.Prove that there are at least $\frac{n^2}{2}$ checkers in chess board.
Problem
Source: Azerbaijan Balkan TST 2016 no 3
Tags: combinatorics
15.11.2016 06:05
Assign squares with checkers to be red and square with non-checkers to be blue. If there are $l$ blue squares in the chessboard. I suffices to prove $l \le n^2/2$. We count number of pairs of red and blue squares in either same row or same column in two ways. Denote $a_{i} \; (1 \le i \le l)$ as number of red squares that are in same row or column with a blue square then $a_i \ge n$ , $b_i \; (1 \le i \le n^2-l)$ as number of blue squares that are in same row or column with a red square. This follows $$S=\sum_{j=1}^{n^2-l}b_j=\sum_{i=1}^la_i \ge nl.$$Note that $S$ is also equal to the total number of pairs of squares in same column or row minus pairs that are both red and pairs that are both blue. The total number of pairs of squares in same row or same column is $2n\binom{n}{2}=n^2(n-1)$. It suffices to find an upper bound for number of pairs that are both blue (or red). Denote $x_i \; ( 1 \le i \le n)$ as number of blue squares on the $i$th row then $\sum_{i=1}^nx_i=l$. Hence, according to Jensen inequality, the total number of pairs of squares in same row that are both blue is $$\sum_{i=1}^n \binom{x_i}{2} \ge n \binom{l/n}{2}= \frac{l^2}{2n}- \frac l2.$$Similarly, there are at least $\frac{l^2}{2n}- \frac l2 $ pairs of squares in same column that are both blue. Thus, the total number of pairs of squares that are both blue is at least $\frac{l^2}{n}-l$. For pairs of squares that are both red, similarly, we find a lower bound of $\frac{(n^2-l)^2}{n}-(n^2-l)$. Thus, \begin{align*} S & \le n^2(n-1)-\left( \frac{l^2}{n}-l \right)- \left( \frac{(n^2-l)^2}{n}-(n^2-l) \right), \\ & =n^3-\frac{l^2+(n^2-l)^2}{n} \le \frac{n^3}{2}. \end{align*}This follows $nl \le \frac{n^3}{2}$ or $l \le \frac{n^2}{2}$ or $n^2-l \ge \frac{n^2}{2}$. Thus, there are at least $\frac{n^2}{2}$ checkers in the chessboard.
15.11.2016 06:45
Suppose the 'emptiest' line (lines being rows and columns) contains $k$ checkers. WLOG it is the first row. Any column with an empty first cell contains at least $n-k$ checkers. Any other column contains at least $k$ checkers. Hence the board contains at least $(n-k)^2+k^2$ checkers. This (as a quadratic function) is minimized at $k=\frac{n}{2}$, which gives the bound.
17.11.2016 18:09
My idea is same as @shinichiman, but my proof seems different. We will count $(A,B)$ in two way, where $A$, $B$ are two cell has checker and doesn't have checker, respectively, so that $A$ and $B$ lie in same column or row. Let $k$ be number of cell that doesn't have checker, then by hypothesis, each of these cell lies with at least $n$ other cells that have checker, so the least pair is $kn$. On the otherhand, let $x_i,y_i$ be the number of cells has checker and doesn't have checker, respectively in the column $1\leq i\leq n$, then $x_i+y_i=n$ and in this $i$-th column, there are $x_i.y_i$ pairs $(A,B)$, by $AM-GM$, it's not exceed $\frac{n^2}{4}$. Summing $i$ over $1$ to $n$, we have, the maximum pair, counting in horizontal direction is $n.\frac{n^2}{4}=\frac{n^3}{4}$, anagoulously, counting in vertical, the maximum pair is $\frac{n^3}{4}$, so the maximum pair is $\frac{n^3}{2}$ Thus, $kn\leq\frac{n^3}{2}$ and hence: $k\leq\frac{n^2}{2}$, and since there are $n^2$ cells, we have desired thing!