Some squares of an $n \times n$ chessboard have been marked ($n \in N^*$). Prove that if the number of marked squares is at least $n\left(\sqrt{n} + \frac12\right)$, then there exists a rectangle whose vertices are centers of marked squares.
Let $a_i$ be the number of marked squares in row $i$.
Let $R_i$ denote the numbers of different pairs $(\ell,k)$, such that the $\ell$'th and $k$'th squares in that row are marked.
If we show that the total number of such pairs is greater than $\dbinom{n}{2}$ then by PHP there would exist two rows such that the same pair is marked, and that would make a rectangle.
To see that that is true we use Jensen on $\dbinom{x}{2}$ and get
$$\sum_{i=1}^{n} R_i=\sum_{i=1}^n \dbinom{a_i}{2}\geq n\dbinom{\sqrt{n}+\frac{1}{2}}{2}\geq \dbinom{n}{2}. \;\; \blacksquare$$