3. Each move of a chess knight is a move of one square horizontally and two squares vertically, or vice versa - one square vertically and two squares horizontally. (In the diagram on the right, the knight marked with the letter $\mathrm{K}$ can move to any of the shaded squares in one move.)

A chess knight is placed in an arbitrary square of a rectangular board measuring $2 \times$ 2016 squares. Moving according to the described rules (and not going beyond the edges of the board), it can move from this square to some other squares on the board, but not to all. What is the minimum number of squares that need to be added to the board so that the knight can move from any square of the board to all other squares? (Adding a square is done so that it shares a common side with one of the existing squares. Any number of squares can be added, and the resulting board does not necessarily have to be rectangular).

![](https://cdn.mathpix.com/cropped/2024_05_06_b7836ca1d235428660f5g-06.jpg?height=361&width=378&top_left_y=222&top_left_x=1456)
Answer: 2

Solution. Let's number the cells as shown in Figure 1. The knight can move from any cell to any cell with the same number, and cannot move to other cells.

| $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{4}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{4}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\ldots$ |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| $\mathbf{1}$ | $\mathbf{4}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{4}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{4}$ | $\ldots$ |

Fig. 1

Thus, all cells are divided into 4 sets, such that the knight cannot jump from one set to another, but can freely move within one set.

Let's add two cells as shown in Figure 2. We will prove that now the knight can move from any cell to any other cell. Cell A "connects" the cells marked in pink, i.e., through it, one can jump from set 1 to set 4. (Being in any cell with number 1, one can reach the pink cell with number 1, then through A reach the pink cell with number 4, and from there - to any cell with number 4. In the end, from any cell with number 1, one can reach any cell with number 4 using A.)

Cell B connects the cells marked in green, i.e., through it, one can jump from any of the sets 2, 3, 4 to any of these sets.

In the end, by combining cells A and B, one can move from any set to any other set. For example, to move from set 1 to set 2, first use A to move from 1 to 4, then use B to move from 4 to 2.

|  | $\mathrm{B}$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 2 | 3 | 1 | 4 | 2 | 3 | 1 | 4 | 2 | 3 | $\ldots$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| 1 | 4 | 2 | 3 | 1 | 4 | 2 | 3 | 1 | 4 | $\ldots$ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |

Fig. 2

It remains to be convinced that one cell is not enough. From Figure 3, it is clear that all added cells are divided into two types: cells A can be reached from no more than 3 cells on the board, cells B can be reached from 4 cells, but among them, there are always two from the same set (marked with the same number). That is, a cell that can be reached from all 4 sets does not exist.

|  | $A$ | $A$ | $B$ | $B$ | $\cdots$ |  |  |  |  | $\cdots$ | B | B | A | A |  |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| A | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{4}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{4}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\cdots$ | $\mathbf{O}$ | $\mathbf{1}$ | $\mathbf{4}$ | A |
| A | $\mathbf{1}$ | $\mathbf{4}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{4}$ | $\mathbf{2}$ | $\mathbf{3}$ | $\mathbf{1}$ | $\mathbf{4}$ | $\cdots$ |  | $\mathbf{2}$ | $\mathbf{3}$ | A |
|  | A | A | B | B | $\cdots$ |  |  |  |  | $\cdots$ | B | B | A | A |  |

Fig. 3

Criteria for evaluating solutions. The solution is evaluated based on the presence of three components:

a) The correct method of adding two cells is shown,

b) It is proven that with this method of adding two cells, the knight can indeed traverse the entire board,

c) It is proven that one cell is not enough.

(-) The solution does not meet any of the criteria listed below.

$(-/+)$ The solution only contains a).

(+/2) a) and b) are present, c) is missing or incorrect.

(+/-) a) and c) are present, b) is missing or incorrect.

$(+)$ a), b), and c) are present.