MathNet 2023-part-02 — 191 problems (EN–VI) Question 39

At least $n\left(\sqrt{n}+\frac{1}{2}\right)$ squares of an $n \times n$ chessboard have been marked. Show that there exist four marked squares which form the corners of a rectangle.