3. (5) The $(n, k)$-knight figure moves by $n$ positions in one of two directions and by $k$ in the other (the usual knight is thus a $(2,1)$-knight). Given $n$ and $k$, determine the smallest number of colors needed to color an infinite checkerboard such that the $(n, k)$-knight always changes color with each move.
3. Answer: two colors are sufficient.

If $n$ and $k$ have different parity, a checkerboard coloring will work. If $n$ and $k$ are both odd, a vertical stripe pattern of width 1 will suffice. If $n$ and $k$ are both even, the knight will only move within a certain subset of vertices with the same parity of coordinates. Each such subset can be easily colored based on the coloring for a $(n / 2, k / 2)$-knight.