Cute coloring problem on a board Suppose we color an $n\times n$ square board using $n$ colors exactly $n$ times each. Prove that there is either a column or a row containing at least $\lceil \sqrt n \rceil$ different colors. A friend of mine gave me this problem and I managed to solve it, but I would like to know if there is a neater way.
Regards.

Here is another solution I found: Suppose each column contains less than $\lceil \sqrt n\rceil$ different colors. Then that means The number of times a color is repeated per column is at least $n-\lceil \sqrt n \rceil$ So the number of times a number is repeated columnwise through the hole board is at least $n^2-n\lceil\sqrt n\rceil$. Note that if color 1 appears in $k_1$ columns then the number of times it is repeated columnwise is $n-k_i$ so we get $n^2-\sum_{k=1}^nk_i\leq n^2-n\lceil \sqrt n \rceil\rightarrow\sum_{k=1}^nk_i\geq n\lceil \sqrt n \rceil\ $
On the other hand note that the number of times color 1 is repeated row-wise is n minus the number of times a number is repeated the most inside any column. Note if color $1$ is found in $k_1$ columns then the maximum will be at least $\lceil \frac{n}{k_1}\rceil$ So then we must have $n^2-\sum_{k=1}^n\lceil \frac{n}{k_1}\rceil\leq n^2-n\lceil \sqrt n \rceil\rightarrow\sum_{k=1}^n\lceil \frac{n}{k_1}\rceil\geq n\lceil \sqrt n \rceil\ $.
So we must solve $\sum_{k=1}^nk_i\geq n\lceil \sqrt n \rceil$ and $\sum_{k=1}^n\lceil \frac{n}{k_1}\rceil\geq n\lceil \sqrt n \rceil$
Note that making the inequality on the left an equality would help us. So we let $\sum_{k=1}^nk_i= n\lceil \sqrt n \rceil$.
I'm stumped here.
