In an \color{cyan}{n\times n} square, each of the numbers \color{cyan}{1,2,\ldots,n} appears exactly \color{cyan}{n} times.
Show that there is a row or column that contains at least \color{cyan}{\sqrt{n}} distinct numbers.
1 Like
Let R_i and C_j be the number of unique values in a given row or column. If the average value of all R_i and C_j is at least \sqrt n, we guarantee the existence of a row or column with at least \sqrt n different values.
This average is \frac{R_1+R_2+...R_n+C_1+C_2+...C_n}{2n} in one way, but if we define a function r(x), c(x) to be the number of rows, columns in which x appears, we can count the average as \frac{\sum_{i=1}^nr(i)+c(i)}{2n}. Since each number appears exactly n times, then we can say that r(x) \times c(x) \geq n. Now r(i)+c(i) \geq 2\sqrt{r(x) \times c(x)} \geq 2 \sqrt{n}, so \frac{\sum_{i=1}^nr(i)+c(i)}{2n} \geq \frac{2n\sqrt{n}}{2n}=\sqrt{n}. We are done.
1 Like