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.

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.
