Problem 8.5.1. In the cells of a $12 \times 12$ table, natural numbers are arranged such that the following condition is met: for any number in a non-corner cell, there is an adjacent cell (by side) that contains a smaller number. What is the smallest number of different numbers that can be in the table?

(Non-corner cells are those that are not in the corner of the table. There are exactly 140 of them.)
Answer: 11.

Solution. First, let's provide an example with the arrangement of 11 different numbers.

| 1 | 2 | 3 | 4 | 5 | 6 | 6 | 5 | 4 | 3 | 2 | 1 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 2 | 3 | 4 | 5 | 6 | 7 | 7 | 6 | 5 | 4 | 3 | 2 |
| 3 | 4 | 5 | 6 | 7 | 8 | 8 | 7 | 6 | 5 | 4 | 3 |
| 4 | 5 | 6 | 7 | 8 | 9 | 9 | 8 | 7 | 6 | 5 | 4 |
| 5 | 6 | 7 | 8 | 9 | 10 | 10 | 9 | 8 | 7 | 6 | 5 |
| 6 | 7 | 8 | 9 | 10 | 11 | 11 | 10 | 9 | 8 | 7 | 6 |
| 6 | 7 | 8 | 9 | 10 | 11 | 11 | 10 | 9 | 8 | 7 | 6 |
| 5 | 6 | 7 | 8 | 9 | 10 | 10 | 9 | 8 | 7 | 6 | 5 |
| 4 | 5 | 6 | 7 | 8 | 9 | 9 | 8 | 7 | 6 | 5 | 4 |
| 3 | 4 | 5 | 6 | 7 | 8 | 8 | 7 | 6 | 5 | 4 | 3 |
| 2 | 3 | 4 | 5 | 6 | 7 | 7 | 6 | 5 | 4 | 3 | 2 |
| 1 | 2 | 3 | 4 | 5 | 6 | 6 | 5 | 4 | 3 | 2 | 1 |

Now, let's prove that in any arrangement satisfying the condition, there are at least 11 different numbers. We will draw arrows between cells: if two adjacent cells contain different numbers, we will draw an arrow from the larger number to the smaller one. By the condition, at least one arrow comes out of each non-corner cell.

Consider the cell in the 6th row and 6th column (one of the four "central" cells). We will construct a directed path starting from it: we will sequentially move from a cell along any of the arrows coming out of it. Since the number of cells in the table is finite, we will either eventually arrive at a cell we have already visited (obviously, this is impossible, as the numbers in the cells of our path are constantly decreasing), or we will arrive at a corner cell. To reach a corner cell, it is necessary to change rows at least 5 times and columns at least 5 times, which means making at least \(5 + 5 = 10\) moves. Therefore, our directed path passes through at least 11 cells, and all the numbers in them are clearly different.