Part (b) is weak -- we can actually color the $2^m \times 2^m$ board with $2^{m + 1} - 1$ colors, as follows: For $m = 0$ this is trivial. Now proceed by induction. Split the $2^m \times 2^m$ board into four $2^{m - 1} \times 2^{m - 1}$ quadrants. In the two main-diagonal quadrants, use the good coloring with colors 1 through $2^m - 1$. In one of the off-diagonal quadrants, put any Latin square with colors $2^m$ through $2^{m} + 2^{m - 1} - 1$; in the other off-diagonal quadrant, put any Latin square with colors $2^m + 2^{m - 1}$ through $2^{m + 1} - 1$. \[ \begin{array}{|c|c|c|c|} \hline 1 & 2 & 4 & 5 \\ \hline 3 & 1 & 5 & 4 \\ \hline 6 & 7 & 1 & 2 \\ \hline 7 & 6 & 3 & 1\\ \hline \end{array} \]

Part a). It is true for every odd $n$. Proof. Put $2n+1$ instead of 2001 and $4n+1$ instead of $4001$. Let chessboard is colored in some way with $4n+1$ colors. Number of all chessboard cells, different from the main diagonal's cells, is $(2n+1)^2 - (2n+1) = 4n^2+2n$. So there exists set $M$ of at least $n+1$ cells among them, colored with the same color. We have: $\#M \ge n+1$, and if $(i,j) \in M \Rightarrow 1 \le i,\,j \le 2n+1, \, i\neq j$. Then there exist $(i_1,j_1),\, (i_2,j_2) \in M$ with: $i_1=i_2$ or $i_1=j_2$. As elements of $M$, they are colored with the same color, but should be colored differently.

Part $a)$ of this problem is actually, the first part of, IMO'97'Q1 (silver matrix question). Anyways, an alternative for $a)$ is as follows. In this particular example, $k=2n-1$; hence, such a coloring means that, the union of cells located at $i^{th}$ row and column are all colored with a different color; and all the colors are used. For each color, $\{1,2,\dots,2n-1\}$, if a square is colored with it, write a number inside. Let, $c_i$ be the sum of cells in the $i^{th}$ column; and similarly, $r_i$ be the sum for the $i^{th}$ row. Clearly, $\sum_{i=1}^n c_i=\sum_{i=1}^n r_i \triangleq S$. $$ 2S = \sum_{i=1}^n (c_i+r_i)=\sum_{i=1}^n \sum_{j=1}^{2n-1}j = n^2(2n-1), $$while, $n$ is odd, a contradiction.