TR-MO 2001 Problem 6

We wish to color the cells of a $n \times n$ chessboard with $k$ different colors such that for every $i\in \{1,2,...,n\}$ , the $2n-1$ cells on $i$ . row and $i$ . column have all different colors.

a) Prove that for $n=2001$ and $k=4001$ , such coloring is not possible.

b) Show that for $n=2^{m}-1$ and $k=2^{m+1}-1$ , such coloring is possible.