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

On each cell of an $n \times n$ chessboard, we write a number from $1, 2, 3, . . . , n$ in such a way that each number appears exactly $n$ times. Prove that there exists a row or a column of the chessboard which contains at least $\sqrt{n}$ distinct numbers.

This question is dying for a proof by contradiction, but I can't seem to show how. When I searched through the Internet, there is the following hint:

Assume each row and each column has less than $\sqrt{n}$ distinct numbers in it. For each row or column, consider the number of distinct numbers in it.

I feel like double counting is involved in the process, but what to count in two different ways? Also I can prove the statement with the probabilistic method but I would really like to learn the double counting approach.

Here is the other proof:

Choose a random row or column ($2n$ choices). Let $\textbf X$ be the number of distinct entries in it. Use the indicator variable $I_i$, for the existence of number $i$ in the block: $\textbf X = \sum I_i.$ Clearly, $E[I_i] = P[I_i = 1]$. Then $P[I_i = 1] \geq 2\sqrt n / (2n) = 1/\sqrt n$. The lower bound is obtained if all the $i$ happens to be in some $\sqrt n$ edged square sub-matrix. Hence, by linearity $\textbf E[X] \geq \sqrt n$. This proves the existence.

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.