I need to solve the following problem:
Given $n \times n$ grid of numbers from $1$ to $n$ where each number occurs in a grid exactly $n$ times, prove that there exists a row or column which contains at least $\sqrt{n}$ different numbers.
I've tried to find the solution and I've found the potential solution but I can't quite get through the step of taking $2\sqrt{n}$ as a lower bound for the number of occurencies of any number $i$ in row/columns.
I have an intuition that solution may involve naive probabilistic method, although to be honest I can't really grasp this concept very well. Can you point me to a solution or hints about this problem?
The argument on Art of Problem Solving, elaborated, is as follows.
Fix a value $k$ between $1$ and $n$. If there are $a_k$ different rows and $b_k$ different columns that contain the value $k$, then there are $a_kb_k$ total cells in the grid where a $k$ can be: all the intersection of these rows with these columns.
Since the value $k$ actually occurs exactly $n$ times, we must have $a_kb_k \ge n$. By the AM-GM inequality, $\frac{a_k+b_k}{2} \ge \sqrt{a_kb_k}$, which can be applied here to conclude that $a_k+b_k \ge 2\sqrt n$.
Number the $n$ rows and $n$ columns (collectively, "lines") $1, 2, \dots, 2n$ and let $d_i$ be the number of distinct values contained in line $i$. We have $$ \sum_{i=1}^{2n} d_i = \sum_{k=1}^n (a_k + b_k) $$ because the two sides are counting the same thing in two ways: the number of pairs $(i, k)$ where line $i$ contains the value $k$. The right-hand side of this equation adds up $n$ terms that are each at least $2 \sqrt n$, so we conclude that $$ \sum_{i=1}^{2n} d_i \ge 2 n \sqrt n $$ and therefore the average value of $d_i$ is $$ \frac1{2n} \sum_{i=1}^{2n} d_i \ge \sqrt n. $$ There must be some line $i$ for which $d_i$ is at least the average, and therefore some line $i$ containing $\sqrt n$ distinct values.