Problem 1383

To determine if it is possible for every two numbers $a$ and $b$ that share a common side in Nikolai's board to be at a knight's move distance in Stoyan's board, we need to analyze the constraints and properties of knight's moves and adjacency on a chessboard.

1. Understanding Knight's Moves:
A knight's move in chess is defined as moving two squares in one direction and one square in a perpendicular direction. This means that from any given cell $(i, j)$, a knight can move to the following cells:
$$(i+2, j+1), (i+2, j-1), (i-2, j+1), (i-2, j-1), (i+1, j+2), (i+1, j-2), (i-1, j+2), (i-1, j-2)$$

2. Analyzing Adjacency:
On Nikolai's board, two numbers $a$ and $b$ are adjacent if they share a common side. This means they are either horizontally or vertically next to each other.

3. Corner Case Analysis:
Consider the corners of the $100 \times 100$ board. The corners have only two neighbors. For example, the top-left corner (cell 1) has neighbors at cells 2 and 101. Similarly, the top-right corner (cell 100) has neighbors at cells 99 and 200.

4. Knight's Move Constraints:
For the knight's move condition to hold, the numbers in adjacent cells on Nikolai's board must be reachable by a knight's move on Stoyan's board. This imposes a strict constraint on the numbering.

5. Contradiction via Parity Argument:
A key observation is that a knight's move changes the parity of the sum of the coordinates. If a cell $(i, j)$ has coordinates with sum $i + j$ even, then all cells reachable by a knight's move will have coordinates with sum odd, and vice versa.

6. **Parity on a $100 \times 100$ Board:**
On a $100 \times 100$ board, the parity of the sum of coordinates alternates between even and odd. Therefore, adjacent cells on Nikolai's board will have sums of coordinates with the same parity (both even or both odd).

7. Incompatibility with Knight's Move:
Since a knight's move changes the parity of the sum of coordinates, it is impossible for two adjacent cells on Nikolai's board (which have the same parity) to be at a knight's move distance on Stoyan's board (which requires different parities).

8. Conclusion:
The requirement that every pair of adjacent cells on Nikolai's board be at a knight's move distance on Stoyan's board leads to a contradiction due to the parity argument. Therefore, it is not possible to number the cells in such a way.

$\blacksquare$