We associate coordinates to each unit square, the square in the bottom-left corner having coordinates $(1, 1)$, while the one in the upper-right corner has coordinates $(n, n)$. Notice that one can get from $(k, \ell)$ to $(k+3, \ell+3)$ in two moves: $(k, \ell) \to (k+2, \ell+1) \to (k+3, \ell+3)$.

• $n \equiv 1 \pmod{3}$. Using moves similar to the ones described above, the path $(1, 1) \to \dots \to (n, n)$ passes through $\frac{2n+1}{3} < \lfloor 2n/3 \rfloor + 2 < n$ unit squares, hence it does not use all the colors, whether there are $n$ colors, or only $\lfloor 2n/3 \rfloor + 2$ colors.

• $n \equiv 0 \pmod{3}$. The path that starts with
$$(1, 1) \to (2, 3) \to (3, 5) \to (5, 4) \to (6, 6) \to \dots \to (n, n)$$
and continues with moves similar to the ones described above, will pass through exactly
$$\frac{2n+3}{3} < \lfloor 2n/3 \rfloor + 2 \le n$$
squares, hence it will not pass through squares of all possible colors, and this for both the situations, a) and b);

• $n \equiv 2 \pmod{3}$. The path that starts with
$$(1, 1) \rightarrow (2, 3) \rightarrow (4, 2) \rightarrow (3, 4) \rightarrow (5, 5) \rightarrow \dots \rightarrow (n, n)$$
and continues with moves similar to the ones described above, will pass through exactly
$$\frac{2n+5}{3} = \lfloor 2n/3 \rfloor + 2 < n$$
squares, hence it does not pass through squares of all possible colors, under the conditions from a).

It remains to exhibit a coloring with $\lfloor 2n/3 \rfloor + 2$ colors such that any path $(1, 1) \to (n, n)$ contains squares of all the colors.

It is easy to see that there is no conflict in this coloring because the squares that use the first $(N-1)/2$ colors and the ones that use the last $(N-1)/2$ colors are separated by the diagonal $\{(m, n - m + 1) \mid 1 \le m \le n\}$. Finally, we color with $(N + 1)/2$ all the remaining squares.

Example 2. (given in the contest by Tudor Plopeanu) Consider the sequence $(a_m)_{m \ge 1}$ given by: $1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, \dots$. Color row number $k$, from left to right, with $a_k, a_{k+1}, \dots, a_{n+k-1}$. It is easy to check the upper-right corner has color $a_{2n-1} = N = \lfloor 2n/3 \rfloor + 2$. From a square with color $a_j$, the knight can jump to a square having one of the colors $a_{j-3}, a_{j-1}, a_{j+1}, a_{j+3}$. By the way the sequence is constructed, $a_{j-3}, a_{j-1}, a_{j+1}, a_{j+3} \in \{a_j - 1, a_j + 1\}$, so again, in its path from color 1 to color $N$, the knight can not possibly skip a color.

Example 3. Let $n = 3j + 2$, $j \in \mathbb{N}^*$. Color the bottom-left corner with 1, and use color $k$ for all the squares to which the knight can get in $k - 1$ moves, but not less. We prove that the upper-right corner has the color $N = \lfloor 2n/3 \rfloor + 2 = 2j + 3$. Once we have shown this, it is clear that, again, the knight can not skip a color, so any path has to contain squares of all the $N$ colors. For each square, the color number indicates the length of the shortest path (number of squares contained), from the square in the bottom-left corner to the given square. We prove that the shortest path to the upper-right corner contains exactly $N$ squares. We have already seen an example of a path containing $N$ squares. To prove that this is the shortest one possible, notice that each move changes the sum of coordinates by 1 or by 3, so in order to get from the bottom-left corner (having the sum of coordinates 2) to the upper-right corner (sum of coordinates $2n = 6j + 4$), one needs at least $2j + 1$ moves. But if we color the board in a chessboard pattern, the knight changes color each time it moves; the bottom-left and the upper-right corners are of the same color, so any path between the two of them will consist of an even number of moves, therefore the minimum number of moves is at least $2j + 2$; the upper-right corner will have the color $2j + 3 = N$.