8.8. In the cells of an $8 \times 8$ board, natural numbers from 1 to 64 (each appearing once) are placed such that numbers differing by 1 are in adjacent side-by-side cells. What is the smallest value that the sum of the numbers on the diagonal from the bottom left to the top right corner can take?
Answer: 88.

Solution. We will color the cells of the board in a checkerboard pattern. Let the considered diagonal be black. We will move through the cells according to the numbers placed. Consider the moment when we occupy the last cell on the diagonal. Before this, we must have visited all the cells on one side of it, so we have visited at least 19 black cells (7 on the diagonal and 12 on this side). Since white and black cells alternate during the traversal of the board, we have also visited at least 19 white cells, so the number of the current cell is no less than \(2 \cdot 19 + 1 = 39\). Since all cells on the diagonal have numbers of the same parity, the numbers in the other cells are no less than \(1, 3, \ldots, 13\). Thus, the sum of the numbers on the diagonal is no less than \(1 + 3 + \ldots + 13 + 39 = 88\). The diagram shows that this value is achievable.

| 58 | 57 | 48 | 47 | 42 | 41 | 40 | 39 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 59 | 56 | 49 | 46 | 43 | 12 | 13 | 38 |
| 60 | 55 | 50 | 45 | 44 | 11 | 14 | 37 |
| 61 | 54 | 51 | 8 | 9 | 10 | 15 | 36 |
| 62 | 53 | 52 | 7 | 18 | 17 | 16 | 35 |
| 63 | 4 | 5 | 6 | 19 | 20 | 21 | 34 |
| 64 | 3 | 26 | 25 | 24 | 23 | 22 | 33 |
| 1 | 2 | 27 | 28 | 29 | 30 | 31 | 32 |