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.
 A: Each color, since it is used $n$ times, is found in at least $2\sqrt{n}$ distinct lines (i.e., rows and columns).  (If it is found in $r$ rows and $c$ columns, then $r c \ge n$; hence $r+c \ge 2\sqrt{n}$.)  Adding these up, the number of distinct (color, line) pairs is at least $2n\sqrt{n}$.  By the pigeonhole principle, then, at least one of the $2n$ lines must contain at least $\sqrt{n}$ (and hence at least $\left\lceil\sqrt{n}\right\rceil$) distinct colors.
A: 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.
