 Tasks with inequalities. Case analysis Examples and counterexamples. Constructions

Author: Shapovosov A.B.

The plan of the shah's palace is a $6 \times 6$ square, divided into rooms of size $1 \times 1$. There is a door in the middle of each wall between the rooms. The shah told his architect: "Knock down some walls so that all rooms become $2 \times 1$, no new doors appear, and the path between any two rooms passes through no more than $N$ doors." What is the smallest value of $N$ that the shah should name to make the order executable?
Consider an arbitrary path from the bottom-left corner of the palace to the top-right corner. Since it is necessary to "climb" 5 horizontal levels and "shift to the right" 5 vertical levels, one would have to pass through at least 10 doors, visiting at least 11 rooms (including the starting and ending rooms).

11 rooms of size $1 \times 1$ could not have been transformed into 5 rooms of size $2 \times 1$. Therefore, the same path in the reconstructed palace must pass through at least 6 rooms, and thus through at least 5 doors. Such a reconstruction of the palace is indeed possible (see the diagram).

| 2 | 2 | 2 | 2 | 2 |
| :---: | :---: | :---: | :---: | :---: |
|  |  | 1 |  |  |
|  | 1 | 0 | 1 |  |
|  | 1 |  | 1 |  |
| 2 | 6 | 1 | 2 | 2 |
|  |  | 2 |  |  |

In this case, it is indeed possible to get from any room to any other room by passing through no more than 5 doors. Let's denote the central rooms with the number 0, the rooms connected to them by a door with the number 1, and the rooms connected by a door to the rooms "of type" 1 with the number 2. Since all rooms have been labeled, it is possible to get from any room to one of the central rooms by passing through no more than two doors. Therefore, it is possible to get from any room to any other room by constructing a path through the central rooms and thus passing through no more than 5 doors (the fifth door would be needed if it is necessary to move from one central room to another).

## Answer

$N=5$.

Submit a comment