$:$ Steranov C.

On an $N \times N$ chessboard, there are $N^{2}$ checkers. Can they be rearranged so that any two checkers that are a knight's move apart are, after the rearrangement, only a king's move apart (i.e., adjacent)? Consider two cases:

a) $N=3$;

b) $N=8$
a) The required permutation is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_d9b26d382f9c77aca61cg-25.jpg?height=303&width=678&top_left_y=0&top_left_x=690)

b) Let's introduce two "distances" between the cells of the board: \( d_{1}(a, b) \) - the minimum number of knight moves required to move from cell \( a \) to cell \( b \), and \( d_{2}(a, b) \) - the analogous number for king moves. Let \( a' \) and \( b' \) be the cells to which the checkers move from cells \( a \) and \( b \) after the permutation. Then the condition considered in the problem obviously implies the inequality \( d_{1}(a, b) \geq d_{2}(a', b') \). We will prove that this is impossible.

First method. If \( a' \) and \( b' \) are opposite corner cells, then \( d_{2}(a', b') = 7 \), but for any two cells \( a \) and \( b \), \( d_{1}(a, b) \leq 6 \). To verify this, it is sufficient to check that from any cell on the board, you can reach any central cell of the opposite color in three moves, and any central cell of the same color in two moves.

Second method. The number of cells that are at a distance \( d_{1} = 2 \) from the central cell \( a \) is 25, as can be easily verified. But from the cell \( a' \), the number of cells at a distance \( d_{2} \leq 2 \) is no more than 24.

## Answer

a) Possible; b) impossible.