Balkan Mathematical Olympiad

For each $i=1,\dots ,n$, define $S_i$ as the set of $j$ such that the square $(i,j)$ is marked. Suppose by contradiction that there is no rectangle with vertices in centers of marked squares. Then $|S_i\cap S_j|\le 1$, $\forall i\ne j$, and $|S_1|+|S_2|+\cdots +|S_n|\ge n(\sqrt{n}+\frac{1}{2})$.

For each pair $(i,j)$, $i<j$, there is at most one set $S_k$ such that $i,j\in S_k$. Hence the total number of pairs $(i,j)$, $i<j$ such that $i,j\in S_k$ for some $k$, is $$A=\left(\genfrac{}{}{0ex}{}{|S_1|}{2}\right)+\left(\genfrac{}{}{0ex}{}{|S_2|}{2}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{|S_n|}{2}\right)$$ On the other hand, this is certainly less than or equal to the number of all pairs $(i,j)$, $1\le i<j\le n$, namely $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$. Therefore, $\frac{n(n-1)}{2}\ge A$.

Observe that the function $f(x)=\frac{x(x-1)}{2}$ is concave up everywhere, hence Jensen's inequality implies $$A\ge n\frac{\left(\frac{|S_1|+\cdots +|S_n|}{n}\right)\left(\frac{|S_1|+\cdots +|S_n|}{n}-1\right)}{2}\ge n\cdot \frac{(\sqrt{n}+\frac{1}{2})\cdot (\sqrt{n}-\frac{1}{2})}{2}=\frac{n(n-\frac{1}{4})}{2}.$$ Therefore, $$\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge A\ge \frac{n(n-\frac{1}{4})}{2}\Rightarrow n-1\ge n-\frac{1}{4},$$ which is a contradiction.