Prove that there exists a row or a column of the chessboard which contains at least √n distinct numbers.

So we have $n$ columns and $n$ rows. Each of these we call a line. So we have $2n$ lines $L_1,L_2,...,L_{2n}$ and suppose that each line has less than $\sqrt{n}$ different numbers ($d(L_i)<\sqrt{n}$).

Suppose number $k\in\{1,2,...,n\}$ appears in $c_k$ columns and $r_k$ rows. Then we see that $$r_k+c_k \geq 2\sqrt{n} .$$

(To prove this, notice that all $n$ appearances of $k$ in the chessboard must be in the $r_k \times c_k$-rectangle formed by the $r_k$ rows and the $c_k$ columns in which $n$ appears; thus $r_k c_k \geq n$. But the AM-GM inequality yields $r_k + c_k \geq 2 \sqrt{r_k c_k} \geq 2 \sqrt{n}$ since $r_k c_k \geq n$.)

So we have: $$2n\cdot \sqrt{n}>\sum _{i=1}^{2n} d(L_i) = \sum_{k=1}^n (r_k+c_k)\geq n\cdot (2\sqrt{n})$$

A contradiction.