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

Question

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.

Answer 1

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.

Answer 2

There is a nice interpretation of the other answer here in terms of the probabilistic method: it is showing that the expected number of distinct elements in a randomly chosen row or column is at least $\sqrt{n}$, from which it follows that some row or column has at least $\sqrt{n}$ distinct elements. Here is the formal argument.

Given an integer $k\in\{1,\ldots,n\}$ let $r_k,c_k$ be the number of rows (resp. columns) that contain the integer $k$. Observe that $r_kc_k\geq n$, since all $n$ instances of $k$ are contained in an $r_k\times c_k$ "rectangle".

Let $\Omega=\{1,\ldots,n\}\times \{R,C\}$ be the set of rows or columns. Let $U$ be a uniformly random element of $\Omega$, and let $D$ be the number of distinct integers appearing in $U$. Then $$ \mathbb E D = \sum_{i=1}^n\mathbb P(i\in D)=\sum_{i=1}^n\frac{r_i+c_i}{2n}\geq \sum_{i=1}^n\frac{\sqrt{r_ic_i}}{n}\geq \sqrt{n}. $$ It follows that there exists some $\omega\in\Omega$ such that $D(\omega)\geq \sqrt{n}$, as desired.