mjhjmtu

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 $sqrtn$ 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 $sqrtn$ 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]$. The lower bound is obtained if all the $i$ happens to be in some $sqrt n$ edged square sub-matrix. Then $P[I_i = 1] geq 2sqrt n / (2n) = 1/sqrt n$. Hence, by linearity $textbf E[X] geq n$. This proves the existence.

So we have $C_1,...C_n$ columns and $R_1,...,R_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 $sqrtn$ different numbers ($d(L_i)<sqrtn$).

Suppose number $kin1,2,...,n$ appears in $c_k$ columns and $r_k$ rows. Then we see that $$r_k+c_k geq 2sqrtn$$

(Imagine a square $sqrtntimes sqrtn$ filled with the same number. ''Clearly'' at this configuration is the minimum for $r_k+c_k$).

So we have: $$2ncdot sqrtn>sum _i=1^2n d(L_i) = sum_k=1^n (r_k+c_k)geq ncdot (2sqrtn)$$

A contradiction.